题解 AT2000 【Leftmost Ball】
ezoixx130
2019-09-09 09:22:56
考虑钦定除 $0$ 以外的所有颜色的首次出现的顺序，即从前往后 $1$ 先出现，$2$ 再出现，然后是 $3,4,\cdots,n$。最后把答案乘一个 $n!$ 就行了。
钦定了顺序之后，就可以把最前面的 $0$ 按顺序分配给 $1$ 到 $n$ 了。考虑从 $n$ 到 $1$，对于每个 $k$，每次插 $1$ 个 $0$ 和 $m-1$ 个 $k$。这时 $0$ 必须插到序列最前面，而第一个 $k$ 必须插在原序列中第一个非零数的前面。
注意到插法跟第一个非零数的位置有关。受到这点的启发，我们可以直接 dp，设 $f_{i,j}$ 表示已经插了 $n-i+1$ 到 $n$，序列前端有 $j$ 个 $0$ 的方案数。该 dp 的转移是：
$f_{i,j+1} = \sum_{k>=j} f_{i-1,k} \times g(m\times(i-1)-j+1,m-2)$。
其中 $g(x,y)$ 表示把 $y$ 个数插到 $x$ 个空当中（可以相邻）的方案数，即 $g(x,y)=C^y_{x+y-1}$。
注意到这个转移后面的那个组合数跟 $k$ 根本没有关系。所以我们直接维护 $f_i$ 的后缀和进行转移就行啦。
代码：
```cpp
#include <bits/stdc++.h>
using namespace std;
#define MAXN 2010
#define mod 1000000007
int n,k,fac[MAXN*MAXN],inv[MAXN*MAXN],f[MAXN][MAXN];
int qpow(int a,int b)
{
int res=1;
while(b)
{
if(b&1)res=(long long)res*a%mod;
a=(long long)a*a%mod;
b>>=1;
}
return res;
}
int c(int n,int m)
{
if(n<0 || n<m)return 0;
return (long long)fac[n]*inv[m]%mod*inv[n-m]%mod;
}
int main()
{
scanf("%d%d",&n,&k);
if(k==1)
{
puts("1");
return 0;
}
fac[0]=inv[0]=1;
for(int i=1;i<=n*k;++i)fac[i]=(long long)fac[i-1]*i%mod;
inv[n*k]=qpow(fac[n*k],mod-2);
for(int i=n*k-1;i>=1;--i)inv[i]=(long long)inv[i+1]*(i+1)%mod;
f[0][0]=1;
for(int i=0;i<=n;++i)
for(int j=i;j>=0;--j)
{
f[i+1][j+1]=(f[i+1][j+1]+(long long)f[i][j]*c(i*k-j+k-2,k-2)%mod)%mod;
if(j)f[i][j-1]=(f[i][j-1]+f[i][j])%mod;
}
printf("%lld\n",(long long)f[n][0]*fac[n]%mod);
}
```