結果
問題 | No.658 テトラナッチ数列 Hard |
ユーザー |
![]() |
提出日時 | 2018-03-02 22:31:21 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 504 ms / 2,000 ms |
コード長 | 2,673 bytes |
コンパイル時間 | 1,315 ms |
コンパイル使用メモリ | 116,564 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-13 03:46:47 |
合計ジャッジ時間 | 4,063 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 8 |
ソースコード
// 基本テンプレート #include <iostream> #include <iomanip> #include <cstdio> #include <string> #include <cstring> #include <deque> #include <list> #include <queue> #include <stack> #include <vector> #include <utility> #include <algorithm> #include <map> #include <set> #include <complex> #include <cmath> #include <limits> #include <cfloat> #include <climits> #include <ctime> #include <cassert> #include <numeric> #include <fstream> #include <functional> using namespace std; #define rep(i,a,n) for(int (i)=(a); (i)<(n); (i)++) #define repq(i,a,n) for(int (i)=(a); (i)<=(n); (i)++) #define repr(i,a,n) for(int (i)=(a); (i)>=(n); (i)--) #define debug(...) fprintf(stderr, __VA_ARGS__) #define int long long int template<typename T> void chmax(T &a, T b) {a = max(a, b);} template<typename T> void chmin(T &a, T b) {a = min(a, b);} template<typename T> void chadd(T &a, T b) {a = a + b;} typedef pair<int, int> pii; typedef long long ll; int dx[] = {0, 0, 1, -1}; int dy[] = {1, -1, 0, 0}; const ll INF = 1001001001001001LL; const ll MOD = 17LL; // 行列ライブラリ // Verified: TopCoder SRM 704 Div.2 (ModEquationEasy) // 行列の積 と 累乗(繰り返し二乗法) // Matrix Library Begin (C++11) template <typename T> using Matrix = vector< vector<T> >; template <typename T> void init_mat(Matrix<T> &A, int h, int w) { A.resize(h, vector<T>(w, 0)); } template <typename T> Matrix<T> calc_mat(Matrix<T> A, Matrix<T> B) { Matrix<T> C(A.size(), vector<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]; // modなし C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD; // modあり } } } return C; } template <typename T> Matrix<T> mat_pow(Matrix<T> A, ll n) { Matrix<T> B(A.size(), vector<T>(A.size())); for(int i=0; i<A.size(); i++) B[i][i] = 1; while(n > 0) { if(n & 1) B = calc_mat(B, A); A = calc_mat(A, A); n >>= 1; } return B; } // Matrix Library End signed main() { int Q; cin >> Q; while(Q--) { int t; cin >> t; if(t <= 3) { cout << 0 << endl; continue; } t -= 3; Matrix<int> mat, vec; init_mat(mat, 4, 4); init_mat(vec, 4, 1); mat = { {1, 1, 1, 1}, {1, 0, 0, 0}, {0, 1, 0, 0}, {0, 0, 1, 0}}; vec = { {1}, {0}, {0}, {0} }; mat = mat_pow(mat, t-1); mat = calc_mat(mat, vec); cout << mat[0][0] << endl; } return 0; }