Description

 

Input

Output

 

Sample Input

22 3 41 2 3

Sample Output

31

 

Data Constraint

 

Hint

 

 

 

题解

• 答案=选择第一个话题能交流的人数的k次方+选择第二个话题交流的人数的k次方+….-选择一二两个话题都能交流的人数的 k 次方+… 
• 暴力的时间复杂度就是O(m*2^n)
• 那么就可以设f[i]为i的子集的方案，转移就是所有它的父亲(可以变成i的)加起来

代码

1 #include 
     
       2 #include 
      
        3 using namespace std; 4 int t,n,m,k,num[1048577]; 5 long long ans,mo=1000000007; 6 long long ksm(long long a,long long b) 7 { 8     long long r=1; 9     for(;b;b>>=1,a=a*a%mo) if(b&1) r=r*a%mo;10     return r;   11 }12 void dfs(int x,int y,int zf)13 {14     if (x>n)15     {16         if (y==0) return;17         (ans+=zf*ksm(num[y],k)+mo)%=mo;18         return;19     }20     dfs(x+1,y,zf),dfs(x+1,y|(1<