結果
問題 | No.503 配列コレクション |
ユーザー |
|
提出日時 | 2017-04-08 02:40:52 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 562 ms / 2,000 ms |
コード長 | 1,218 bytes |
コンパイル時間 | 391 ms |
コンパイル使用メモリ | 51,712 KB |
実行使用メモリ | 57,600 KB |
最終ジャッジ日時 | 2024-07-16 03:50:48 |
合計ジャッジ時間 | 2,158 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 25 |
ソースコード
#include <cstdio>#include <vector>#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))using ll = long long;using namespace std;template <typename X, typename T> auto vectors(X x, T a) { return vector<T>(x, a); }template <typename X, typename Y, typename Z, typename... Zs> auto vectors(X x, Y y, Z z, Zs... zs) { auto cont = vectors(y, z, zs...); return vector<decltype(cont)>(x, cont); }const int mod = 1e9+7;int solve(int n, int k, int d) {int r = 0; while (n >= k) { n -= k-1; r += 1; }if (d == 1) return n;auto dp = vectors(n+1, r+1, 0);auto cnt = vectors(n+1, r+1, 0);dp[0][0] = 1;cnt[0][0] = 1;repeat (x,r) {dp[0][x+1] = dp[0][x] *(ll) d % mod;cnt[0][x+1] = 1;}repeat (y,n-1) {repeat (x,r+1) {ll acc = 0;ll cntacc = 0;repeat (z,x+1) {acc += dp[y][x-z] + cnt[y][x-z] *(ll) dp[0][z] % mod;cntacc += cnt[y][x-z];}dp[y+1][x] = acc % mod;cnt[y+1][x] = cntacc % mod;}}return dp[n-1][r];}int main() {int n, k, d; scanf("%d%d%d", &n, &k, &d);printf("%d\n", solve(n, k, d));return 0;}