题面看着很吓人！但是经过了一步步的思考，切完后再来看，其实也不过如此。
纪念一下独立切的铜牌构造题。
由于有 \(+1\) 操作，考虑反着建立 01-trie，即以最低位作为第一个分支。这样 \(+1\) 操作相当于对最右边的一条链上每个点执行左右儿子交换。
考虑 trie 树上每个叶子挂着对应数值在 \(A\) 中的位置，我们的目标状态为：每个叶子挂着的数等于对应数值。
不管是异或还是 \(+1\) 操作，都只能交换左右儿子，所以无解的判定是容易的：进行一次 DFS，判断当前点 \(u\) 与目标状态的 \(v\) 子树是否合法，每次判断 \(u\) 的子树中最左边的叶子在 \(v\) 的左子树还是右子树，然后递归判定。
这样一遍 DFS 我们还能顺便求出 \(t_u=0/1\) 表示为了到达目标状态，点 \(u\) 是否需要交换左右儿子。
为了方便表述，我们以“\(t_u\) 的改变”来代替点 \(u\) 交换左右儿子的操作。那么，我们的目标是把所有点的 \(t\) 变为 \(0\)。
我们现在有两种方法：
-
异或一个数，使得同一层内的点 \(t\) 值全部取反，或全都不改变。
-
\(+1\)，使得最右边一条链上所有点的 \(t\) 值全部取反。
注意到对于一条链，如果我们通过异或操作把它“旋转”到最右边，进行一次 \(+1\) 操作，再旋转回来，等价于我们可以令这条链上的 \(t\) 值全部取反。
所以我们思考操作若干条链来达成目标。
但是不一定有解。在操作之前，我们可以先异或一个值 \(v\)，使得一些层的 \(t\) 值取反。
具体的，枚举最后一层（不是叶子，是叶子上面的一层）是否先提前取反，然后依次往上枚举每一层。
设 \(d_u\) 表示被链覆盖的次数的奇偶性，有 \(d_u = d_{lson(u)}\operatorname{xor} d_{rson(u)}\)，合法的条件为 \(d_u\operatorname{xor} t_u = 0\)。
如果该层全部点都满足 \(d_u\operatorname{xor} t_u = 1\)，那么先提前把这一层所有 \(t\) 取反。
然后这题就做完了，操作次数显然远远小于 \(10^6\)。
点击查看代码
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define fi first
#define se second
#define pir pair <ll, ll>
#define mkp make_pair
#define pb push_back
using namespace std;
const ll maxn = 3e5 + 10, mod = 1e9 + 7;
ll n, a[maxn], b[maxn], ans[maxn << 2], len;
ll trie[maxn * 18][2], tot = 1, t[maxn * 18], fa[maxn * 18];
vector <ll> vec[20];
void dfs(ll bit, ll u, ll v, ll uw, ll vw) {
if(bit == n) {
if(b[uw] != vw) {
puts("No");
exit(0);
} return;
}
if(b[uw] & (1 << bit)) {
dfs(bit + 1, trie[u][0], trie[v][1], uw, vw | (1 << bit));
dfs(bit + 1, trie[u][1], trie[v][0], uw | (1 << bit), vw);
t[u] = 1;
} else {
dfs(bit + 1, trie[u][0], trie[v][0], uw, vw);
dfs(bit + 1, trie[u][1], trie[v][1], uw | (1 << bit), vw | (1 << bit));
}
}
ll tag;
ll query(ll u) {
ll val = 0;
for(ll i = n - 2; ~i; i--) {
val |= (trie[fa[u]][1 ^ ((tag >> i) & 1)] == u) << i;
u = fa[u];
} return val;
}
void add1() {
ll p = 1;
for(ll i = 0; i < n; i++) {
swap(trie[p][0], trie[p][1]);
p = trie[p][(tag >> i) & 1];
}
}
ll msk, d[maxn * 18], ok;
int main() {
scanf("%lld", &n); vec[0].pb(1);
for(ll i = 0; i < (1 << n); i++) {
scanf("%lld", a + i); b[a[i]] = i;
ll p = 1;
for(ll j = 0; j < n; j++) {
ll c = (a[i] >> j) & 1;
if(!trie[p][c]) {
trie[p][c] = ++tot;
vec[j + 1].pb(tot);
fa[tot] = p;
}
p = trie[p][c];
}
}
dfs(0, 1, 1, 0, 0);
for(ll i = 0; i < 2; i++) {
msk = (i << n - 1), ok = 1;
for(ll j: vec[n - 1]) d[j] = t[j] ^ i;
for(ll j = n - 2; ~j; j--) {
ll x = 0, gd = 0;
for(ll k: vec[j]) {
d[k] = t[k] ^ x;
if(d[k] ^ d[trie[k][0]] ^ d[trie[k][1]]) {
if(gd) {
ok = 0;
break;
}
x = 1, d[k] ^= 1;
}
gd = 1;
}
msk |= (x << j);
if(!ok) break;
}
if(!ok) continue;
ans[++len] = tag = msk;
for(ll j: vec[n - 1])
if(d[j]) {
ll val = query(j);
val ^= (1 << n - 1) - 1;
ans[++len] = val, tag ^= val;
add1(), ans[++len] = -1;
}
ans[++len] = tag ^ msk;
puts("Yes");
printf("%lld\n", len);
for(ll i = 1; i <= len; i++)
printf("%lld ", ans[i]);
return 0;
}
puts("No");
return 0;
}