結果
問題 | No.194 フィボナッチ数列の理解(1) |
ユーザー | nikollson |
提出日時 | 2015-04-28 21:24:20 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 10 ms / 5,000 ms |
コード長 | 2,197 bytes |
コンパイル時間 | 880 ms |
コンパイル使用メモリ | 83,564 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-07-05 05:06:33 |
合計ジャッジ時間 | 2,044 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
コンパイルメッセージ
main.cpp: In function ‘void print(P&)’: main.cpp:95:34: warning: format ‘%d’ expects argument of type ‘int’, but argument 2 has type ‘__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type’ {aka ‘long long int’} [-Wformat=] 95 | printf("%d ",a[i][j]); | ~^ | | | int | %lld main.cpp: In function ‘void print(V&)’: main.cpp:101:26: warning: format ‘%d’ expects argument of type ‘int’, but argument 2 has type ‘__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type’ {aka ‘long long int’} [-Wformat=] 101 | printf("%d ",a[i]); | ~^ | | | int | %lld
ソースコード
#include<cstdio>#include<iostream>#include<vector>#include<string>#include<algorithm>#include<map>#include<set>#include<queue>#include<deque>#define reps(i,f,n) for(int i=f;i<int(n);i++)#define rep(i,n) reps(i,0,n)#define pb push_backusing namespace std;#ifdef __BORLANDC__typedef __int64 ll;#elsetypedef long long ll;#endifconst ll MOD = 1000000007;class P:public vector<vector<ll> >{public:P(int n){rep(i,n){vector<ll> dat(n);this->pb(dat);}}};class V:public vector<ll>{public:V(int n){rep(i,n)this->pb(0);}};P multi(P& a, P& b){int n = a.size();P ret(n);rep(i,n){rep(j,n){int num = 0;rep(k,n){num = (num+a[i][k]*b[k][j])%MOD;}ret[i][j] = num;}}return ret;}V multi(P& a, V& b){int n = a.size();V ret(n);rep(i,n){int num = 0;rep(j,n){num = (num+a[i][j]*b[j])%MOD;}ret[i] = num;}return ret;}P getP(int n){P ret(n+1);rep(i,n-1){rep(j,n){if(j-1==i)ret[i][j]=1;else ret[i][j] = 0;}}rep(i,n)ret[n-1][i]=1;rep(i,n)ret[i][n]=0;rep(i,n+1)ret[n][i]=1;return ret;}void print(P& a){rep(i,a.size()){rep(j,a.size()){printf("%d ",a[i][j]);}puts("");}}void print(V& a){rep(i,a.size()){printf("%d ",a[i]);}puts("");}int main(){ll n,k;cin>>n>>k;vector<ll> a(n);rep(i,n)cin>>a[i];ll ansF = -1;ll ansS = -1;if(n<=30){const int T = 50;vector<P> b;b.pb(getP(n));reps(i,1,T){b.pb(multi(b[i-1], b[i-1]));}V vec(n+1);rep(i,n)vec[i] = a[i];rep(i,n)vec[n] = (vec[n]+a[i])%MOD;ll tk = k-n;ll sc = 1;rep(i,T){if((tk&sc)>0){vec = multi(b[i], vec);}sc*=2;}ansF = vec[n-1];ansS = vec[n];}else{deque<ll> b;rep(i,n)b.pb(a[i]);ll sum = 0;rep(i,n)sum += b[i];ll allsum = sum;rep(i,k-n){ll next = sum;allsum = (allsum+sum)%MOD;ll front = b[0];sum = (sum + next - front + MOD)%MOD;//rep(j,b.size())cout<<b[j]<<" ";cout<<endl;b.pop_front();b.pb(next);}ansF = b[n-1];ansS = allsum;}cout<<ansF<<" "<<ansS<<endl;}/*3 61 1 15 81 2 3 4 5*/