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

$[思维+前缀和]$

给定长度为 $n$ 的 $a$ 数组，一共 $m$ 次询问：每次询问给定一个长度 $k$ 的 $a$ 数组的一个子集。

定义：集合的权值为该集合内所有元素的异或值

定义：超集为包含该集合的其他所有长度为 $n$ 的 $a$ 数组的子集

求该子集的所有子集的权值之和以及该子集的所有超集的权值之和

例如题目样例： $a$ 数组为 $[1,5,9]$

第 $3$ 次查询为长度为 $2$ 的子集 $[1,2]$ (这是下标)，所以实际为 $[1,5]$

该集合的所有子集为 $[1]$ ， $[5]$ ， $[1，5]$ ；对应的权值为 $1$ ， $[5]$ ， $[1，5]$ ；所以所有子集的权值为 $10$

该集合的所有超集为 $[1,5]$ ， $[5]$ ；对应的权值为 $[1，5]$ ， $[1，5]$ ；所以所有超集的权值为 $17$

解决这道题目使用的前缀和的思想

设 $pre[i]$ (其中 $i$ 的二进制表示状态，即构成的集合)表示其包含所有子集的权值之和

设 $fpre[i]$ 表示其包含所有超集的权值之和

当前的状态为 $j$ ， $i$ 是状态 $j$ 二进制下第 $i$ 位，如果满足 $(j\ >>\ i)\ \&\ 1$ ，那么有：

$pre[j]=pre[j]+pre[j-(1\ <<\ i)]$

$fpre[j]=fpre[j]+fpre[j+(1\ <<\ i)]$

这就是子集更新与超集更新的式子，因为是每一位考虑的，所以不会遗漏与重复！

总代码：

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

#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;


const int N = 21;

int pre[1 << N], fpre[1 << N];

signed main(){
    HelloWorld;
    
    int n, q; cin >> n >> q;
    vector<int> a(n);
    for(int i = 0; i < n; i ++) cin >> a[i];
    
    for(int i = 0; i < (1 << n); i ++){
        int res = 0;
        for(int j = 0; j < n; j ++){
            if((i >> j) & 1) res ^= a[j];
        }
        pre[i] = res, fpre[i] = res;
    }

    for(int i = 0; i < n; i ++){
        for(int j = 0; j < (1 << n); j ++){
            if((j >> i) & 1) pre[j] += pre[j - (1 << i)];
            else fpre[j] += fpre[j + (1 << i)];
        }
    }

    while(q --){
        int k; cin >> k;
        int x = 0;
        for(int i = 1; i <= k; i ++){
            int q; cin >> q;
            q --;
            x += (1 << q);
        }
        cout << pre[x] << " " << fpre[x] << endl;
    }
    return 0;
}