[DP记录]AT2000 [AGC002F] Leftmost Ball

**题意** ： 给你 $n$ 种颜色的球，每个球有 $k$ 个，把这 $n\times k$ 个球排成一排，把每一种颜色的最左边出现的球涂成白色(初始球不包含白色)，求有多少种不同的颜色序列。 答案对 $10^9+7$ 取模。 $n,k\leq 2000$ ，时限$\texttt{2s}$。 ------------ 考虑怎样的序列才可能是由上述规则生成的序列。 充要条件 ： 每个前缀的白球个数 $\geq$ 其他颜色种类数 于是，在合法性问题上，我们只关心各个彩色球的第一次出现，以及白球。 考虑 $\rm DP$ ，向 $n\times k$ 个槽位中放球。 记 $dp[i][j]$ 为放置了前 $i$ 个白球，以及第一次出现最靠前的 $j$ 种彩球，每种彩球放置 $k-1$ 个的方案数。 显然，这里要求 $i\geq j$。 考虑最靠前的第一个空位放置什么，转移如下 ： - 放置一个白球 一定合法。 $$dp[i+1][j]\texttt{ += }dp[i][j]$$ - 放置一个彩球 由 $dp[i][j]$ 转移至 $dp[i][j+1]$。 $i$ 个白球一定都在这个空位前面，所以当 $i\geq j+1$ 则合法。 选择一个未出现的颜色，方案数为 $(n-j)$。 在后面的空位中，选择 $k-2$ 个用于放置其他的同色球，方案数为 $\dbinom{nk-i-j(k-1)-1}{k-2}$ $$dp[i][j+1]\texttt{ += }dp[i][j]\times(n-j)\times\dbinom{nk-i-j(k-1)-1}{k-2}$$ 复杂度 $O(n^2)$。注意需要特判 $k=1$ 的情况 ```cpp #include<algorithm> #include<cstdio> #define ll long long #define MaxN 2050 using namespace std; const int mod=1000000007; ll powM(ll a,int t=mod-2){ ll ret=1; while(t){ if (t&1)ret=ret*a%mod; a=a*a%mod;t>>=1; }return ret; } int fac[MaxN*MaxN],ifac[MaxN*MaxN]; int C(int n,int m) {return 1ll*fac[n]*ifac[m]%mod*ifac[n-m]%mod;} void Init(int n) { fac[0]=1; for (int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%mod; ifac[n]=powM(fac[n]); for (int i=n;i;i--) ifac[i-1]=1ll*ifac[i]*i%mod; } int n,k,dp[MaxN][MaxN]; int main() { scanf("%d%d",&n,&k); Init(n*k); if (k==1){puts("1");return 0;} dp[0][0]=1; for (int i=0;i<=n;i++) for (int j=0;j<=i;j++){ if (j+1<=i) dp[i][j+1]=(dp[i][j+1]+1ll*dp[i][j]*(n-j)%mod*C(n*k-i-j*(k-1)-1,k-2))%mod; dp[i+1][j]=(dp[i+1][j]+dp[i][j])%mod; } printf("%d",dp[n][n]); return 0; } ```