如何用格雷码优化枚举子集

yummy · 2023-07-03 22:08:27 · 题解

最近在给小朋友们备“位运算”这一节的课，在洛谷搜罗题目的时候发现这么一个非同寻常的题目。

目前我们看到，这题目前只能卡常完成，也就是枚举每个 S，然后尽快计算出 v(S)。但是，目前我看到的几篇题解都是希望在给定 v(S) 的时候通过计算前缀和以及 __builtin_ffs 来快速敲掉 v(S) 的一个前缀并加入一个数。

那么，有没有一种方法枚举子集，使得我们每次可以只改变一个数呢？

有的，格雷码就是例子。

所以我们使用格雷码维护所有子集，就可以保证每次只需要修改一个数，不需要使用前缀和技巧。但是递归常数非常感人，因此好像相比于维护当前要改的数位，还是直接 __builtin_ctz 快一点。

#include<bits/stdc++.h>
using namespace std;
int n;
unsigned long long a[32],ans,total;
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%llu",&a[i]);
    int S=0;
    for(int stt=1;stt<(1<<n);stt++)
    //stt记录哪些数翻过哪些没翻过
    {
        int lbt=(stt)&(-stt),bit=__builtin_ctz(lbt);
        //修改数位的位值，以及哪一位要修改
        total^=a[bit];
        S^=lbt;//S以格雷码顺序枚举
        ans^=total*S;
    }
    printf("%llu\n",ans);
}