結果
問題 | No.658 テトラナッチ数列 Hard |
ユーザー |
![]() |
提出日時 | 2018-03-02 22:32:25 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 306 ms / 2,000 ms |
コード長 | 920 bytes |
コンパイル時間 | 963 ms |
コンパイル使用メモリ | 75,936 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-13 03:49:38 |
合計ジャッジ時間 | 3,384 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 8 |
ソースコード
#include<algorithm>#include<iostream>#include<vector>using namespace std;typedef long long lint;typedef vector<int>vi;typedef pair<int,int>pii;#define rep(i,n)for(int i=0;i<(int)(n);++i)const int A=4;vector<vi> mul(const vector<vi> &a,const vector<vi> &b){vector<vi> ret(A, vi(A));rep(i,A){rep(j,A){rep(k,A){ret[i][j]+=a[i][k]*b[k][j];ret[i][j]%=17;}}}return ret;}vector<vi> pow(const vector<vi> &a,lint e){vector<vi> cur(A,vi(A,0));rep(i,A)cur[i][i]=1;for(int i=63;i>=0;--i){cur=mul(cur,cur);if(e&1LL<<i)cur=mul(cur,a);}return cur;}int main(){int q;cin>>q;rep(_,q){lint n;cin>>n;vector<vi> a(A,vi(A));rep(i,A)a[A-1][i]=1;rep(i,A-1)a[i][i+1]=1;vector<vi> t=pow(a,n);if(0){rep(i,A){rep(j,A){cerr<<t[i][j]<<" ";}cerr<<endl;}}cout<<t[0][0]<<endl;}}