結果
問題 |
No.3228 Very Large Fibonacci Sum
|
ユーザー |
|
提出日時 | 2025-08-09 04:21:02 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,241 bytes |
コンパイル時間 | 2,547 ms |
コンパイル使用メモリ | 171,280 KB |
実行使用メモリ | 7,716 KB |
最終ジャッジ日時 | 2025-08-09 04:21:06 |
合計ジャッジ時間 | 2,725 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 WA * 2 |
other | AC * 4 WA * 19 |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll,ll> P; #define REP(i,n) for(ll i=0;i<ll(n);i++) const ll MOD=1000000007; typedef vector<ll> vl; typedef vector<vector<ll> > vvl; vvl mul(vvl X, vvl Y) { vvl Z(X.size(),vl(Y[0].size())); REP(i,X.size()){ REP(k,Y.size()){ REP(j,Y[0].size()){ Z[i][j]=(Z[i][j]+X[i][k]*Y[k][j])%MOD; } } } return Z; } vvl pow(vvl A,ll n){ vvl B(A.size(),vl(A[0].size())); REP(i,B.size()) B[i][i]=1; while(n>0){ if (n%2==1) B=mul(B,A); A=mul(A,A); n/=2; } return B; } ll modpow(ll x,ll n){ ll res=1; while(n!=0LL){ if(n%2!=0LL) res=(res*x)%MOD; x=(x*x)%MOD; n/=2; } return res; } int main(void){ cin.tie(nullptr); ios_base::sync_with_stdio(false); ll i,j; ll a,b,c,d,e,N; cin >> a >> b >> c >> d >> e >> N; vvl A(4,vl(4,0)); A[0][0]=c+1; A[0][1]=d-c; A[0][2]=-d; A[0][3]=e; A[1][0]=1; A[2][1]=1; A[3][3]=1; if(N==0){ cout << (a+MOD)%MOD << endl; return 0; } if(N==1){ cout << (a+b+MOD)%MOD << endl; return 0; } A=pow(A,N-2); ll k=2*a+b+b*c+a*d+e; ll x=(A[0][0]*k+A[0][1]*(a+b)+A[0][2]*a+A[0][3])%MOD; cout << (x+MOD)%MOD << endl; return 0; }