結果
問題 | No.1136 Four Points Tour |
ユーザー |
![]() |
提出日時 | 2022-11-09 02:23:05 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 972 bytes |
コンパイル時間 | 1,821 ms |
コンパイル使用メモリ | 174,992 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-22 09:37:43 |
合計ジャッジ時間 | 2,996 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 41 |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef vector<vector<int64_t>> Matrix; // 行列の乗算(mod) Matrix mat_mul(const Matrix &a, const Matrix &b, int64_t mod) { Matrix c(a.size(), vector<int64_t>(b[0].size())); for(int i = 0; i < a.size(); i++) { for(int k = 0; k < b.size(); k++) { for(int j = 0; j < b[0].size(); j++) { c[i][j] += a[i][k] * b[k][j]; c[i][j] %= mod; } } } return c; } // 行列の累乗(mod) Matrix mat_pow(Matrix a, int64_t n, int64_t mod) { Matrix b(a.size(), vector<int64_t>(a.size())); for(int i = 0; i < a.size(); i++) b[i][i] = 1; while(n > 0) { if(n & 1) b = mat_mul(b, a, mod); a = mat_mul(a, a, mod); n >>= 1; } return b; } int main() { int64_t n; cin >> n; const int64_t mod = 1000000007; Matrix A = {{0, 1, 1, 1}, {1, 0, 1, 1}, {1, 1, 0, 1}, {1, 1, 1, 0}}; Matrix B = {{1}, {0}, {0}, {0}}; Matrix ans = mat_mul(mat_pow(A, n, mod), B, mod); cout << ans[0][0] << endl; return 0; }