[AGC002F] Leftmost Ball

Description

给你 \(n\) 种颜色的球,每个球有 \(k\) 个,把这 \(n\times k\) 个球排成一排,把每一种颜色的最左边出现的球涂成白色(初始球不包含白色),求有多少种不同的颜色序列,答案对 \(10^9+7\) 取模。

Solution

白色的点很特殊,考虑单独提出来。那么合法的方案就只需要每种颜色前都能找到一个白点与之对应,而是怎样的对应关系其实并不要紧,因为对应关系不会改变序列。所以只需要保证任意位置,白色点个数大于等于其他颜色的种数。考虑到这种限制关系,我们想到dp。

\(dp[i][j]\) 表示用了 \(i\) 个白球和 \(j\) 种其他颜色的所有球的方案数,要保证 \(i\geq j\)。就有转移

\[dp[i][j]=dp[i-1][j](i>j)+(n-j+1)\binom{nk-(j-1)(k-1)-i-1}{k-2}dp[i][j-1] \]

这是分别考虑在从左到右第一个空位填白色还是其他颜色。白色的话就只有唯一的方案;其他颜色的话,首先考虑是什么颜色,只剩下 \(n-j+1\) 种(因为是从 \(dp[i][j-1]\))转移,然后第一个空位就必须填这种颜色,就剩下 \(nk-(j-1)(k-1)-i-1\) 个空位,填 \(k-2\) 个(除去第一个和一个白色)。

在第一个空位填这个决策很关键,这样保证了在这一步选不同颜色,在接下来的转移中一定不会重样,因为第一个空位被填了。这其中隐喻了一种顺序关系。

[AGC002F] Leftmost Ball

上一篇:整数反转


下一篇:Noip模拟42 2021.8.17