結果
問題 | No.503 配列コレクション |
ユーザー |
![]() |
提出日時 | 2017-04-07 22:59:08 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 304 ms / 2,000 ms |
コード長 | 1,602 bytes |
コンパイル時間 | 1,556 ms |
コンパイル使用メモリ | 162,756 KB |
実行使用メモリ | 42,544 KB |
最終ジャッジ日時 | 2024-07-16 02:51:55 |
合計ジャッジ時間 | 9,997 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 25 |
ソースコード
#include<bits/stdc++.h>#include<unordered_set>#include<unordered_map>using namespace std;#define MAX 1000002int n;int k;int d;#define MOD 1000000007long long int p[MAX];class Combination{long long int ppow(long long int i, long long int j){long long int res = 1LL;while (j){if ((j & 1LL)){res *= i;if (res >= MOD){res %= MOD;}}j >>= 1;i *= i;if (i >= MOD){i %= MOD;}}return res;}public:vector<long long int> k;vector<long long int> r;void resize(int N){k.resize(N + 2);r.resize(N + 2);k[0] = 1;for (int i = 1; i < k.size(); i++){k[i] = k[i - 1];k[i] *= i;if (k[i] >= MOD)k[i] %= MOD;}for (int i = 0; i < r.size(); i++){r[i] = ppow(k[i], MOD - 2);}}long long int C(int a, int b){if (a < b)return 0;long long int up = k[a];long long int dw = r[b] * r[a - b];dw %= MOD;up *= dw;up %= MOD;return up;}long long int H(int a, int b){if (a == 0)return 1;if (b == 0)return 1;return C(a + b - 1, b);}} c;int main(){c.resize(MAX * 2);cin >> n >> k >> d;p[0] = 1;for (int i = 1; i < MAX; i++){p[i] = p[i - 1];p[i] *= d;p[i] %= MOD;}int op = 0;while (n >= k){n -= k - 1;op++;}if (d == 1){cout << n << endl;return 0;}long long int ans = 0;for (int i = 1; i <= 1; i++){for (int j = 0; j <= op; j++){if (n - 1 == 0){j = op;}long long int w = c.H(n - 1, op-j);w *= p[j];w %= MOD;w *= n;w %= MOD;ans += w;ans %= MOD;}}printf("%lld\n", ans);return 0;}