专题班前缀和练习题 - B - 智乃酱的子集与超集

这个题从题面到解法都是很新颖的
先跳出前缀和这个框架，想想这个题在干什么
N = 20
M = 1e5
数据范围很多时候会提示数组怎么开，以及算法复杂度是多少





Q1：这个复杂度，提醒什么？
2表示这N个物品的某一个，取，还是不取
Q2：20维度的数组开不下，咋办？
开成一维的，用二进制位压缩
之后才会想到前缀和：因为要维护子集合与超集合

把 N 个物品理解为向量，先想二维的情况
F[A][B] = v[A][B]
F[A][B] += F[0][B] + F[A][0]
推广到 N 维：
F[A][B][C][D][E]... = v[A][B][C][D][E]...
F[A][B][C][D][E]... += v[A][0][0][0][0]... + ...
写成容斥，在维度上是不好扩展的。而写成空间向量的理解，是很好扩展的
加上二进制位运算

#include <bits/stdc++.h>
using namespace std;

#define ll long long
const int maxn = 20;
const int maxm = 1e5 + 10;
ll pre[(1<<maxn) + 20], suf[(1<<maxn) + 20], v[(1<<maxn) + 20];

int n, m, k, tmp, x;
int a[maxm];

int main(){
    //freopen("input.txt", "r", stdin);
    scanf("%d%d", &n, &m);
    memset(pre, 0, sizeof(pre));
    memset(suf, 0, sizeof(suf));
    memset(v, 0, sizeof(v));
    for(k = 0; k < n; k++)
        scanf("%d", &a[k]);
    for(int i = 0; i < (1 << n); i++){
        for(int j = 0; j < n; j++)
            if (i & (1 << j))
                v[i] = v[i] ^ a[j];
        pre[i] = suf[i] = v[i];
    }
    for(int j = 0; j < n; j++)
        for(int i = 0; i < (1 << n); i++)
            if (i & (1 << j))
                pre[i] += pre[i ^ (1 << j)];
            else
                suf[i] += suf[i ^ (1 << j)];
    while(m--){
        scanf("%d", &k);
        x = 0;
        while(k--){
            scanf("%d", &tmp);
            x += (1 << (tmp - 1));
        }
        printf("%lld %lld\n", pre[x], suf[x]);
    }
    return 0;
}