题面

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

解法

设\(f(i,\;j)\)表示在这些\((n \times k个)\)位置上已经放了i个白球，j种其他颜色的球。(i<j)

\(f(i,\;j) = f(i-1,\; j)+f(i ,\;j-1)\times (n-j+1)\times \dbinom{k-2}{n*k-i-(j-1)*(k-1)-1}\)

第一部分: 加一个白球,我们规定了白球放首位以避免重复计算

第二部分: 加入一种新颜色: 还有(n-j+1)种颜色,选出一种后,需要放(k-2)个,又因为共有i+(j-1)*(k-1)-1个空格,所以是\(f(i ,\;j-1)\times (n-j+1)\times \dbinom{k-2}{n*k-i-(j-1)*(k-1)-1}\)

证毕!

代码

#include
    
     using namespace std ;#define int unsigned long longconst int mxn = 8000005 ;const int Mod = 1e9+7 ;int frac[mxn], inv[mxn];int f[2005][2005], n, k;int power(int a, int b){    int res=1, car=a;     while(b){        if(b&1) (res*=car)%=Mod;        (car*=car)%=Mod;        b>>=1;    }    return res;}void init(){    frac[0]=1 ;    for(int i=1;i
     
      0;--i) inv[i]=(inv[i+1]*(i+1))%Mod ;    inv[0] = 1 ;}int C(int n, int k){    return ((frac[n]*inv[k]%Mod)*inv[n-k])%Mod ;}signed main(){    init() ;    cin>>n>>k;    if(k==1) return puts("1"),0 ;    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]+(j?((((f[i][j-1]*(n-j+1))%Mod)*C(n*k-i-(j-1)*(k-1)-1, k-2))%Mod):(0)))%=Mod ;    cout<
      
       <