HDU 3006 The Number of set（位运算 状态压缩）

 1 # include<stdio.h>
 2 # include<string.h>
 3 int n,m,k;
 4 int dp[1<<15];
 5 int main(){
 6     int i;
 7     while(scanf("%d%d",&n,&m)!=EOF){
 8         memset(dp,0,sizeof(dp));
 9         while(n--){
10             scanf("%d",&k);
11             int set = 0;
12             int temp;
13             for(i=1;i<=k;i++){    //得到这个集合的二进制表示
14                 scanf("%d",&temp);
15                 set = set|(1<<(temp-1));
16             }
17             
18             dp[set] = 1;
19             for(i=0; i<(1<<m); i++)    //将新的集合与以往得到的集合合并
20                 if(dp[i])
21                     dp[i|set] = 1;
22         }
23         int ans = 0;
24         for(i=0; i<(1<<m); i++)    //判断可以组成集合的个数
25             if(dp[i])
26                 ans++;
27             printf("%d\n",ans);
28     }
29     return 0;
30 }