結果
問題 |
No.1879 How many matchings?
|
ユーザー |
|
提出日時 | 2025-05-21 15:37:09 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 2,736 bytes |
コンパイル時間 | 4,011 ms |
コンパイル使用メモリ | 286,316 KB |
実行使用メモリ | 7,844 KB |
最終ジャッジ日時 | 2025-05-21 15:37:14 |
合計ジャッジ時間 | 4,420 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 15 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/modint> using namespace std; using namespace atcoder; using ll = long long; using mint = modint1000000007; template<typename T> struct Matrix : vector<vector<T>> { using vector<vector<T>>::vector; using vector<vector<T>>::operator=; Matrix() {} Matrix(ll N) { *this = vector<vector<T>>(N, vector<T>(N, T())); for(ll i = 0; i < N; i++) { (*this)[i][i] = 1; } } Matrix(ll H, ll W, T x = 0) { *this = vector<vector<T>>(H, vector<T>(W, x)); } Matrix(vector<vector<T>> v) { *this = v; } Matrix operator+(const Matrix &m) const { return Matrix(*this) += m; } Matrix operator-(const Matrix &m) const { return Matrix(*this) -= m; } Matrix operator*(const Matrix &m) const { return Matrix(*this) *= m; } Matrix operator*(const T &x) const { return Matrix(*this) *= x; } Matrix operator^(ll n) const { return Matrix(*this) ^= n; } Matrix operator+=(const Matrix &m) const { ll h = this->size(), w = (*this)[0].size(); assert(h == m.size() && w == m[0].size()); for(ll i = 0; i < h; i++) { for(ll j = 0; j < w; j++) { *this[i][j] += m[i][j]; } } return *this; } Matrix operator-=(const Matrix &m) { ll h = this->size(), w = (*this)[0].size(); assert(h == m.size() && w == m[0].size()); for(ll i = 0; i < h; i++) { for(ll j = 0; j < w; j++) { *this[i][j] -= m[i][j]; } } return *this; } Matrix operator*=(const Matrix &m) { ll h = this->size(), w = (*this)[0].size(); assert(w == (ll)m.size()); vector<vector<T>> r(h, vector<T>(m[0].size(), T(0))); for(ll i = 0; i < h; i++) { for(ll j = 0; j < (ll)m[0].size(); j++) { for(ll k = 0; k < w; k++) { r[i][j] += (*this)[i][k] * m[k][j]; } } } this->swap(r); return *this; } Matrix operator*=(const T &x) { ll h = this->size(), w = (*this)[0].size(); for(ll i = 0; i < h; i++) { for(ll j = 0; j < w; j++) { *this[i][j] *= x; } } return *this; } Matrix operator^=(ll n) { ll h = this->size(); Matrix m(h); while(n) { if(n & 1) { m *= *this; } *this *= *this; n >>= 1LL; } this->swap(m); return *this; } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); ll N; cin >> N; Matrix<mint> A = {{0, 1, 0, 1}, {1, 0, 0, 0}, {0, 1, 0, 0}, {0, 0, 1, 0}}; Matrix<mint> B = {{1, 1, 1, 1}, {1, 0, 0, 0}, {0, 1, 0, 0}, {0, 0, 1, 0}}; Matrix<mint> dp = {{3}, {1}, {1}, {1}}; if(N == 1) { cout << 1 << "\n"; } if(N == 2) { cout << 1 << "\n"; } if(N == 3) { cout << 3 << "\n"; } if(N < 4) { return 0; } auto C = B * A; dp = (C ^ ((N - 3) / 2)) * dp; if(~N & 1) { dp = A * dp; } cout << dp[0][0].val() << "\n"; }