原文链接https://www.cnblogs.com/zhouzhendong/p/AGC002F.html

题目传送门 - AGC002F

题意

　　给定 $n,k$ ，表示有 $n\times k$ 个球，其中，颜色为 $1,2,\cdots, n$ 的球各有 $k$ 个。

　　将这些球任意排列成一排，对于每一种颜色，将这种颜色的球的最左边的那个涂成颜色 $0$ 。

　　问最终可以得到多少种不同的排列。

　　$1\leq n,k\leq 2000,{\rm Mod} = 10^9 +7$

题解

　　首先当 $k=1$ 时答案显然是 $1$ ，先判掉。

　　然后我们求最终序列中，颜色为 $1,\cdots ,n $ 的球的最左出现位置递增 的方案总数。这样最后只需要把答案乘上 $n!$ 就可以了。

　　考虑如何求这个东西。我们考虑动态规划，假装我们一个一个地把颜色涂到序列上。

　　令 $dp[i][j]$ 表示已经涂完前 $i$ 种颜色，并已经涂了 $j$ 个颜色 $0$ 的方案总数。

　　由于每种颜色的第一个位置都会被涂成 $0$ ，所以当前涂了颜色 $1,\cdots ,i$ 的格子总数为 $(k-1)\times i$ ，再加上被涂成 $0$ 的格子，现在总共已经确定了 $(k-1)\times i+j$ 个格子。而且，显然有 $i\leq j$ 。于是我们来考虑 DP 转移。

　　考虑 $dp[i][j]$ 对于其他 DP 值的贡献：

　　　　1.　下一个格子选择涂颜色 $0$ ： $dp[i][j+1]+=dp[i][j]$

　　　　2.　让下一个格子成为最终序列中颜色 $i+1$ 第一次出现的地方。显然，我们又占用了 $1$ 个位置；而且除掉变成 $0$ 的和第一个，颜色 $i+1$ 还有 $k-2$ 个没有被填入。相当于在 $k(n-i)-(j-i)-1$ 个格子里面选择 $k-2$ 个，于是转移就是 ： $dp[i+1][j]+=\binom{k(n-i)-(j-i)-1}{k-2} dp[i][j]$

　　然后就 OK 啦。到这里，您就可以体会到为什么一开始我们要把 $k=1$ 的判掉了吧。

代码

#include <bits/stdc++.h>

using namespace std;

const int N=2005,mod=1e9+7;

int n,k;

int Fac[N*N],Inv[N*N],dp[N][N];

int Pow(int x,int y){

	int ans=1;

	for (;y;y>>=1,x=1LL*x*x%mod)

		if (y&1)

			ans=1LL*ans*x%mod;

	return ans;

}

int C(int n,int m){

	if (m<0||m>n)

		return 0;

	return 1LL*Fac[n]*Inv[m]%mod*Inv[n-m]%mod;

}

int main(){

	scanf("%d%d",&n,&k);

	if (k==1){

		puts("1");

		return 0;

	}

	for (int i=Fac[0]=1;i<=n*k;i++)

		Fac[i]=1LL*Fac[i-1]*i%mod;

	Inv[n*k]=Pow(Fac[n*k],mod-2);

	for (int i=n*k-1;i>=0;i--)

		Inv[i]=1LL*Inv[i+1]*(i+1)%mod;

	dp[0][0]=1;

	for (int i=0;i<=n;i++)

		for (int j=i;j<=n;j++){

			dp[i][j+1]=(dp[i][j+1]+dp[i][j])%mod;

			dp[i+1][j]=(1LL*dp[i][j]*C(k*(n-i)-(j-i)-1,k-2)+dp[i+1][j])%mod;

		}

	printf("%lld",1LL*dp[n][n]*Fac[n]%mod);

	return 0;

}