codeforces 553A – Kyoya and Colored Balls(组合数学+乘法逆元)

题目链接:Kyoya and Colored Balls

【题意】给出K(<=1000)种颜色的球,球的总数不超过1000个,第i种颜色的球的最后一个位置需要在第i+1种颜色最后一个球前面,问这样有多少种排列方式。

【分析】一看就发现是组合数学,可是我数学已经忘光了,而且还没开始做数学专题,导致直接不会写了,然后想着换种方法用DP求,然后就没时间了,唉;其实就是从后往前推,最后一种颜色的最后一个球先固定放在现在能放的最后面,然后对于每一种颜色的求分别求C(还剩下的位置数量,这种颜色的总数-1),最后把这些都乘起来就可以了,中间C()的除法用乘法逆元即可。由于球的总数不超过1000,所以阶乘不需要预处理也可以(说来惭愧,这是我第一次用乘法逆元,所以这场掉分是必须的)。

【AC CODE】31ms

#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <set>
//#include <unordered_set>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f, MAXN = 1000+10;
const LL MOD = 1000000007;

LL fact(int n)
{
	LL ans = 1;
	repe(i,2,n) ans = (ans*i)%MOD;
	return ans;
}
LL pow_mod(LL x, int n)
{
	LL ans = 1;
	while(n)
	{
		if(n&1) ans = (ans*x)%MOD;
		x = (x*x)%MOD;
		n >>= 1;
	}
	return ans;
}
LL dv(LL a, LL b)
{
	return a*pow_mod(b,MOD-2)%MOD;
}
LL cal(int n, int m)
{
	LL fn = fact(n),tmp = fact(m)*fact(n-m)%MOD;
	return dv(fn,tmp);
}
int main()
{
#ifdef SHY
	freopen("d:\\1.txt", "r", stdin);
#endif
	int n;
	scanf("%d", &n);
	LL ans = 1,sum = 0;
	rep(i,0,n)
	{
		LL a;
		scanf("%I64d", &a);
		sum += a;
		ans = ans*cal(sum-1,a-1)%MOD;
	}
	printf("%I64d\n", ans);
	return 0;
}

 

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

请输入正确的验证码