【hpu oj 1011 QAQ的序列组合 [组合数学]】
程序员文章站
2022-07-04 12:48:38
...
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);
}
}
上一篇: python基础知识之循环语句
下一篇: MCU最强科普总结