結果
問題 | No.658 テトラナッチ数列 Hard |
ユーザー |
|
提出日時 | 2023-02-23 14:09:13 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 95 ms / 2,000 ms |
コード長 | 1,784 bytes |
コンパイル時間 | 770 ms |
コンパイル使用メモリ | 82,052 KB |
最終ジャッジ日時 | 2025-02-10 20:02:43 |
ジャッジサーバーID (参考情報) |
judge3 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 8 |
ソースコード
#include<iostream> #include<vector> using namespace std; using ll=long long; #define rep(i,n) for(int i=0;i<n;i++) #define rrep(i,n) for(int i=(n)-1;i>=0;i--) #define all(v) v.begin(),v.end() #define rall(v) v.rbegin(),v.rend() template<class T> bool chmax(T &a, T b){if (a < b){a = b;return true;} else return false;} template<class T> bool chmin(T &a, T b){if (a > b){a = b;return true;} else return false;} const int MOD=17; template<class T> vector<vector<T>> pd(vector<vector<T>> &A, vector<vector<T>> &B){ int nx = A.size(), mx = A[0].size(), lx = B[0].size(); vector<vector<T>> C(nx, vector<T>(lx)); for (int i = 0; i < nx; i++){ for (int j = 0; j < lx; j++){ for (int k = 0; k < mx; k++){ C[i][j] += A[i][k] * B[k][j]; C[i][j] %= MOD; } } } return C; } template<class T> vector<vector<vector<T>>> set_matrix(vector<vector<T>> A){ vector<vector<vector<T>>> V; for (int i = 0; i < 60; i++){ V.push_back(A); A = pd(A, A); } return V; } template<class T> vector<vector<T>> matrix_pow(vector<vector<vector<T>>> &V, ll k){ int l = V[0].size(); vector<vector<T>> M(l ,vector<T>(l)); for (int i = 0; i < l; i++){ M[i][i] = 1; } for (int i = 0; i < 60; i++){ if (k >> i & 1){ M = pd(V[i], M); } } return M; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int q; cin>>q; vector<vector<int>>A={{1,1,1,1},{1,0,0,0},{0,1,0,0},{0,0,1,0}}; vector<vector<vector<int>>>V=set_matrix(A); while(q--){ ll n; cin>>n; n-=4; vector<vector<int>>M=matrix_pow(V,n); if(n<0)cout<<0<<"\n"; else cout<<M[0][0]<<"\n"; } }