AGC057C Increment or Xor

First 3300! 感觉是个不算太难的 1+1 问题。

首先考察最低位，可以发现加法还是异或对最低位的影响是等价的，那么最低位必须初始就是 $0101\ldots$ 或 $1010\ldots$ ，两者可以通过一次异或互相转换，否则一定无解。

那么可以发现，对于每个数如果我们都不考虑最低位，那么奇数位置和偶数位置的数就分别变成了字问题。因为我们总是可以通过异或最低位来控制让奇数位置还是偶数位置的数加一，而异或的唯一区别就是两个部分必须同时做异或，这个几乎不影响后面的问题。

然后我们可以把最低位删掉，同时把偶数和奇数位的数拿出来，然后分别作为子问题继续做。很显然，如果其中任何一个子问题无解，那么原问题一定无解。

那么两个子问题有解，原问题就一定有解吗？

样例 2 告诉我们并不是这样的，手完可以发现，有可能在递归到下一位后回到第二位时，第二位一边是 $1010$ 另一边是 $0101$ ，此时无论如何都无法让两边都是 $0101$ 了。

但是上面的过程启发了我们，每次进行加一时，其实递归到这个过程的最底层，本质上就是在对最高位的一对 $(i,i+2^{n-1})$ 将 $(1,0)$ 变成 $(0,1)$ 。那么我们其实可以直接模拟这个过程，然后看看是否使得原序列被复原成了 $[0,2^{n}-1]$ 。

也就是说，我们直接枚举每对 $(i,i+2^{n-1})$ ，如果它是 $(1,0)$ ，那么我们就通过一次异或操作让它们的低位同时异或得到 $2^{n-1} - 1$ ，然后执行一次 $+1$ 来变成 $(0,1)$ 。这两个数的低位是一定相同的，否则一定无解（本质上就是在刚才的过程中途就会判出无解）。

现在的问题就是给定一个序列，需要执行 $+1$ 和异或一个值，并且实时询问某个位置的值是多少。这个可以通过维护一个倒着的 Trie 解决，即 $+1$ 就是交换儿子，异或就直接打标记。具体方法有在 044C 中写到。

复杂度 $O(n2^n)$ ，实际操作次数不超过 $2^n + 1$ 。

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
const int MAXN = 5e5 + 20;
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
const int P = 1e9 + 9;
int n;
int A[MAXN];

int son[MAXN * 20][2] , wf[MAXN * 20] , fa[MAXN * 20] , cnt = 1;
int nd[MAXN] , val;

void add( int u = 1 , int dep = 0 ) {
    swap( son[u][0] , son[u][1] );
    swap( wf[son[u][0]] , wf[son[u][1]] );
    if( dep == n - 1 ) return;
    add( son[u][( val >> dep ) & 1] , dep + 1 );
}

int gv( int u , int dep = n - 1 ) {
    if( dep == -1 ) return 0;
    return gv( fa[u] , dep - 1 ) | ( wf[u] << dep );
}

void solve() {
    cin >> n;
    rep( i , 0 , ( 1 << n ) - 1 ) {
        scanf("%d",A + i);
        int cur = 1;
        rep( k , 0 , n - 1 ) {
            int tw = ( A[i] >> k ) & 1;
            if( !son[cur][tw] ) ++ cnt , son[cur][tw] = cnt , fa[cnt] = cur , wf[cnt] = tw;
            cur = son[cur][tw];
        }
        nd[i] = cur;
    }
    int N = 1 << n;

    vi ops;

    for( int i = 0 ; i < N / 2 ; ++ i ) {
        if( !( A[i + N / 2] >> n - 1 ) ) {
            int x = gv( nd[i + N / 2] ) ^ val , v = ( ( x & ( 1 << n ) - 1 ) ^ ( 1 << n ) - 1 );
            val ^= v;
//            cout << v << endl;
            ops.pb( v ) , ops.pb( -1 );
            add( );
        }
    }

    int v = ( gv( nd[0] ) ^ val );
    val ^= v;
    ops.pb( v );


    rep( i , 0 , N - 1 ) {
        if( ( gv( nd[i] ) ^ val ) != i ) {
            puts("No"); exit( 0 );
        }
    }
    puts("Yes");
    cout << ops.size() << endl;
    for( int x : ops ) printf("%d ",x); puts("");
}

signed main() {
//    int T;cin >> T;while( T-- ) solve();
    solve();
}