Submission #124879
Source Code Expand
#include <cstdio>
#include <vector>
#include <algorithm>
#include <iostream>
#include <cassert>
#include <string>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <numeric>
#include <functional>
#include <ctime>
using namespace std;
#define FOR(i,n) for(int i = 0; i < (n); i++)
#define sz(c) ((int)(c).size())
#define ten(x) ((int)1e##x)
#define tenll(x) ((ll)1e##x)
typedef pair<int, int> Pii;
typedef long long ll;
typedef unsigned long long ull;
template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
const ll MOD = 1000000007ll;
typedef vector<ll> vi;
typedef pair<vi, ll> P;
P multi(const P& l, const P& r, const P& resize_base) {
const int K = sz(l.first);
P ret(vi(2*K), 0);
//multi
FOR(i, K) FOR(j, K) ret.first[i + j] += l.first[i] * r.first[j] % MOD;
FOR(i, 2 * K) ret.first[i] %= MOD;
ret.second = accumulate(l.first.begin(), l.first.end(), 0LL) % MOD * r.second % MOD + l.second;
//resize
for (int i = 2 * K - 1; i >= K; i--) {
for (int j = 1; j <= K; j++) {
ret.first[i - j] += ret.first[i] * resize_base.first[K - j] % MOD;
}
}
ret.second += accumulate(ret.first.begin() + K, ret.first.end(), 0LL) % MOD * resize_base.second % MOD;
ret.first.resize(K);
FOR(i, K) ret.first[i] %= MOD;
ret.second %= MOD;
return ret;
}
ll substitute(const P& val, const vi& init) {
ll ret = val.second;
FOR(i, sz(val.first)) ret += init[i] * val.first[i] % MOD;
return ret % MOD;
}
//0-indexed
ll nth(const vi& init, const vi& coef, ll constant, ll n) {
const int K = coef.size();
const int M = K * 2 - 1;
P p(vi(K),0), ret(vi(K),0),base(coef,constant);
p.first[1] = ret.first[0] = 1;
for (; n; n /= 2) {
if (n & 1) ret = multi(ret, p, base);
p = multi(p, p, base);
}
return substitute(ret, init);
}
ll solve(int K, int N,ll constant) {
vector<ll> init(K, 1); // 初項
vector<ll> coef(K, 1); // 係数
ll ret = nth(init, coef, constant, N);
return ret;
}
int main() {
int K, N;
while (cin >> K >> N) {
cout << solve(K, N-1, 0) << endl;
}
return 0;
}
Submission Info
Submission Time |
|
Task |
T - フィボナッチ |
User |
math |
Language |
C++ (G++ 4.6.4) |
Score |
8 |
Code Size |
2137 Byte |
Status |
AC |
Exec Time |
439 ms |
Memory |
932 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 |
439 ms |
924 KB |
01 |
AC |
235 ms |
804 KB |
02 |
AC |
397 ms |
776 KB |
03 |
AC |
84 ms |
932 KB |
04 |
AC |
151 ms |
792 KB |
90 |
AC |
22 ms |
764 KB |
91 |
AC |
23 ms |
800 KB |