[AGC002F] Leftmost Ball

給你 \(n\) 種顔色的球，每個球有 \(k\) 個，把這 \(n\times k\) 個球排成一排，把每一種顔色的最左邊出現的球塗成白色(初始球不包含白色)，求有多少種不同的顔色序列，答案對 \(10^9+7\) 取模。

白色的點很特殊，考慮單獨提出來。那麼合法的方案就隻需要每種顔色前都能找到一個白點與之對應，而是怎樣的對應關系其實并不要緊，因為對應關系不會改變序列。是以隻需要保證任意位置，白色點個數大于等于其他顔色的種數。考慮到這種限制關系，我們想到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\) 個（除去第一個和一個白色）。

在第一個空位填這個決策很關鍵，這樣保證了在這一步選不同顔色，在接下來的轉移中一定不會重樣，因為第一個空位被填了。這其中隐喻了一種順序關系。