結果
問題 | No.658 テトラナッチ数列 Hard |
ユーザー |
![]() |
提出日時 | 2023-03-08 12:03:53 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 970 ms / 2,000 ms |
コード長 | 1,451 bytes |
コンパイル時間 | 4,545 ms |
コンパイル使用メモリ | 255,956 KB |
最終ジャッジ日時 | 2025-02-11 06:48:50 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 8 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace std; using namespace atcoder; using ll=long long; using ld=long double; ld pie=3.141592653589793; ll inf=10010010010010010; ll mod=17; vector<vector<ll>>mul(vector<vector<ll>>&a,vector<vector<ll>>&b){ vector<vector<ll>>c(a.size(),vector<ll>(b[0].size(),0)); for (ll i = 0; i < a.size(); i++) { for (ll j = 0; j < b[0].size(); j++) { for (ll k = 0; k < a[0].size(); k++) { c[i][j]+=a[i][k]*b[k][j]; c[i][j]%=mod; } } } return c; } vector<vector<ll>>matpow(vector<vector<ll>>a,ll n){ vector<vector<ll>>b(a.size(),vector<ll>(a.size(),0)); for (ll i = 0; i < a.size(); i++) { b[i][i]=1; } while (n>0) { if (n%2) { b=mul(a,b); n-=1; }else{ a=mul(a,a); n/=2; } } return b; } int main(){ ll q; cin >> q; for (ll i = 0; i < q; i++) { ll n; cin >> n; vector<vector<ll>>a(4,vector<ll>(4,0)); a[0][0]=1,a[0][1]=1,a[0][2]=1,a[0][3]=1; a[1][0]=1,a[2][1]=1,a[3][2]=1; if (n<=3) { cout << 0 << endl; }else if (n==4) { cout << 1 << endl; }else{ vector<vector<ll>>d=matpow(a,n-4); cout << d[0][0] << endl; } } }