B 智乃酱的子集与超集 题解

AC代码（含注释）

//本质：二进制状压dp
//外衣：前缀和
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1<<20;
int a[25],sup_sum[maxn],chi_sum[maxn];
signed main(){
    int N,M;
    cin>>N>>M;
    for(int i=1;i<=N;i++){
        cin>>a[i];
    }
    for(int i=0;i<(1<<N);i++){//对于1<<N种情况
        int sum=0;
        for(int j=0;j<N;j++){//遍历二进制每一位
            int nowbit=(1<<j);//对于状压后第j位
            if(i&nowbit)sum^=a[j+1];//第j个物品存在，去异或它
        }
        sup_sum[i]=chi_sum[i]=sum;//记录每种情况的异或和
    }
    //子集不一定是真子集,超集不一定是真超集,本身也含
    //空集是任何非空集合的真子集,任何非空集合都是空集的真超集
    //要先针对每一位,再遍历所有状态,这是基于dp的思想
    //每种状态都在每一位上从低位至高位累加状态
    for(int i=0;i<N;i++){//对于二进制每一位
        int nowbit=(1<<i);//对于状压后第i位
        for(int j=0;j<(1<<N);j++){//对于1<<N种情况
            int presit=j^nowbit;//获取当前状态在第i位的子状态或超状态
            if(j&nowbit)chi_sum[j]+=chi_sum[presit];//子状态前缀和
            else sup_sum[j]+=sup_sum[presit];//超状态前缀和
        }
    }
    //模拟：2种物品
    //对于二进制第1位：
    //sup_sum[00]+=sup_sum[01]
    //chi_sum[01]+=chi_sum[00]
    //sup_sum[10]+=sup_sum[11]
    //chi_sum[11]+=chi_sum[10]
    //对于二进制第2位：
    //sup_sum[00]+=sup_sum[10]
    //sup_sum[01]+=sup_sum[11]
    //chi_sum[10]+=chi_sum[00]
    //chi_sum[11]+=chi_sum[01]
    while(M--){
        int k;
        cin>>k;
        int nowsit=0;
        for(int i=1;i<=k;i++){
            int p;
            cin>>p;
            int nowbit=(1<<(p-1));
            nowsit|=nowbit;
        }
        cout<<chi_sum[nowsit]<<" "<<sup_sum[nowsit]<<endl;
    }
    return 0;
}