题解 AT2000 【Leftmost Ball】

· · 题解

看到这道题的时候，我其实是非常懵逼的。看了几篇博客，终于略通一二。下面是我对此题的理解。

题目大意

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

分析

数据规模是\leq2000,考虑O(n^2)的做法：

我们观察发现：对于任意方法的任意前缀，白色的球的个数一定大于等于其颜色种类数，这就给了我们递推的条件——我们可以把白色球与其他颜色球分开看：

现在我们有n\times{k}位置：

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

考虑转移：

我们可以从f(i-1,j)多放一个白球转移，也可以从f(i,j-1)多放一种颜色转移，那么转移方程已经呼之欲出，但我们需要注意，此处计算方案不能算重，那么我们人为规定每一次放颜色球时，第一个球一定放在当前第一个空格。

1.初始状态。 2.先放绿色。 3.先放白色。 4.方案算重。

所以有转移方程：

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

最后记得一定要特判k=1的情况（因为上面那个霸道的（雾）规定）。

代码如下

#include<iostream>
#include<cstdio>
#include<cstdlib>
#define re register
#define LL long long
#define N 2005
#define Maxn 4000000
using namespace std;
const int Mod=1e9+7;
int n,k;
LL f[N][N],fac[Maxn+5],inv_fac[Maxn+5];
inline LL C(int n,int m){ return (((fac[m]*inv_fac[n])%Mod)*inv_fac[m-n])%Mod; }
LL power(LL x,int P){
    LL ans=1,m=x;
    while(P){
        if(P&1) (ans*=m)%=Mod;
        P>>=1;(m*=m)%=Mod;
    }
    return ans;
}
int main(){
    scanf("%d%d",&n,&k);
    if(k==1){ printf("%d\n",1); return 0; }
    fac[0]=1; for(re int i=1;i<=Maxn;++i) fac[i]=(fac[i-1]*i)%Mod;
    inv_fac[Maxn]=power(fac[Maxn],Mod-2); for(re int i=Maxn-1;i>=0;--i) inv_fac[i]=(inv_fac[i+1]*(i+1))%Mod;
    f[0][0]=1;
    for(re int i=1;i<=n;++i){
        for(re int j=0;j<=i;++j){
            f[i][j]=f[i-1][j];
            if(!j) continue;
            (f[i][j]+=f[i][j-1]*(n-j+1)%Mod*C(k-2,n-i+(n-j+1)*(k-1)-1)%Mod)%=Mod;
        }
    }
    printf("%lld\n",f[n][n]);
    return 0;
}

后记

这道题我的理解还有一些生硬，须进一步体会。有什么不对的地方也请大佬指教。