problem
给两个长为 \(n\) 的 0/1 字符串 \(S,T\)，进行如下操作 \(cnt\) 次：
- 自行选定 \(0\leq x<n\)，使得 \(T_x\) 异或一。
- 将 \(S\) 异或上 \(T\)。
- 将 \(T\) 的最后一位移动到最前面，即如 \(0123\) 变成 \(3012\)。
最小化 \(cnt\) 使得 \(S\) 全为零。\(n\leq 20\)，多测 \(10^5\) 组固定 \(n\)。
solution
我们很容易构造 \(cnt=2n\) 的方案。甚至 \(cnt=n\) 好像也行，我不管。
不考虑这个循环位移。则我们如果固定了 \(cnt\)，那么异或一的操作实际上是将区间 \([x_i,x_i+cnt-i]\) 异或一，对于第 \(i\) 次操作。
我们完全可以倒着做这个操作，让区间的长度递增，则第 \(i\) 次操作变成了：
- 在 \(S\) 上选择一段长为 \(i\) 的区间异或一。
- 目标：使得 \(S\) 清空，如果将 \(S\) 超过 \(n\) 的部分按顺序异或回来，叠起来。
我们再倒过来，我们设 \(F(S,cnt)\) 表示在第 \(cnt\) 步（未做 \(cnt\) 步时），\(S\) 是否有可能通过从 \(0\) 处得到，如果 \(F(S,cnt)\) 为真，则说明 \(T=0\) 时可以用 \(cnt\) 步解决原问题。
假如我们通过一波暗箱操作得到了 \(F\)（注意到 \(cnt\) 是 \(O(n)\) 的），对于询问，我们枚举 \(cnt\)，然后因为原来的 \(T\) 跟着移动，我们让原来的 \(T\) 进行 \(cnt\) 次操作（但不修改），直接改掉 \(S\)，然后询问另外的 \(S\)。
现在考虑如何求 \(F\)，实际上我们可以直接暴力转移，枚举异或区间在哪里，然后异或上去就是了。
code
点击查看代码
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr,##__VA_ARGS__)
#else
#define debug(...) void(0)
#endif
typedef long long LL;
int read(int&len){
static char a[40];
scanf("%s",a+1);
len=strlen(a+1);
int res=0;
for(int i=len;i>=1;i--) res=res<<1|(a[i]-'0');
return res;
}
bool f[1<<20][45];
LL g[20];
LL getfull(int k){return (1ll<<k)-1;}
LL cover(LL S,int n){
while(S>getfull(n)) S^=(S>>n)^(S>>n<<n);
return S;
}
void printbin(int S,int n){
#ifdef LOCAL
for(int j=0;j<n;j++) debug("%d",(S>>j)&1);
#endif
}
void dp(int n){
memset(f,0,sizeof f);
f[0][0]=1;
for(int i=0;i<=n<<1;i++){
// debug("g[%d]:",i);
for(int j=0;j<n;j++) g[j]=cover(getfull(i+1)<<j,n);
// debug("f[%d]:",i);
for(int S=0;S<1<<n;S++){
if(!f[S][i]) continue;
// #ifdef LOCAL
// printbin(S,n);
// debug(",");
// #endif
for(int j=0;j<n;j++) f[S^g[j]][i+1]=1;//fwt exactly
}
// debug("\n");
}
}
struct ask{
int le,S,T,id;
bool operator<(ask b){return le<b.le;}
} q[200010];
int n,m,bua[200010];
int main(){
#ifdef LOCAL
freopen("input.in","r",stdin);
#endif
scanf("%d%d",&m,&n);
dp(n);
for(int i=1;i<=m;i++) q[i].S=read(q[i].le),q[i].T=read(q[i].le),q[i].id=i;
// sort(q+1,q+m+1);
for(int i=1;i<=m;i++){
int n=q[i].le,id=q[i].id,S=q[i].S,T=q[i].T;
// if(q[i].le!=q[i-1].le) dp(n);//一开始以为询问的 n 都不同哈哈哈
for(int&cnt=bua[id]=0;cnt<=n<<1;cnt++){
if(f[S][cnt]) break;
S^=cover(T<<cnt,n);
}
}
for(int i=1;i<=m;i++) printf("%d\n",bua[i]);
return 0;
}