Submission #99341
Source Code Expand
#include <algorithm> #include <bitset> #include <cassert> #include <cctype> #include <climits> #include <cmath> #include <complex> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #include <deque> #include <fstream> #include <iomanip> #include <iostream> #include <list> #include <map> #include <numeric> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <valarray> #include <vector> #define EPS 1e-9 #define INF 1070000000LL #define MOD 1000000007LL #define fir first #define foreach(it,X) for(__typeof((X).begin()) it=(X).begin();it!=(X).end();it++) #define ite iterator #define mp make_pair #define mt make_tuple #define rep(i,n) rep2(i,0,n) #define rep2(i,m,n) for(int i=m;i<(n);i++) #define pb push_back #define sec second #define sz(x) ((int)(x).size()) using namespace std; struct timer{ time_t start; timer(){start=clock();} ~timer(){cerr<<1.*(clock()-start)/CLOCKS_PER_SEC<<" secs"<<endl;} }; typedef istringstream iss; typedef long long ll; typedef pair<ll,ll> pi; typedef stringstream sst; typedef vector<ll> vi; ll K,N; vi mult(vi v,vi w){ vi res(2*K,0); rep(i,K)rep(j,K){ res[i+j]+=v[i]*w[j]%MOD; } for(int i=2*K-1;i>=K;i--)rep2(j,i-K,i){ res[j]=(res[j]+res[i])%MOD; } return res; } vi f(ll N){ vi res(2*K,0); if(N<K){ res[N]=1; return res; } vi v=f(N/2); res=mult(v,v); if(N&1)res=mult(res,f(1)); return res; } int main(){ cin.tie(0); ios_base::sync_with_stdio(0); cin>>K>>N; N--; vi res=f(N); ll ans=0; rep(i,K)ans+=res[i]; cout<<ans%MOD<<endl; }
Submission Info
Submission Time | |
---|---|
Task | T - フィボナッチ |
User | evima |
Language | C++ (G++ 4.6.4) |
Score | 8 |
Code Size | 1661 Byte |
Status | AC |
Exec Time | 318 ms |
Memory | 1300 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 | 318 ms | 1300 KB |
01 | AC | 166 ms | 1112 KB |
02 | AC | 268 ms | 1244 KB |
03 | AC | 75 ms | 980 KB |
04 | AC | 26 ms | 864 KB |
90 | AC | 24 ms | 920 KB |
91 | AC | 24 ms | 868 KB |