Description

把一共 $n$ 种颜色,每种颜色 $k$ 个的球排成一行,然后把每种颜色的第一个球涂成白色。求最终颜色序列的种数。

Idea

我们可以看成 $n+1$ 个颜色,其中白球有 $n$ 个,剩下每种颜色 $k-1$ 个。题目的限制条件为,颜色序列的每个前缀中,白球数量不得小于其他球的数量。我们可以利用这个性质从后往前 $DP$。

设 $f_{i,j}$ 表示放下 $i$ 个白球,$j$ 种其他颜色球的方案数。

  • 新增一个白球,直接由 $f_{i-1,j}$ 转移过来;
  • 新增一种其他的颜色,也就是加入了 $k-1$ 个新的小球。为了避免算重,$k-1$ 个球中的第一个必须放在最靠前的空位中,剩下 $k-2$ 个插入剩下的小球中,也就是 $n-i+(n-j+1)*(k-1)-1$。

Code