A SRM 05 - YYL 杯 R1

背景

傻逼题

描述

       给一个序列，序列里只有两种元素1和2。现在要从序列里选出一些非空子序列使得子序列里两种元素数量相同。问有多少种方案数？

输入格式

     多组数据

     第一行一个正整数T，表示数据组数。

     每组数据内

            第一行 两个个正整数n，表示序列的长度

            第二行 n个数字，表示整个序列。

输出格式

      一个整数，表示方案数(mod 1e9+7)。

样例输入

1

3

2 2 1

样例输出

2

数据范围与约定

样例解释

在第一个样例中，两个子序列分别为{1,3},{2,3}，集合中数字为元素下标。

 

这道题呢 很容易发现答案和数字的排列顺序无关 我们只需要统计1和2的个数 然后一波组合数就可以推出答案了对吧 23333

但是啊 这题n可以到1e6（但是实测没有....)所以我们不可能用o（n2）的递推预处理组合数 而且空间也不够

这时候我们可以想到预处理阶乘 时间空间都满足而且可以实现o（1）计算组合数的值 

但是组合数C（n，m）=n!/m!(n-m)! 而除法是不满足除法过程中取模的 

这个时候逆元的派上了用场  a/b==a*power(b,P-2)%P

所以乘法是满足取余性质的 我们就可以o（n）预处理出阶乘取模后的值了

又由费马小定理的 因为p为质数 所以我们可以推出b的逆元

只用一次快速幂就能算出1e6的逆元 然后利用公式

fac(i)=fac(i-1)*i

fac_inv(i-1)=fac_inv(i)*i

tips fac为阶乘fac_inv为阶乘逆元

就可以o(n)预处理逆元了

然后就枚举一波 i—min（cnt1，cnt2） 就可以算出答案了 23333

不过注意每乘一次就要取余一次 不然可能会炸longlong

#include
      
       #include
       
        #include
        
         #define LL long longusing namespace std;const int mod=1e9+7,M=1000001;LL read(){    LL ans=0,f=1,c=getchar();    while(c<'0'||c>'9'){
    if(c=='-') f=-1; c=getchar();}    while(c>='0'&&c<='9'){ans=ans*10+(c-'0'); c=getchar();}    return ans*f;}LL T,n,cnt1,cnt2,k,ans;LL w[M],b[M];LL qmod(LL a,LL b,LL c){    LL ans=1;    while(b){        if(b&1) ans=ans*a%c;        b=b/2;        a=a*a%c;    }    return ans;}void prepare(){    int mx=1000000; w[1]=1;    for(int i=2;i<=mx;i++) w[i]=w[i-1]*i%mod;    b[mx]=qmod(w[mx],mod-2,mod); //printf("[%lld]\n",w[mx]);    for(int i=mx;i>=1;i--) b[i-1]=b[i]*i%mod; //printf("[%d]\n",b[0]);}int main(){    prepare();    T=read();    while(T--){        n=read();         cnt1=0; cnt2=0; ans=0;        for(int i=1;i<=n;i++){            k=read();            if(k==1) cnt1++;            else cnt2++;        }        for(int i=1;i<=min(cnt1,cnt2);i++)            ans=(ans+w[cnt1]*b[i]%mod*b[cnt1-i]%mod*w[cnt2]%mod*b[i]%mod*b[cnt2-i]%mod)%mod;        printf("%lld\n",ans);    }    return 0;}