51Nod 1453 抽彩球

Problem

一个袋子中有n个彩球，他们用k种不同的颜色染色。颜色被从1到k编号。同一种颜色的球看成是一样的。现在从袋中一个一个的拿出球来，直到拿完所有的球。对于所有颜色为i (1<=i<=k-1)的球，他的最后一个球总是在编号比他大的球拿完之前拿完，问这样情况有多少种。

样例解释：这个样例中有2个1号颜色的球，2个2号颜色的球，1个3号颜色的球。三种方案是： 1 2 1 2 3 1 1 2 2 3 2 1 1 2 3

Solution

我们先每种颜色各取出来一个，然后按顺序摆放，假设这就是最后一个球，然后按顺序摆其他球。

比如我要摆i号球，i号球一共有a[i]个，i号球的最后一个球，前面已经有sum[i-1]个球，那我们在摆第1个i号球时，有sum[i-1]+1种选择，第2个有sum[i-1]+2种，第a[i]-1个有sum[i-1]+a[i]-1，即sum[i]-1种，最后要除以(a[i]-1)!，因为没有顺序。就是说(sum[i-1]+1)(sum[i-1]+2)...(sum[i-1]+a[i]-1)/(a[i]-1)!，即C[sum[i]-1][a[i]-1]种可能，相乘即可，可以用费马小定理来处理除法。

Code

#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll mod=1000000007;
ll k,a[1020],ans=1,f1[1020]={1,1},f2[1020]={1,1};
ll speed(ll a,ll b,ll p){
	ll cur=a,ans=1;
	while(b){
		if(b&1) ans=ans*cur%p;
		cur=cur*cur%p;
		b>>=1;
	}
	return ans%p;
}
int main(){
	for(int i=1;i<=1000;i++){
		f1[i]=f1[i-1]*i%mod;
		f2[i]=f2[i-1]*speed(i,mod-2,mod)%mod;
	}
	scanf("%lld",&k);
	for(int i=1;i<=k;i++){
		scanf("%lld",&a[i]);
		a[i]+=a[i-1];
	}
	for(int i=1;i<=k;i++){
		int sum=a[i]-1,part=a[i]-a[i-1]-1;
		ans=ans*f1[sum]%mod*f2[part]%mod*f2[sum-part]%mod;
	}
	printf("%lld\n",ans);
	return 0;
}