Submission #99009
Source Code Expand
#include <algorithm> #include <cmath> #include <climits> #include <complex> #include <cstdio> #include <cstdlib> #include <iostream> #include <map> #include <queue> #include <set> #include <sstream> #include <string> #include <stack> #include <utility> #include <vector> using namespace std; typedef long long LL; typedef pair<int,int> PII; #define MP make_pair #define REP(i,n) for(int i=0;i<(int)n;i++) #define EACH(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++) #define ALL(c) (c).begin(),(c).end() LL MOD = 1000000007; const int MAXN = 1001; LL A[MAXN]; LL CO[MAXN]; LL temp[2*MAXN]; LL m2[MAXN][MAXN]; //m :Aの長さ //n レベル LL solve(LL n ,int m) { if(m==1) { LL ret = A[0]; LL mul = CO[0]; for(;n>0;n>>=1) { if((n&1)==1) { ret = (ret*mul)%MOD; } mul = (mul*mul) % MOD; } return ret; } for(int j=0; j<m; j++) m2[0][j] = CO[j]; for(int i=1; i<m-1; i++) { for(int j=0; j<m; j++) { LL x = m2[i-1][m-1] * CO[j]; if(j-1>=0) x += m2[i-1][j-1]; m2[i][j] = x% MOD; } } LL ret[MAXN]; for(int i=0; i<m; i++) ret[i] = 0; ret[0]=1; for(int l=32; l>=0; l--) { if((n>>l)&1) { // cout<<l<<endl; for(int i=0; i<m; i++) temp[i] = ret[m-1] * CO[i]; for(int i=1; i<m; i++) temp[i] += ret[i-1]; for(int i=0; i<m; i++) ret[i] = temp[i] % MOD; /* cout<<"hjoge"<<endl; for(int i=0; i<m; i++) cout<<ret[i]<<" "; cout<<endl;*/ } if(l>0) { for(int i=0; i<2*m; i++) temp[i] = 0; for(int i=0; i<m; i++) { for(int j=0; j<m; j++) { temp[i+j] += ret[i] * ret[j] % MOD; } } for(int i=0; i<2*m-2; i++) temp[i] %= MOD; /* cout<<"temp"<<endl; for(int i=0; i<2*m-1; i++) cout<<temp[i]<<" "; cout<<endl;*/ for(int i=0; i<m ;i++) { LL s = temp[i]; for(int j=m; j<2*m-1; j++) s += temp[j] * m2[j-m][i] % MOD; ret[i] =s % MOD; } /* cout<<l<<endl; for(int i=0; i<m; i++) cout<<ret[i] <<" "; cout<<endl;*/ } } LL s =0; for(int i=0; i<m; i++) { s += ret[i] * A[i] % MOD; // cout<<ret[i]<<" "; } // cout<<endl; return s % MOD; } int main() { LL K,N; cin>>K>>N; for(int i=0; i<K; i++) A[i] = 1; for(int i=0; i<K; i++) CO[i] = 1; LL ans = solve(N-1,K); cout<<ans<<endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | T - フィボナッチ |
User | tokoharu |
Language | C++ (G++ 4.6.4) |
Score | 8 |
Code Size | 2495 Byte |
Status | AC |
Exec Time | 1645 ms |
Memory | 8876 KB |
Judge Result
Set Name | All | ||
---|---|---|---|
Score / Max Score | 8 / 8 | ||
Status |
|
Set Name | Test Cases |
---|---|
All | 00, 01, 02, 03, 04, 90, 91 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00 | AC | 1630 ms | 8744 KB |
01 | AC | 1005 ms | 7128 KB |
02 | AC | 1645 ms | 8876 KB |
03 | AC | 220 ms | 3620 KB |
04 | AC | 1610 ms | 8680 KB |
90 | AC | 30 ms | 1036 KB |
91 | AC | 23 ms | 1040 KB |