AGC057C 题解

DaiRuiChen007 · 2024-05-06 09:31:30 · 题解

Problem Link

题目大意

给定一个 0\sim 2^n-1 的排列 p_i，每次可以把所有数 +1 后对 2^n 取模或每个数异或上 x，构造一种操作方法，使得 p_i=i。

数据范围：n\le 18。

思路分析

记 m=2^{n-1}，那么一个排列能还原的一个必要条件是 p_{i}\equiv p_{i+m}\pmod m，即 p_i 与 p_{i+m} 的低 n-1 位相同。

可以倒推证明：最终排列满足该性质，且对于两个低 n-1 位相同的数，全体异或或全体 -1 后低 n-1 位依然相同。

那么说明原本的排列也必须满足 p_{i}\equiv p_{i+m}\pmod m。

假如 p_0\sim p_{m-1} 的最高位都是 0，那么唯一的还原方法就是给每个数异或上 p_0，可以证明这种情况下 +1 操作并没有用。

那么我们只要清空每个 p_0\sim p_{m-1} 的最高位，假如 p_i 最高位是 1，我们可以把每个数异或上 \overline {p_i} 使得 p_i=2^n-1 然后全体 +1 即可，此时其他 p_0\sim p_{m-1} 的低 n-1 异或后都不可能是 m-1（另一个低位是 m-1 的元素是 p_{i+m}），然后不断操作就能得到答案，操作数不超过 2^n+1。

只需要一个数据结构维护全局 +1，全局异或和单点查值，用 01-Trie 维护，全局加一相当于把一条链上的点交换左右儿子。

时间复杂度 \mathcal O(n2^n)。

代码呈现

#include<bits/stdc++.h>
using namespace std;
int a[1<<18],n,N;
int p[1<<18],q[1<<18],tg[18]; //ds
void init() {
    for(int i=0;i<N;++i) {
        for(int k=0;k<n;++k) p[i]=(p[i]<<1)|(a[i]>>k&1);
        p[i]|=N;
    }
}
void rev(int x) { //^x
    for(int i=0;i<n;++i) if(x>>i&1) tg[i]^=1;
}
void add() { //+1
    for(int i=0,u=1;i<n;++i) q[u]^=1,u=u<<1|(tg[i]^q[u]);
}
int qry(int u) {
    int y=0,x=p[u];
    for(int i=n-1;~i;--i) {
        y|=((x&1)!=(q[x>>1]^tg[i]))<<i,x>>=1;
    }
    return y;
}
vector <int> opr;
signed main() {
    scanf("%d",&n),N=1<<n;
    int m=N/2;
    for(int i=0;i<N;++i) scanf("%d",&a[i]);
    init();
    for(int i=0;i<m;++i) if(a[i]%m!=a[i+m]%m) return puts("No"),0;
    for(int i=0;i<m;++i) {
        int x=qry(i);
        if(x&m) {
            opr.push_back((N-1)^x),opr.push_back(-1);
            rev((N-1)^x),add();
        }
    }
    opr.push_back(qry(0)),rev(qry(0));
    for(int i=0;i<N;++i) if(i!=qry(i)) return puts("No"),0;
    printf("Yes\n%d\n",(int)opr.size());
    for(int i:opr) printf("%d ",i); puts("");
    return 0;
}