洛谷 AT2000 Leftmost Ball

题目链接

数据范围告诉我们需要一个(O(n^2))级别的做法

首先朴素DP

Step 1

(dp[i][...])表示前(i)个球和每种颜色的球放了多少个

显然我们必须要记录每种颜色的球放了多少才能完美解决,因此枚举放到第几个球是不行的

Step 2

(dp[..])表示每种颜色的球放了多少个

因为白球是同种颜色球中最靠左的那个,为了方便和去重,我们考虑每个白球都是放在从左往右第一个空位,其他的球随意找空

因为我们假定了每一种球是不同的,最后要除以((k-1))个球的排列

Step 3

(dp[i][j])表示当前放了(i)个白球,(j)种颜色的球

因为白球一定是同种颜色的球最前面的那个

我们把白球和其他的球分开来看

对于不同颜色的球,我们发现放法就是从当前剩余的空位中找出来((k-1))个空的组合数

因此可以考虑每次放一种颜色的球

每次对序列操作,要么放一个白球,要么把一种颜色的(k-1)个球全部放入

为了避免重复,我们每次只考虑从左往右第一个空位置上放什么球,

[dp[i][j]=dp[i-1][j]+dp[i][j-1]*(n-j+1)*C_{n*k-(j-1)*(k-1)-i-1}^{k-2} ]

解释一下:

(dp[i-1][j])表示当前放了一个白球的转移

(dp[i][j-1]*(n-j+1)*C_{n*k-(j-1)*(k-1)-i-1}^{k-2})表示当前放了一种颜色的球的转移

其中(n-j+1)表示从剩下的颜色中选出一种颜色,放一个球在最前面的空位

然后在(n*k-(j-1)*(k-1)-i-1)个空位中选出(k-2)个给剩下的球放

注意(dp[i][j])要保证(i>=j)时才有意义

[Code]

#include<bits/stdc++.h>
using namespace std;

int read(){
	int x=0; char c=getchar(); int flag=1;
	while(!isdigit(c)) { if(c=='-') flag=-1; c=getchar(); }
	while(isdigit(c)) { x=((x+(x<<2))<<1)+(c^48); c=getchar(); }
	return x*flag;
}

const int mod=1e9+7;

int n,k;
int dp[2005][2005];//i个白球，j种颜色 

int fac[4000005],Inv[4000005]; 

int C(int n,int m){
	if(m<0||n<m) return 0;
    return 1ll*(1ll*fac[n]*Inv[m]%mod)*Inv[n-m]%mod; 
}

void exgcd(int a,int b,int &x,int &y){
    if(b==0) { x=1; y=0; return ; }
    exgcd(b,a%b,y,x); y-=a/b*x;
}

int inv(int a){
    int x=0,y=0;
    exgcd(a,mod,x,y);
    return (x%mod+mod)%mod;
}

signed main(){
	fac[0]=1;
	for(int i=1;i<=4000000;i++) fac[i]=1ll*fac[i-1]*i%mod;
	Inv[4000000]=inv(fac[4000000]);
	for(int i=3999999;i>=0;i--) Inv[i]=1ll*Inv[i+1]*(i+1)%mod;
	
    n=read(),k=read();
    if(k==1) { puts("1"); return 0; } 
	dp[0][0]=1;
    
    for(int i=1;i<=n;i++){ 
	    dp[i][0]=1;
		for(int j=1;j<=i;j++){
			dp[i][j]=(dp[i-1][j]+1ll*(1ll*dp[i][j-1]*C(n*k-(j-1)*(k-1)-i-1,k-2))%mod*(n-j+1)%mod)%mod; 
		} 
	}
	
	printf("%d
",dp[n][n]);
    return 0;
}