Submission #227817
Source Code Expand
#include<bits/stdc++.h> #define rep(i,n) for(int i=0;i<(int)n;i++) #define all(c) (c).begin(),(c).end() #define mp make_pair #define pb push_back #define each(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++) #define dbg(x) cerr<<__LINE__<<": "<<#x<<" = "<<(x)<<endl using namespace std; typedef long long ll; typedef vector<int> vi; typedef pair<int,int> pi; const int inf = (int)1e9; const double INF = 1e12, EPS = 1e-9; typedef deque<int> di; const int mod = inf + 7; int K, N; inline void advance(di &co){ int n = co.size(); co.push_front(0); rep(i, n) (co[i] += co[n]) %= mod; co.pop_back(); } inline void dbl(di &v){ int n = v.size(); di prev = v; v.clear(); v.resize(n * 2); rep(i, n) rep(j, n) (v[i + j] += (ll)prev[i] * prev[j] % mod) %= mod; di co(K, 1); for(int i = n; i < 2 * n; i++){ rep(j, n) (v[j] += (ll)v[i] * co[j] % mod) %= mod; advance(co); } rep(i, n) v.pop_back(); } int main(){ cin >> K >> N; N--; di v(K, 0); v[1] = 1; int p; for(p = 31; !(N >> p & 1); p--); p--; for(; p >= 0; p--){ dbl(v); if(N >> p & 1) advance(v); } ll ans = 0; rep(i, K) ans += v[i]; cout << ans % mod << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | T - フィボナッチ |
User | nadeko |
Language | C++ (G++ 4.6.4) |
Score | 8 |
Code Size | 1263 Byte |
Status | AC |
Exec Time | 929 ms |
Memory | 1208 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 | 929 ms | 1132 KB |
01 | AC | 527 ms | 1168 KB |
02 | AC | 918 ms | 1084 KB |
03 | AC | 166 ms | 996 KB |
04 | AC | 275 ms | 1208 KB |
90 | AC | 29 ms | 976 KB |
91 | AC | 28 ms | 1068 KB |