Description
有n种颜色(不包括白色)的球各k个,要求你将它们排成一列,然后将每种颜色最靠左的球染白。求最终序列的方案数。
1≤n,k≤2000。
Solution
数数难,难如屑食汉(意味不明)
我们不妨将白球当做一种颜色来处理。那么我们发现只要满足最后恰有n个白球(这样其他球各有k−1个),并且第i个白球之前出现了至多i−1种非白颜色,那么序列就是合法的。
然后这样如果直接顺次DP的话,由于需要记所有球还有多少没用所以复杂度上天……我们考虑转换一下思路,在考虑一个颜色的时候就把该颜色所有球全安排上。那么设计状态fi,j表示已经放了i个白球,然后用了j种颜色的情况(显然要求i≤j)。那么转移的时候,我们限制不管放白球还是放非白球一定要放置在最靠左的空位(否则会记重),那么显然可以直接放一个白球,也可以放非白球,非白球的转移就是考虑放哪种球然后除了最靠左的球以外的k−2个放哪就行了。转移方程如下: f_{i, j}=f_{i - 1, j} + (n - j + 1)\binom{nk - i - (j - 1) * (k - 1) - 1}{k - 2}f_{i, j - 1}
Description
1 |
|