欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【hpu oj 1011 QAQ的序列组合 [组合数学]】

程序员文章站 2022-07-04 12:48:38
...

点击打开链接


【hpu oj 1011 QAQ的序列组合 [组合数学]】



AC代码:/*用到了快速幂,逆元,。。。需要预处理一下,不然会超时?!*/


#include<cstdio>
#define mod 1000000007
typedef long long LL;
#define maxn  1000000+11
LL num[maxn],pre[maxn];
void reset()
{
	num[0]=1;
	LL i;
	for(i=1;i<maxn;++i)
		num[i]=num[i-1]*i%mod;
}
LL QuickPower(LL a,LL n)
{
	LL ans=1;
	while(n)
	{
		if(n&1)
			ans=ans*a%mod;
		a=a*a%mod;
		n>>=1;
	}
	return ans;
}
void count()
{
	LL i;
	for(i=0;i<maxn;i++)
		pre[i]=QuickPower(num[i],mod-2);
}
int main()
{
	int t;
	reset();
	count();
	scanf("%d",&t);
	while(t--)
	{
		LL h=0,low=1;
		int n;
		scanf("%d",&n);
		while(n--)
		{
			LL a;
			scanf("%lld",&a);
			h+=a;
			low=low*pre[a]%mod;
		}
		LL ant;
		if(h==0)
			printf("0\n");
		else 
			printf("%lld\n",(num[h]%mod*low%mod)%mod);
	}
}