题解|#智乃酱的子集与超集#

链接：https://ac.nowcoder.com/acm/contest/19483/B
简要题意：给出一个数组a，定义一个集合的价值为里头所有物品价值的异或。现给出若干集合，求每个集合所有子集、所有超集的价值之和
分析：采用二进制来表示每个集合。二进制的每一位可以看成dp的一个维度。如集合1011表示含有第0、1、3个物品（采用从右到左，物品从0下标开始标号）
这样要想判定集合j是否含有第i个物品，就只需看j&(1<<i)是否为1即可
我们用pre和suf数组来记录每个集合的所有子集和所有超集之和
初始化时，先令pre[i]=suf[i]=集合i的价值
接下来，对于每个物品i，
如果它包含在集合j中，那么j&(1<<i)=1，集合j^(1<<i)就是集合j的子集（j的第i位是1，j^(1<<i)的第i位是0），这时候更新pre[j]
如果它不在集合j中，那么j&(1<<i)=0，集合j^(1<<i)就是集合j的超集（j的第i位是0，j^(1<<i)的第i位是1），这时候更新suf[j]

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define _for(i,a,b)    for(int i=(a);i<=(b);i++)
const int N=25;
const int M=1048576;
ll a[M],pre[M],suf[M];
int n,m;
int main(){
    cin >> n >> m;
    int maxbit=(1<<n);//总集合个数
    _for(i,0,n-1){
        cin >> a[i];
    }
    _for(i,0,maxbit-1){//遍历每个集合，考虑每个集合内部的物品
        ll sum=0;
        _for(j,0,n-1){//遍历所有物品
            if(i & (1<<j))    sum^=a[j];//集合i含有物品j
        }
        pre[i]=sum;
        suf[i]=sum;
    }
    _for(i,0,n-1){//遍历每个物品，即每个维度
        _for(j,0,maxbit-1){
            if(j & (1<<i))    pre[j]+=pre[j^(1<<i)];
            else    suf[j]+=suf[j^(1<<i)];
        }
    }
    while(m--){
        int k;
        cin >> k;
        int q=0;//q为当前的集合方案
        while(k--){
            int x;
            cin >> x;
            q|=(1<<(x-1));
        }
        cout << pre[q] << " " << suf[q] << "\n";
    }
    return 0;
}