(2024NOV6th,MAGA!!!!)

金组难度巅峰了。

题意

给定 $T$ 对长度为 $n$ 的 $01$ 序列 $a$ 和 $b$。定义一次操作为：

1. 选择 $b$ 中一个元素，并取反。
2. $a \oplus b \to a$（$\oplus$ 表示按位异或）。
3. 将 $b$ 右旋一位。

问最少多少次操作能使 $a$ 全部变成 $0$。

心路历程

看错好几次题......需要注意一次操作是指完整执行三个步骤。

一开始想建图。考虑所有可能的 $2^n$ 种 $01$ 序列 $s$，$t$ 为 $s$ 挑一个位置取反并右旋一位的可能序列（显然有 $n$ 个），每个 $s$ 都向 $t$ 建有向边。所求的是一条长度最短且途径序列异或和为 $a$ 的路径。然后就发现好像只是给爆搜加了个好听的名字，这个图不怎么特殊，也没有发现什么性质，至此本题思考方向可以说完全跑偏。

好啦看题解。

正解

先形式化地写一下题目的条件。设总共做了 $k$ 次操作，记 $b^x$ 为做了 $x$ 次操作后的 $b$ 序列。

则题目条件为：$(\oplus_{x=1}^{k} b^x) \oplus a =0$。

写完了之后就发现，由于 $a$ 是给定的，实际上只需要关注 $(\oplus_{x=1}^{k} b^x)$ 即可，因此以下分析均忽略步骤二。

观察一：只有第一个步骤是不确定的。

这给我们启发：可以将第一个步骤与第三个步骤分开处理。第三个步骤很简单，做了 $i$ 次操作就直接把 $b$ 右旋 $i$ 次即可。所以考虑步骤一对最终结果的贡献。

观察二：步数的上限是 $3 \times n$。

先把 $b$ 全部变成 $0$（最多 $n$ 次），再对于现在 $a$ 中每个为 $1$ 的位置，对对应的 $b$ 中位置取反（这样 $b$ 中就有且仅有了一个 $1$），再将 $b$ 变为全 $0$（最多 $n$ 轮，每轮要 $2$ 次操作）。故上限为 $3\times n$。

观察三：记将 $b$ 右旋 $d$ 次的结果为 $d(b)$，第 $i$ 次操作选择取反的位置为 $pos_i$。若总共进行 $k$ 次操作，则 $(\oplus_{x=1}^{k} b^x)$ 等于 $\oplus_{x=1}^{k} x(b)$ 对以下区间（旋转意义下，以下分析均是）取反的结果。

$$[pos_1,pos_1+k-1] \\ [pos_2,pos_2+k-2] \\ \dots \\ [pos_i,pos_i,+k-i]\\ [pos_k,pos_k]$$

本题最重要的一个观察，下图很直观的说明了这一事实。（来自 @2017gdgzoi999）

所以我们实际上只需要维护 $i$ 步之后，哪些区间可能会被取反即可。对 $\oplus_{x=1}^{k} x(b)$ 进行取反后可能的结果就可以覆盖所有的结果。

接下来就到了 dp 的部分，考虑状压 dp。记 $f_{i,j}$ 表示 $j$ 状态能不能恰好在第 $i$ 次操作出现。$j$ 的二进制数的第 $x$ 位表示位置 $x$ 有/没有被取反。

感觉我说的不是很清楚。给个例子： $f_{1,(110)_2}=0$ 就表示第一次操作后，不可能让第一位取反，第二位取反，第三位不取反的状态出现。

初始：$f_{0,0}\gets 1$

转移：$f_{i,j}\gets\lor f_{i-1,k}$，其中 $k$ 表示对 $j$ 的第 $[pos,pos+i-1](1\le pos\le n)$ 位取反的结果。

这个转移就是每次都去补第一次操作，相当于第一次选择对 $pos$ 取反。由观察三，这对第 $i$ 次操作的影响相当于在第 $2$ 至第 $i$ 次的结果上（即 $k$），再对 $[pos,pos+i-1]$ 取反（即 $j$ ）。

由于步数的上限为 $O(n)$ 级别的，这样就有了一个 $O(n^2 \times 2^n)$ 的 dp。实际上，这个复杂度仍有优化空间。

观察四：若状态 $x$ 是状态 $x'$ 右旋一位的结果，那么 $f_{i,x}=f_{i,x'}$。进一步地，如果 $x$ 能由 $y$ 右旋达到，则 $f_{i,x}=f_{i,y}$。

我们只需要将每一次操作取反的位置全部向右移一位，这样所有对应的区间也都会右移一位。由于初始状态为全 $0$，所以区间右移就等同于将最终结果右移一位。下图直观地说明了这一事实。

而且可以发现，这一结论是等价关系。即若 $x$ 与 $y$ 能右旋达到，$f_{i,x}=1 \iff f_{i,y}=1,f_{i,x}=0 \iff f_{i,y}=0$。

这样的话，对于 $2^n$ 种总状态，我们可以把每 $n$ 个右旋能互相达到的状态分为一类，这样就会得到 $\frac{2^n}{n}$ 个等价类。对于每个等价类，随意选取其中一个代表状态 $j$ 进行完整转移（代码实现中选取的是最小的一个），等价类中其余的项直接从 $j$ 转移过来即可。形式化地写一下，记对 $x$ 的第 $[s,t]$ 位取反的结果为 $\operatorname{rev}(x,s,t)$。如果将 $j$ 所在等价类选取的代表状态记为 $rep_j$，有：

$$\begin{cases} f_{i,j} \gets \lor_{k=1}^{k\le n }f_{i-1,\operatorname{rev}(j,k,k+i-1)} & j= rep_j \\ f_{i,j} \gets f_{i,rep_j} & j\ne rep_j \end{cases}$$

这样我们就得到了一个 $3 \times n \times ({2^n\over n} \times n + {(n-1)2^n\over n})=O(n\times 2^n)$ 复杂度的 dp。

接下来考虑如何查询答案，有了以上的分析，这是很简单的。记步数为 $d$，记 $b$ 右旋 $d$ 次的结果为 $d(b)$。由题目条件 $(\oplus_{x=1}^{k} b^x) \oplus a =0$ 与观察三，实际上有 $\oplus_{x=1}^{d} x(b)\oplus j\oplus a=0$，其中 $j$ 表示对某些位置取反。化简一下，$j=\oplus_{x=1}^{d} x(b) \oplus a$。我们的 dp 就派上用场了。如果说 $f_{d,j}=1$ ，就说明可行。从小到大枚举步数 $d$ ，找到的最小的可行 $d$ 就是答案。由于步数为 $O(n)$ 级别的，则每次询问时间为 $O(n)$。

综合以上，加上 dp 预处理的时间。总时间复杂度 $O(n\times 2^n + n \times T)$ 可以通过本题。

（状压 dp 好题啊，藏得很深，并不套路。）

代码

#include <bits/stdc++.h>
using namespace std;
#define Tp template<typename T>
#define Ts template<typename T,typename... _T>
char buf[1<<20],*p1=buf,*p2=buf;
#define getchar() (p1==p2&&(p2=buf+fread(p1=buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
Tp inline void read(T& x){
    x=0;char c=getchar();bool f=0;
    for(;!isdigit(c);c=getchar())if(c=='-')f=1;
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    f&&(x=-x);
}
Ts inline void read(T& x,_T&... y){read(x),read(y...);}
const int N=25,K=(1<<20);
bool f[N*4][K];
int n,rp[K];
int _rotate(int x){//右旋一位
    return ((x&1)<<(n-1))|(x>>1);
}
vector <int> rps,oth;
void init(){
    int D=(1<<n);//2^n中状态 
    memset(rp,-1,sizeof rp);
    for(int i=0;i<D;++i){//划分等价类
        if(rp[i]!=-1){
            oth.push_back(i);
            continue;
        }
        rp[i]=i;
        rps.push_back(i);
        int x=_rotate(i);
        while(x!=i){
            rp[x]=i,x=_rotate(x);
        }
    }
    f[0][0]=1;
    for(int i=1,x=0;i<=3*n;++i){//dp转移
    	x^=1<<(i-1)%n; 
        for(int j:rps){
            for(int k=0;k<n;++k,x=_rotate(x)){
                f[i][j]|=f[i-1][j^x];
            }
        }
        for(int j:oth){
            f[i][j]=f[i][rp[j]];
        }
    }
}
void rdbit(int &a){
    char c;
    while((c=getchar())<'0' || c>'1');
    a=c-'0';
    while((c=getchar())>='0' && c<='1'){
        a=(a<<1)|(c-'0');
    }
}
int solve(){
    int a,b;
    rdbit(a),rdbit(b);
    if(a==0) return 0;
    int tmp=b;
    for(int i=1;i<=3*n;++i){
        if(f[i][tmp^a])
            return i;
        b=_rotate(b);
        tmp^=b;
    }
    return -1;
}
int main(){
    int T;
    read(T,n);
    init();//dp
    while(T--)
        cout<<solve()<<'\n';
    return 0;
}