Submission #99353
Source Code Expand
#include <string> #include <vector> #include <cmath> #include <ctime> #include <iostream> #include <cstdio> #include <set> #include <map> #include <queue> #include <sstream> #include <algorithm> #include <numeric> #include <cstring> using namespace std; typedef long long ll; const ll MOD = 1000000007ll; ll nth(const vector<ll> init, const vector<ll> coef, ll constant, ll n){ const int K = coef.size(); const int M = K * 2 - 1; vector<int> binary; for(int m=n;m;m/=2)binary.push_back(m % 2); reverse(binary.begin(), binary.end()); vector<ll> cs(M, 0); cs[0] = 1; ll ks = 0; for(int i=0;i<binary.size();i++){ { // *2 vector<ll> next(M, 0); ll sum = 1; for(int a=0;a<K;a++){ for(int b=0;b<K;b++){ next[a+b] = (next[a+b] + cs[a] * cs[b] % MOD) % MOD; } sum = (sum + cs[a]) % MOD; } cs = next; for(int j=M-1;j>=K;j--){ for(int k=1;k<=K;k++)cs[j-k] = (cs[j-k] + coef[K-k] * cs[j] % MOD) % MOD; cs[j] = 0; } ks = (ks * sum) % MOD; } if(binary[i]){ // +1 vector<ll> next(M, 0); for(int i=0;i<K;i++)next[i+1] = cs[i]; cs = next; for(int k=1;k<=K;k++)cs[K-k] = (cs[K-k] + coef[K-k] * cs[K] % MOD) % MOD; cs[K] = 0; } } ll ret = 0; for(int i=0;i<K;i++)ret = (ret + cs[i] * init[i] % MOD) % MOD; ret = (ret + ks * constant % MOD) % MOD; return ret; } ll solve(int K, int N){ const vector<ll> init(K, 1); // 初項 const vector<ll> coef(K, 1); // 係数 const ll constant = 0; // 定数係数 ll ret = nth(init, coef, constant, N); return ret; } int main(){ int K, N; cin >> K >> N; N--; cout << solve(K, N) << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | T - フィボナッチ |
User | kroton |
Language | C++ (G++ 4.6.4) |
Score | 8 |
Code Size | 1729 Byte |
Status | AC |
Exec Time | 556 ms |
Memory | 1020 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 | 556 ms | 1020 KB |
01 | AC | 311 ms | 864 KB |
02 | AC | 529 ms | 860 KB |
03 | AC | 104 ms | 920 KB |
04 | AC | 175 ms | 920 KB |
90 | AC | 22 ms | 868 KB |
91 | AC | 25 ms | 848 KB |