AtCoder Grand Contest 002 F - Leftmost Ball

题意：

有 n 种颜色的球，颜色分别标号为 1 到 n，每种颜色的球都有 k 个。这 nk 个球从左到右排成一个序列，接着把每种颜色最靠左的球涂成颜色 0。问有多少种最终可能得到的颜色序列。

题解：

思路不错，关键是要转化模型。
先忽略颜色，最后再乘个阶乘。

那么一个合法的序列相当于上图的拓扑序，那么就转成了一个拓扑序的计数问题。
考虑构造这个序列，就是说从后往前填如节点，定义f[i][j]$f[i][j]$表示已经用了j种不同的颜色，i个白点，转移的时候就多填入一个白点，或者新加一列新的颜色。

code：

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#define LL long long
using namespace std;
const LL mod=1e9+7;
LL n,k,f[2010][2010];
LL fac[4100010],inv[4100010];
void pre()
{
    fac[0]=fac[1]=inv[0]=inv[1]=1;
    for(LL i=2;i<=4100000;i++) fac[i]=fac[i-1]*i%mod,inv[i]=(mod-mod/i)*inv[mod%i]%mod;
    for(LL i=2;i<=4100000;i++) inv[i]=inv[i-1]*inv[i]%mod;
}
LL C(LL m,LL n) {return fac[m]*inv[m-n]%mod*inv[n]%mod;}
LL get(LL k,LL n) {return C(k+n,n);}
int main()
{
    pre();
    scanf("%lld %lld",&n,&k);
    if(k==1) return puts("1"),0;
    f[1][0]=1;
    for(LL i=1;i<=n;i++)
        for(LL j=0;j<=i;j++)
        {
            if(j<i) f[i][j+1]=(f[i][j+1]+f[i][j])%mod;
            if(i<n) (f[i+1][j]+=f[i][j]*get(k-2,i*(k-1)+j))%=mod;
        }
    printf("%lld",f[n][n]*fac[n]%mod);
}