結果
問題 | No.194 フィボナッチ数列の理解(1) |
ユーザー | takayuta1999 |
提出日時 | 2015-04-26 23:22:18 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 39 ms / 5,000 ms |
コード長 | 2,846 bytes |
コンパイル時間 | 340 ms |
コンパイル使用メモリ | 43,064 KB |
実行使用メモリ | 7,856 KB |
最終ジャッジ日時 | 2024-07-05 01:39:15 |
合計ジャッジ時間 | 1,975 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:111:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 111 | scanf("%d %lld",&n,&k); | ~~~~~^~~~~~~~~~~~~~~~~ main.cpp:112:35: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 112 | for(int i=0;i<n;i++) scanf("%d",&A[i]); | ~~~~~^~~~~~~~~~~~
ソースコード
#include <cstdio> #include <cstdlib> #include <algorithm> #include <vector> #include <cstring> #define SIZE 70 #define MOD 1000000007 #define MX 1000005 using namespace std; typedef long long int ll; struct Matrix { int n; ll A[SIZE][SIZE]; ll mpow(ll x,ll t) { if(t==0) return 1; ll ret=mpow(x,t/2); ret=ret*ret%MOD; if(t%2==1) ret=ret*x%MOD; return ret; } ll inv(ll x) { return mpow(x,MOD-2);//if MOD is a prime number } void init(int m) { n=m; for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { A[i][j]=0; } } } void add(int a,int b,ll x) { A[a][b]+=x; if(A[a][b]>=MOD) A[a][b]-=MOD; } }; Matrix SUM_mat,PR_mat; void product(Matrix&A,Matrix&B) { int n=A.n; PR_mat.init(n); for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { PR_mat.A[i][j]=0; for(int k=0;k<n;k++) { PR_mat.A[i][j]+=A.A[i][k]*B.A[k][j]%MOD; if(PR_mat.A[i][j]>=MOD) PR_mat.A[i][j]-=MOD; } } } } void sumsum(Matrix&A,Matrix&B) { int n=A.n; SUM_mat.init(n); for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { SUM_mat.A[i][j]=0; for(int k=0;k<n;k++) { SUM_mat.A[i][j]+=(A.A[i][k]+B.A[k][j])%MOD; if(SUM_mat.A[i][j]>=MOD) SUM_mat.A[i][j]-=MOD; } } } } Matrix mt[SIZE]; void mpow(Matrix&M,ll t,int dep) { if(t==1) { mt[dep]=M; return; } mpow(M,t/2,dep+1); product(mt[dep+1],mt[dep+1]); mt[dep]=PR_mat; if(t%2==1) { product(mt[dep],M); mt[dep]=PR_mat; } } Matrix mat; int A[MX],F[MX]; int n; ll k; int get(int i,int j) { if(i==n-1) return 1; return i+1==j?1:0; } int main() { scanf("%d %lld",&n,&k); for(int i=0;i<n;i++) scanf("%d",&A[i]); if(k<MX) { int now=0,sum=0; for(int i=0;i<n;i++) { now+=A[i]; sum+=A[i]; sum%=MOD; now%=MOD; F[i]=A[i]; } for(int i=n;i<k;i++) { F[i]=now; sum+=F[i]; sum%=MOD; if(i+1==k) break; now+=MOD-F[i-n]; now%=MOD; now+=F[i]; now%=MOD; } printf("%d %d\n",now,sum); } else { mat.init(n*2); for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { mat.add(i,j,get(i,j)); } } for(int i=n;i<n*2;i++) { for(int j=0;j<n*2;j++) { mat.add(i,j,i%n==j%n?1:0); } } mpow(mat,k-1,0); Matrix am,sm; am.init(n); for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { ll vl=0; for(int k=0;k<2*n;k++) { vl+=mt[0].A[i][k]*(k%n==j?1:0)%MOD; vl%=MOD; } am.add(i,j,vl); } } ll r1=0; for(int i=0;i<n;i++) { r1+=am.A[0][i]*(ll) A[i]%MOD; r1%=MOD; } sm.init(n); for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { ll vl=0; for(int k=0;k<2*n;k++) { vl+=mt[0].A[i+n][k]*(k%n==j?1:0)%MOD; vl%=MOD; } sm.add(i,j,vl); } } ll r2=0; for(int i=0;i<n;i++) { r2+=sm.A[0][i]*(ll) A[i]%MOD; r2%=MOD; } printf("%lld %lld\n",r1,(r1+r2+MOD-A[0])%MOD); } return 0; }