题解 AT2000 【Leftmost Ball】

墨尔 · 2019-02-20 15:06:35 · 题解

考虑最后可能的序列，有 k 个白球，n 种其他颜色的球各 k-1 个。显然只有当任意前缀中白球的个数均大等于其他颜色的种类数时合法。

设 f[i][j] 表示已经放了 i 个白球和 j 种其他的颜色的可行方案数。(j \leq i)

转移时考虑合法序列的从左到右的第一个空位放什么。

放白球：即从 f[i-1][j] 转移，因为是在第一个空位放置白球，转移过来必定合法。

放新的颜色的球：即从 f[i][j-1] 转移，先在剩下 n-j+1 种没有放置过的颜色中选择一个作为这次放置的颜色，放置在第一个空位（按转移规则，已经放置的 i 个白球一定都在当前第一个空位的前面，因此必定合法）。放完后还剩 k-2 的这个颜色的球没有放，显然只需要在剩下的后面 n\times k-i-(j-1)\times (k-1)-1 个空位里找任意 k-2 个空位放就好，有 C_{n\times k-i-(j-1)\times (k-1)-1}^{k-2} 种方案

综上，转移方程为 f[i][j]=f[i-1][j]+f[i][j-1]\times (n-j+1)\times C_{n\times k-i-(j-1)\times (k-1)-1}^{k-2}

初始状态为 f[i][0]=1，即前 i 个位置都放白球，答案为f[n][n]。

再注意一下 k=1 的特判即可。