#252237 (C++14) No.503 配列コレクション

• 問題: No.503 配列コレクション
• ユーザー: square1001
• 提出日時: 2018-04-17 21:26:19
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: WA
• 実行時間: -
• コード長: 725 bytes
• コンパイル時間: 488 ms
• コンパイル使用メモリ: 64,580 KB
• 実行使用メモリ: 19,716 KB
• 最終ジャッジ日時: 2023-09-09 11:08:36
• 合計ジャッジ時間: 1,931 ms
• ジャッジサーバーID （参考情報）: judge11 / judge15

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 7,468 KB
testcase_01	AC	2 ms; 4,380 KB
testcase_02	AC	2 ms; 7,436 KB
testcase_03	AC	2 ms; 7,492 KB
testcase_04	WA	-
testcase_05	AC	2 ms; 7,488 KB
testcase_06	AC	2 ms; 7,524 KB
testcase_07	AC	2 ms; 7,576 KB
testcase_08	AC	2 ms; 7,416 KB
testcase_09	AC	2 ms; 7,468 KB
testcase_10	AC	3 ms; 7,456 KB
testcase_11	AC	3 ms; 7,484 KB
testcase_12	AC	2 ms; 7,464 KB
testcase_13	AC	2 ms; 7,504 KB
testcase_14	AC	9 ms; 10,032 KB
testcase_15	AC	2 ms; 7,504 KB
testcase_16	AC	2 ms; 4,376 KB
testcase_17	AC	1 ms; 4,376 KB
testcase_18	WA	-
testcase_19	WA	-
testcase_20	WA	-
testcase_21	WA	-
testcase_22	AC	2 ms; 7,436 KB
testcase_23	AC	1 ms; 4,380 KB
testcase_24	WA	-

ソースコード

#include <iostream>
using namespace std;
int N, K, D, fact[2000009], inv[2000009], finv[2000009], mod = 1000000007;
int main() {
	cin >> N >> K >> D;
	int P = N / (K - 1), Q = N % (K - 1);
	if (Q == 0) Q += K - 1, P++;
	if (D == 1) cout << Q << endl;
	else {
		fact[0] = 1, finv[0] = 1;
		for (int i = 1; i <= P + Q; i++) {
			fact[i] = 1LL * fact[i - 1] * i % mod;
			inv[i] = (i == 1 ? 1 : 1LL * inv[mod % i] * (mod - mod / i) % mod);
			finv[i] = 1LL * finv[i - 1] * inv[i] % mod;
		}
		int ret = 0, pw = 1;
		for (int i = 0; i <= P; i++) {
			ret = (ret + 1LL * pw * fact[P + Q - i - 2] % mod * finv[Q - 2] % mod * finv[P - i]) % mod;
			pw = 1LL * pw * D % mod;
		}
		cout << 1LL * ret * Q % mod << endl;
	}
	return 0;
}