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
AC × 7
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