貌似哪里讲过这题。。总之当时掉线了（理解能力又差水平又低选手的日常）。。
看看题目，应该是DP。
尝试了几次换状态，毫无思路。那我们就来继续挖掘性质吧。。。为了更直观，我们令第i个出现的球颜色就是i（最后乘个阶乘就成）。那么有：
1122->0102
13223312->00203312
122132441231344->002102041231344
我们发现，i个0将序列分成i段，第i段的数字由1...i组成。考虑从1到n依次塞数字，数字i要塞在第i个0后面，因此会有这样的现象。我们尝试DP这个过程。我们发现，从1开始DP将非常恶心，因为前面的数字会影响后面数字的可摆放区间。也就是说，小数字会影响大数字，但大数字却不会影响小数字。于是我们考虑倒过来DP，这就非常舒服了，在放数字i时，第i个白球后面的球个数一定为(n-i)*k个，于是我们就可以愉快组合数了！结案！
如果直接这样写，那么样例都过不去。。。比如样例中的0021，可以认为出现顺序为1,2，也可以认为出现顺序为2,1。
因此，除白球外 第1个i球也要放在第1个i+1球前面 否则将当i球、i+1球的实际颜色交换时，该方案会被重复计算。因此，我们要多记一维第一个i球的位置。这个位置必定是直接跟在一串白球后的，所以我们可以这样设计：
令f[i][j]表示已放完第i...n个球，第i个球前有j个白球的方案数。
那么有 f[i][j]=f[i+1][j...n]*C(n-j+(n-i+1)*(k-1)-1,k-2))
前缀和优化一下就好了！
（注意，当k=1时要特判，直接输出1即可）
最喜欢这种代码特别短的题了
#include <bits/stdc++.h>
using namespace std; #define rep(i,l,r) for(int i=l;i<=r;++i)
#define per(i,r,l) for(int i=r;i>=l;--i) typedef long long ll; const int N=,NN=5e6;
const ll p=1e9+; int n,k;
ll jc[NN+],njc[NN+],f[N][N],g[N][N]; ll ksm(ll x,ll w){
ll ans=;
while(w){
if(w&1ll) (ans*=x)%=p;
(x*=x)%=p;
w>>=;
}
return ans;
} ll C(ll a,ll b){
return (jc[a]*njc[b]%p)*njc[a-b]%p;
} int main(){
scanf("%d%d",&n,&k); if(k==){
printf("1\n");
return ;
} jc[]=njc[]=;int L=5e6;
rep(i,,L) jc[i]=(jc[i-]*i)%p;
rep(i,,L) njc[i]=ksm(jc[i],p-); rep(j,,n) g[n][j]=;f[n][n]=;
per(i,n-,){
rep(j,i,n)
f[i][j]=(g[i+][j]*C(n-j+(n-i+)*(k-)-,k-))%p;
per(j,n,) g[i][j]=(g[i][j+]+f[i][j])%p;
} ll ans=;
rep(i,,n) (ans+=f[][i])%=p;
(ans*=jc[n])%=p; printf("%lld\n",ans); return ;
}