AT2000 Leftmost Ball 解题报告

题面

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

解法

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

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

第一部分: 加一个白球,我们规定了白球放首位以避免重复计算

第二部分: 加入一种新颜色: 还有(n-j+1)种颜色,选出一种后,需要放(k-2)个,又因为共有i+(j-1)*(k-1)-1个空格,所以是\(f(i ,\;j-1)\times (n-j+1)\times \dbinom{k-2}{n*k-i-(j-1)*(k-1)-1}\)

证毕!

代码

#include<iostream>

using namespace std ;

#define int unsigned long long

const int mxn = 8000005 ;

const int Mod = 1e9+7 ;

int frac[mxn], inv[mxn];

int f[2005][2005], n, k;

int power(int a, int b){

	int res=1, car=a;

	while(b){

		if(b&1) (res*=car)%=Mod;

		(car*=car)%=Mod;

		b>>=1;

	}

	return res;

}

void init(){

	frac[0]=1 ;

	for(int i=1;i<mxn;++i) (frac[i]=frac[i-1]*i)%=Mod ;

	inv[mxn-1] = power(frac[mxn-1], Mod-2);

	for(int i=mxn-2;i>0;--i) inv[i]=(inv[i+1]*(i+1))%Mod ;

	inv[0] = 1 ;

}

int C(int n, int k){

	return ((frac[n]*inv[k]%Mod)*inv[n-k])%Mod ;

}

signed main(){

	init() ;

	cin>>n>>k;

	if(k==1) return puts("1"),0 ;

	f[0][0] = 1 ;

	for(int i=1;i<=n;++i)

		for(int j=0;j<=i;++j)

			(f[i][j] = f[i-1][j]+(j?((((f[i][j-1]*(n-j+1))%Mod)*C(n*k-i-(j-1)*(k-1)-1, k-2))%Mod):(0)))%=Mod ;

	cout<<f[n][n]<<endl ;

}

巴特西

AT2000 Leftmost Ball 解题报告

题面

解法

代码

最新文章

热门文章