主要思路

这道题还蛮妙的，自己比较顺利的思考出来了。

考虑设置前缀异或和\(\{ S_i \}\)，根据异或按位处理的性质，显然对于所有的\(S_i\)都会小于\(2^n\)。最后，我们可以把限制变成：

• 不存在两个相同的前缀和。
• 不存在一对前缀和，其异或值为\(x\)。

针对\(x\)的大小关系，我们可以分成两种情况：

• \(x \geq 2^n\)，不存在一对\((S_i, S_j)\)的异或为\(x\)，因为存在更高的位并不会被消除。
• \(x < 2^n\)，我们发现每选择一个数作为前缀和，整个\(2^n\)中就会少一个对应的可以被选择的数。所以，我们每次选一个作为\(S_i\)的数时，都要把\(S_i xor \ x\)打标记。

结合一下就可以了。

代码

// CF1174D.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = (1 << 18) + 200;

int n, x, seq[MAX_N];
bool vis[MAX_N];

int main()
{
    scanf("%d%d", &n, &x);
    if (x >= (1 << n))
    {
        int len = (1 << n) - 1;
        printf("%d\n", len);
        for (int i = 1; i <= len; i++)
            printf("%d ", i ^ (i - 1));
    }
    else
    {
        vis[x] = true;
        int tot = 0;
        for (int i = 1, last = 0; i < (1 << n); i++)
            if (vis[i] == false)
                vis[i ^ x] = true, seq[++tot] = i ^ last, last = i;
        printf("%d\n", tot);
        for (int i = 1; i <= tot; i++)
            printf("%d ", seq[i]);
    }
    return 0;
}