一道比较深刻的题目。
考虑条件相当于：对于任意 \(1\) 的个数有限的 \(S\)，其所有的长度为 \(2k+1\) 的子串，经过 \(p\) 的映射后 \(1\) 的个数不变。
- 统计所有的长度固定的子串信息，我们有一个 trick：对于一个长为 \(2k+1\) 的二进制串 \(w\)，设其前 \(2k\) 位和后 \(2k\) 位组成的串为 \(x,y\)，我们连边 \(x\to y\)。
我们需要统计 \(1\) 的个数的信息，于是我们令 \(x\to y\) 的边权为：新产生的 \(S\) 的 \(1\) 的个数减去新产生的 \(S'\) 的 \(1\) 的个数。
问题变为我们可以在图上跑任意次，但必须满足所有边权和为 \(0\)。
根据鸽巢原理，我们总会找到两个相同的长为 \(2k+1\) 的子串。如果我们把周期循环下去，那么合法的条件是这两个子串之间走的环上的边权和为 \(0\)。
即：我们需要支持判断，是否满足任意环的边权和为 \(0\)。
我们可以建立权值为相反数的反向边，这样只需要判断图中是否存在负环，可以使用 SPFA。
接下来，我们先枚举 \(\text{lcp}(p,q)\)，求出最大可能的 \(\text{lcp}\)。
然后，我们一位一位往后填写，并判断填写 \(0\) 是否合法。
对于后面的位，我们钦定边权和反向边边权都为可能的最大值，这样负环就没能在这上面占到便宜。
但是这样会超时：具体的，设 \(m = 2^{2k}\)，那么时间复杂度为 \(O(m^3)\)。
- Key Observe：注意到图是强连通的，且任何时候 \(dis_u \le 2k\)。当 \(dis_0<0\) 时就说明出现了负环，此时 SPFA 复杂度为 \(O(mk)\)。
点击查看代码
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define pir pair <ll, ll>
#define mkp make_pair
#define fi first
#define se second
#define pb push_back
using namespace std;
const ll maxn = 2e5 + 10;
ll t, k, dis[1 << 10], vis[1 << 10];
char p[maxn], q[maxn];
vector <pir> to[maxn];
queue <ll> que;
ll spfa() {
for(ll i = 0; i < (1 << k); i++) dis[i] = 8e18, vis[i] = 0;
dis[0] = 0;
while(!que.empty()) que.pop();
que.push(0);
while(!que.empty()) {
ll u = que.front(); que.pop();
vis[u] = 0;
for(pir e: to[u]) {
ll v = e.fi, w = e.se;
if(dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
if(dis[0] < 0) return 0;
if(!vis[v]) {
vis[v] = 1;
que.push(v);
}
}
}
}
return 1;
}
ll eq;
int main() {
freopen("transform.in", "r", stdin);
freopen("transform.out", "w", stdout);
scanf("%lld", &t);
while(t--) {
scanf("%lld%s", &k, q);
k <<= 1;
eq = 1;
ll pos = -5;
for(ll i = -1; i < (1 << k + 1); i++) {
if(i < (1 << k + 1) - 1 && q[i + 1] == '1') continue;
for(ll u = 0; u < (1 << k); u++) to[u].clear();
for(ll j = 0; j <= i; j++) {
ll x = j >> 1, y = j & ((1 << k) - 1), t = (j & 1);
to[x].pb(mkp(y, t - (q[j] - '0')));
to[y].pb(mkp(x, (q[j] - '0') - t));
}
if(i < (1 << k + 1) - 1) {
ll x = (i + 1) >> 1, y = (i + 1) & ((1 << k) - 1), t = i & 1 ^ 1;
to[x].pb(mkp(y, t - 1));
to[y].pb(mkp(x, 1 - t));
for(ll j = i + 2; j < (1 << k + 1); j++) {
x = j >> 1, y = j & ((1 << k) - 1), t = j & 1;
to[x].pb(mkp(y, t));
to[y].pb(mkp(x, 1 - t));
}
}
if(spfa()) {
pos = i;
}
}
if(pos == -5) {
puts("-1");
continue;
}
if(pos == (1 << k + 1) - 1) {
puts(q);
continue;
}
for(ll i = 0; i <= pos; i++) p[i] = q[i];
++pos;
p[pos] = '1';
for(ll i = pos + 1; i < (1 << k + 1); i++) {
for(ll u = 0; u < (1 << k); u++) to[u].clear();
ll x, y, t;
for(ll j = 0; j < i; j++) {
x = j >> 1, y = j & ((1 << k) - 1), t = (j & 1);
to[x].pb(mkp(y, t - (p[j] - '0')));
to[y].pb(mkp(x, (p[j] - '0') - t));
}
x = i >> 1, y = i & ((1 << k) - 1), t = i & 1;
to[x].pb(mkp(y, t));
to[y].pb(mkp(x, -t));
for(ll j = i + 1; j < (1 << k + 1); j++) {
x = j >> 1, y = j & ((1 << k) - 1), t = j & 1;
to[x].pb(mkp(y, t));
to[y].pb(mkp(x, 1 - t));
}
if(spfa()) {
p[i] = '0';
} else {
p[i] = '1';
}
}
p[1 << k + 1] = 0;
puts(p);
}
return 0;
}