【AtCoder Grand Contest 002F】Leftmost Ball / 题解

【AtCoder Grand Contest 002F】Leftmost Ball / 题解

Description

把一共 $n$ 种颜色,每种颜色 $k$ 个的球排成一行,然后把每种颜色的第一个球涂成白色。求最终颜色序列的种数。

Idea

我们可以看成 $n+1$ 个颜色,其中白球有 $n$ 个,剩下每种颜色 $k-1$ 个。题目的限制条件为,颜色序列的每个前缀中,白球数量不得小于其他球的数量。我们可以利用这个性质从后往前 $DP$。

设 $f_{i,j}$ 表示放下 $i$ 个白球,$j$ 种其他颜色球的方案数。

  • 新增一个白球,直接由 $f_{i-1,j}$ 转移过来;
  • 新增一种其他的颜色,也就是加入了 $k-1$ 个新的小球。为了避免算重,$k-1$ 个球中的第一个必须放在最靠前的空位中,剩下 $k-2$ 个插入剩下的小球中,也就是 $n-i+(n-j+1)*(k-1)-1$。

Code

#include <bits/stdc++.h>
#define ll long long
const int md=1e9+7;
const int maxm=4001000;
const int maxn=2001;
int read(){
    int x=0,flag=1;char ch=getchar();
    while(!isdigit(ch)&&ch!='-') ch=getchar();
    if (ch=='-') flag=-1,ch=getchar();
    while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch-'0'),ch=getchar();
    return x*flag;
}
ll fac[maxm],inv[maxm];
ll ksm(ll a,ll b){
    ll res=1;
    while(b){
        if (b&1) res=res*a%md;
        a=a*a%md;b>>=1;
    }
    return res;
}
void init(int n){
    fac[0]=1;
    for (int i=1;i<=n;++i)
        fac[i]=fac[i-1]*i%md;
    inv[n]=ksm(fac[n],md-2);
    for (int i=n;i;--i)
        inv[i-1]=inv[i]*i%md;
}
ll c(int n,int m){
    return fac[n]*inv[m]%md*inv[n-m]%md;
}
int n,k,f[maxn][maxn];
int main(){
    n=read(),k=read();
    if (k==1) return puts("1"),0;
    init(n*k);
    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];
            if (!j) continue;
            (f[i][j]+=1ll*f[i][j-1]*(n-j+1)%md*
            c(n-i+(n-j+1)*(k-1)-1,k-2)%md)%=md;
        }
    }
    printf("%d\n",f[n][n]);
}
Show Comments