bzoj2839 集合计数-白红宇

bzoj2839 集合计数

阅读量：7097 次

发布时间：2019-06-28

本文共 978 字，大约阅读时间需要 3 分钟。

分析

我的做法和这个博客几乎相同

只是我在处理$2^{2^{n-i}}-1$的时候是先处理前面的再处理后面的

所以前面的$2^{2^{n-i}}$我们只需要从$i=n$开始循环，每次平方即可

代码

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 #include
                  
                   using namespace std;#define int long longconst int mod = 1e9+7;int pw[1001000],inv[1001000];inline int PW(int x,int p){ int res=1; while(p){ if(p&1)res=res*x%mod; x=x*x%mod; p>>=1; } return res;}inline int c(int n,int m){ return pw[n]*inv[m]%mod*inv[n-m]%mod;}signed main(){ int n,m,i,j,k,Ans=0,now=2; scanf("%lld%lld",&n,&k); inv[0]=pw[0]=1; for(i=1;i<=n;i++)pw[i]=pw[i-1]*i%mod; inv[n]=PW(pw[n],mod-2); for(i=n-1;i>0;i--)inv[i]=inv[i+1]*(i+1)%mod; for(i=n;i>=k;i--){ int wh=((i-k)%2==0?1:-1); Ans=(Ans+mod+wh*c(i,k)*c(n,i)%mod*(now-1+mod)%mod)%mod; now=now*now%mod; } cout<
                   
                    <