zoj How Many Sets I(组合计数) - c++编程基础

一个集合s有n个元素，求满足这样的集合序列{s1,s2....sk}使S₁ ∩ S₂ ∩ ... ∩ S_k = ?，si是s的子集。

从每个元素考虑会使问题变得简单。首先n个元素是相互独立的，单独考虑第i个元素，它在k个子集的所有情况是2^k，其中有一种情况是k个子集都有第i个元素，这一种情况正好不是我们想要的，所以合法的应该是2^k-1，那么n个元素就是( 2^k-1 )^n。

#include 
  
   
#include 
   
     #include
     #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
             
               #include 
              
                #include 
               
                 //#define LL __int64 #define LL long long #define ULL unsigned long long #define eps 1e-9 #define PI acos(-1.0) using namespace std; const LL mod = 1000000007; LL Pow(LL a, LL b) { LL res = 1; while(b) { if(b&1) res = (res*a)%mod; b >>= 1; a = (a*a)%mod; } return res; } int main() { LL n,k; while(~scanf(%lld %lld,&n,&k)) { LL res = Pow((LL)2,k); res -= 1; res = Pow(res,n); printf(%lld ,res); } return 0; }