cf 1174 D Ehab and the Expected XOR Problem

cf 1174 D Ehab and the Expected XOR Problem

题意

在1~(2^n)范围内找到一个最长的序列，使得该序列的每一个子串异或后不等于0和x

题解

假设该序列为a，那么前缀异或和b[i] = a[i]^a[i-1]...^a[0]，如果b之间异或都不会等于0和x，那么a之间也不会。

#include <cstdio>
#include <cstring>

int main() {
    int n, x;
    while(~scanf("%d %d", &n, &x)) {
        n = 1 << n;
        int ans[300000], cnt = 0;
        bool vis[300000];
        memset(vis, false, sizeof(vis));
        vis[x] = true;
        for(int i = 1; i < n; i++) {
            if(vis[i] == false){
                ans[cnt++] = i;
                vis[i] = vis[i^x] = true;
            }
        }
        printf("%d
", cnt);
        if(cnt) printf("%d ", ans[0]);
        for(int i = 1; i < cnt; i++) {
            printf("%d ", ans[i] ^ ans[i-1]);
        }
        if(cnt) printf("
");
    }
    return 0;
}