记录编号	578529	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[USACO23 Jan Gold] Light Off	最终得分	100
用户昵称	yrtiop	是否通过	通过
代码语言	C++	运行时间	3.078 s
提交时间	2023-03-27 14:19:21	内存使用	21.39 MiB

#include <bits/stdc++.h>
#define pb emplace_back
#define fir first
#define sec second

const int maxn = 21;
const int maxm = 1 << 20;

int n,p[maxn];
bool dp[maxn][maxm];
char s[maxn],t[maxn];

int shift(int x) {
    return (x >> 1) | ((x & 1) << (n - 1));
}

void work() {
    scanf("%s %s",s,t);
    int S = 0,T = 0;
    for(int i = 0;i < n;++ i)
		S = (S << 1) | (s[i] ^ '0'),T = (T << 1) | (t[i] ^ '0');
    int now = 0;
    for(int i = 0;i <= n;++ i) {
        if(dp[i][S ^ now])
            return printf("%d\n",i),void();
        now = shift(now) ^ T;
    }
    return ;
}

int main() {
	freopen("lightoffg.in","r",stdin);
	freopen("lightoffg.out","w",stdout);
    int T;
    scanf("%d %d",&T,&n);
    dp[0][0] = true;
    memset(p , 0 , sizeof(p));
    for(int i = 0;i < n;++ i) {
        for(int j = 0;j < n;++ j)
            p[j] = shift(p[j]) ^ (1 << j);
        for(int S = 0;S < (1 << n);++ S) {
            if(!dp[i][S])
                continue ;
            for(int j = 0;j < n;++ j)
                dp[i + 1][S ^ p[j]] = true;
        }
    }
    while(T --)
        work();
    return 0;
}