题解 AT2000 【[AGC002F] Leftmost Ball】

· · 题解

洛谷题目传送门

ATCODER传送门

设 dp[i][j] 表示放完 i 个白球和 j 种有颜色的球的情况。

首先 dp[i][j] 显然可以从 dp[i-1][j] 转移（多放一个白球的方案）。

然后 dp[i][j] 可以从 dp[i][j-1] 转移（多添加一种颜色的方案）。

既然要多添加一种颜色，那么就要选择剩下 n-j+1 种颜色填入，

并且要在剩下的 nk-i-1-(j-1)\times(k-1) 个位置中选择 k-2 个填入下一种颜色，也就是 C_{nk-i-1-(j-1)\times (k-1)}^{k-2}。

补充说明：

  1. 排列长度 n\times k，放入 i 个白球和 j-1 种颜色（每种颜色为 k-1 个）
  2. 为什么是 k-2，如果不指定当前剩下的第一个位置为该颜色， 那么当选择其它颜色填入时这种方案就会算重，所以是 k-2，并且剩下的总位置也要减 1。

预处理阶乘和乘法逆元就可以了。

#include <cstdio>
#define rr register
using namespace std;
const int mod=1000000007,N=2001;
int n,k,inv[N*N],fac[N*N],dp[N][N];
inline signed mo(int x,int y){
    return x+y>=mod?x+y-mod:x+y;
}
inline signed c(int n,int m){
   return 1ll*fac[n]*inv[m]%mod*inv[n-m]%mod;
}
signed main(){
    inv[0]=inv[1]=fac[0]=fac[1]=1,scanf("%d%d",&n,&k);
    if (k==1) return !putchar(49);
    for (rr int i=2;i<=n*k;++i)
        inv[i]=1ll*inv[mod%i]*(mod-mod/i)%mod;
    for (rr int i=2;i<=n*k;++i) fac[i]=1ll*fac[i-1]*i%mod;
   for (rr int i=2;i<=n*k;++i) inv[i]=1ll*inv[i-1]*inv[i]%mod;
    for (rr int i=0;i<=n;++i) dp[i][0]=1;
    for (rr int i=1;i<=n;++i)
   for (rr int j=1;j<=i;++j)
        dp[i][j]=mo(dp[i-1][j],1ll*dp[i][j-1]*(n-j+1)%mod*c(n*k-i-1-(j-1)*(k-1),k-2)%mod);
    return !printf("%d\n",dp[n][n]);
}