[DP记录]AT2000 [AGC002F] Leftmost Ball

· · 个人记录

题意 ： 给你 n 种颜色的球，每个球有 k 个，把这 n\times k 个球排成一排，把每一种颜色的最左边出现的球涂成白色(初始球不包含白色)，求有多少种不同的颜色序列。

答案对 10^9+7 取模。

------------ 考虑怎样的序列才可能是由上述规则生成的序列。 充要条件 ： 每个前缀的白球个数 $\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 的情况

#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;
}