結果

問題 No.3457 Fibo-shrink
コンテスト
ユーザー startcpp
提出日時 2026-02-28 14:35:14
言語 C++14
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++14 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 29 ms / 2,000 ms
コード長 808 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 811 ms
コンパイル使用メモリ 82,636 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2026-02-28 14:35:18
合計ジャッジ時間 1,753 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <vector>
#define rep(i, n) for(i = 0; i < n; i++)
using namespace std;

int powmod(int a, int n, int mod) {
	if (n == 0) return 1 % mod;
	if (n % 2 == 0) return powmod(a * a % mod, n / 2, mod);
	return powmod(a, n - 1, mod) * a % mod;
}

int main() {
	int mod = 10007;
	int k, s, n;
	cin >> k >> s >> n;

	int i, j;
	vector<int> fib(n + 1);
	vector<int> fibInv(n + 1);
	fib[0] = 1; fib[1] = 1;
	fibInv[0] = fibInv[1] = 1;
	for (i = 2; i <= n; i++) {
		fib[i] = (fib[i - 1] + fib[i - 2]) % mod;
		fibInv[i] = powmod(fib[i], mod - 2, mod);
	}

	vector<int> a(n + 1);
	a[0] = 0;
	a[1] = s;
	for (i = 2; i <= n; i++) {
		for (j = 1; j <= k + 1; j++) {
			if (i - j <= 0) continue;
			a[i] += a[i - j] * fibInv[j - 1] % mod;
			a[i] %= mod;
		}
	}

	cout << a[n] << endl;
	return 0;
}
0