結果
問題 |
No.658 テトラナッチ数列 Hard
|
ユーザー |
![]() |
提出日時 | 2019-01-20 01:29:43 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 1,363 ms / 2,000 ms |
コード長 | 1,224 bytes |
コンパイル時間 | 1,885 ms |
コンパイル使用メモリ | 170,800 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-18 14:59:43 |
合計ジャッジ時間 | 8,178 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 8 |
ソースコード
#include<bits/stdc++.h> using namespace std; typedef long long ll; ll mod=17; vector<vector<ll>> seki(vector<vector<ll>> a,vector<vector<ll>> b){ vector<vector<ll>> ret; ll s=a.size(),t=b[0].size(); for(ll i=0;i<s;i++){ vector<ll> c; for(ll j=0;j<t;j++){ ll sum=0; for(ll k=0;k<a[0].size();k++){ sum+=a[i][k]*b[k][j]; sum%=mod; } c.push_back(sum); } ret.push_back(c); } return ret; } vector<vector<ll>> kai(vector<vector<ll>> a,ll n){ vector<vector<ll>> ret=a; vector<vector<ll>> now=a; for(ll i=0;i<a.size();i++){ for(ll j=0;j<a.size();j++){ if(i==j)ret[i][j]=1; else ret[i][j]=0; } } while(n>0){ if(n%2==1){ ret=seki(ret,now); } now=seki(now,now); n/=2; } return ret; } int main(){ ll q;cin>>q; vector<vector<ll>> t={{1,1,1,1},{1,0,0,0},{0,1,0,0},{0,0,1,0}}; for(ll i=0;i<q;i++){ ll n;cin>>n; if(n<=3)cout<<0<<endl; else if(n==4)cout<<1<<endl; else{ vector<vector<ll>> now=kai(t,n-4); cout<<now[0][0]%mod<<endl; } } }