結果
問題 | No.658 テトラナッチ数列 Hard |
ユーザー | tsutaj |
提出日時 | 2018-03-02 22:31:21 |
言語 | C++14 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 533 ms / 2,000 ms |
コード長 | 2,673 bytes |
コンパイル時間 | 2,122 ms |
コンパイル使用メモリ | 115,076 KB |
実行使用メモリ | 4,380 KB |
最終ジャッジ日時 | 2023-09-03 23:11:42 |
合計ジャッジ時間 | 5,369 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge13 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,376 KB |
testcase_01 | AC | 2 ms
4,376 KB |
testcase_02 | AC | 2 ms
4,380 KB |
testcase_03 | AC | 3 ms
4,376 KB |
testcase_04 | AC | 201 ms
4,380 KB |
testcase_05 | AC | 230 ms
4,376 KB |
testcase_06 | AC | 285 ms
4,380 KB |
testcase_07 | AC | 306 ms
4,380 KB |
testcase_08 | AC | 359 ms
4,380 KB |
testcase_09 | AC | 533 ms
4,376 KB |
testcase_10 | AC | 533 ms
4,380 KB |
ソースコード
// 基本テンプレート #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; }