結果
問題 |
No.3228 Very Large Fibonacci Sum
|
ユーザー |
![]() |
提出日時 | 2025-08-08 22:39:50 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 1,155 bytes |
コンパイル時間 | 5,665 ms |
コンパイル使用メモリ | 335,564 KB |
実行使用メモリ | 7,716 KB |
最終ジャッジ日時 | 2025-08-08 22:39:57 |
合計ジャッジ時間 | 6,697 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 |
ソースコード
#include<bits/stdc++.h> #include<atcoder/all> using namespace std; using T=atcoder::modint1000000007; struct matrix{ int h,w; vector<vector<T>> val; matrix(int r,int c=-1):h(r),w(c){ if (w==-1) w=h; val.assign(h,vector<T>(w,0)); } matrix operator*(matrix b){ matrix a=*this,c(h,b.w); for (int i=0;i<h;i++){ for (int j=0;j<b.w;j++){ for (int k=0;k<h;k++){ c.val[i][j]+=a.val[i][k]*b.val[k][j]; } } } return c; } matrix identity(int n){ matrix ret(n,n); for (int i=0;i<n;i++) ret.val[i][i]=1; return ret; } matrix pow(long long k){ matrix ret(h,w),m=*this; ret=ret.identity(h); while (k>0){ if (k%2==1) ret=ret*m; m=m*m; k/=2; } return ret; } }; int main(){ int n=4; long long a,b,c,d,e,N; cin>>a>>b>>c>>d>>e>>N; matrix ans(n,1); ans.val[0][0]=a; ans.val[1][0]=a+b; ans.val[2][0]=(a+b)+(c*b+d*a+e); ans.val[3][0]=1; matrix p(n); p.val[0][1]=1; p.val[1][2]=1; p.val[2][0]=-d;p.val[2][1]=d-c;p.val[2][2]=1+c;p.val[2][3]=e; p.val[3][3]=1; ans=p.pow(N)*ans; cout<<ans.val[0][0].val()<<endl; }