結果
問題 | No.658 テトラナッチ数列 Hard |
ユーザー | aim_cpo |
提出日時 | 2018-03-02 22:59:29 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 244 ms / 2,000 ms |
コード長 | 1,394 bytes |
コンパイル時間 | 1,594 ms |
コンパイル使用メモリ | 176,260 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-22 05:24:04 |
合計ジャッジ時間 | 3,249 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,940 KB |
testcase_02 | AC | 2 ms
6,940 KB |
testcase_03 | AC | 2 ms
6,940 KB |
testcase_04 | AC | 95 ms
6,940 KB |
testcase_05 | AC | 109 ms
6,944 KB |
testcase_06 | AC | 136 ms
6,944 KB |
testcase_07 | AC | 140 ms
6,940 KB |
testcase_08 | AC | 164 ms
6,940 KB |
testcase_09 | AC | 240 ms
6,944 KB |
testcase_10 | AC | 244 ms
6,940 KB |
ソースコード
#include<bits/stdc++.h>#define ll long long#define fi first#define se second#define show(x) cerr<<#x<<"="<<x<<"\n"using namespace std;typedef vector<int> vec;typedef vector<vec> mat;mat mul(mat &a,mat &b){mat c(a.size(),vec(b[0].size()));for(int i=0;i<(int)a.size();i++){for(int k=0;k<(int)b.size();k++){for(int j=0;j<(int)b[0].size();j++){c[i][j]=(c[i][j]+a[i][k]*b[k][j])%17;}}}return c;}mat pow(mat a,ll n){mat b(a.size(),vec(a.size()));for(int i=0;i<(int)a.size();i++){b[i][i]=1;}while(n>0){if(n&1)b=mul(b,a);a=mul(a,a);n>>=1;}return b;}int n,m;string s;int main(){ios::sync_with_stdio(false);cin.tie(0);cout.precision(10);cout<<fixed;#ifdef LOCAL_DEFINEFILE *stream1;//FILE *stream2;stream1=freopen("in","r",stdin);//stream2=freopen("out","w",stdout);if(stream1==NULL)return 0;//if(stream2==NULL)return 0;#endifcin>>n;for(int i=0;i<n;i++){ll q;cin>>q;mat a(4,vec(4));for(int j=0;j<4;j++)for(int k=0;k<4;k++)a[j][k]=0;a[0][0]=1,a[1][0]=1,a[2][1]=1,a[3][2]=1;a[0][1]=1,a[0][2]=1,a[0][3]=1;a=pow(a,q-1);cout<<a[3][0]<<endl;}#ifdef LOCAL_DEFINEcerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n";fclose(stream1);//fclose(stream2);#endifreturn 0;}