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
#include <bits/stdc++.h>
#define ll long long
const int md=1e9+7;
const int maxm=4001000;
const int maxn=2001;
int read(){
int x=0,flag=1;char ch=getchar();
while(!isdigit(ch)&&ch!='-') ch=getchar();
if (ch=='-') flag=-1,ch=getchar();
while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch-'0'),ch=getchar();
return x*flag;
}
ll fac[maxm],inv[maxm];
ll ksm(ll a,ll b){
ll res=1;
while(b){
if (b&1) res=res*a%md;
a=a*a%md;b>>=1;
}
return res;
}
void init(int n){
fac[0]=1;
for (int i=1;i<=n;++i)
fac[i]=fac[i-1]*i%md;
inv[n]=ksm(fac[n],md-2);
for (int i=n;i;--i)
inv[i-1]=inv[i]*i%md;
}
ll c(int n,int m){
return fac[n]*inv[m]%md*inv[n-m]%md;
}
int n,k,f[maxn][maxn];
int main(){
n=read(),k=read();
if (k==1) return puts("1"),0;
init(n*k);
f[0][0]=1;
for (int i=1;i<=n;++i){
for (int j=0;j<=i;++j){
f[i][j]=f[i-1][j];
if (!j) continue;
(f[i][j]+=1ll*f[i][j-1]*(n-j+1)%md*
c(n-i+(n-j+1)*(k-1)-1,k-2)%md)%=md;
}
}
printf("%d\n",f[n][n]);
}