弹珠 题解

题意

求 \(n\) 个一样的球放到 \(k\) 个盘子里的方案数（每个盘子至少一个）。

题解

考虑记 \(f(i, j)\) 为结果。

1. 我们可以一次性只加一个球（新放到一个盘子里），也就是可以从 \(f(i - 1, j - 1)\) 转移过来。
2. 也可以用已有的盘子每个盘子放一个球，就是从 \(f(i - j, j)\) 转移过来。

为什么不可以从 \(f(i - k, j)\) 或 \(f(i - k, j - k)\) 而 \(1 \le k \lt j\) 转移过来呢？

因为重复两次上述操作会导致重复（再说了时间复杂度也不允许……）

时间复杂度 \(\mathcal{O} (nk)\)

namespace zqh {
const int N = 5005;

int n, k;
int dp[N][N];

void init() {
    cin >> n >> k;
}

void solve() {
    dp[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <=  min(i, k); j++) {
            dp[i][j] = (dp[i - 1][j - 1] + dp[i - j][j]) % mod;
        }
    }
    cout << dp[n][k];
}

void main() {
    init();
    solve();
}
}  // namespace zqh