题解 CF1320D 【Reachable Strings】
xht
2020-03-03 15:12:51
`011` 和 `110` 可以相互转化，相当于每次可以将每个 `0` 向左右移动两个单位，因此每个 `0` 的位置下标的奇偶性不会变。
但是当出现 `00` 时，左边的 `0` 无法移到右边，右边的 `0` 无法移到左边，也就是**无法跨越奇偶性不同的 `0`**。
换句话说，两个字符串可以相互转化，当且仅当**每个 `0` 所在的位置下标的奇偶性一一对应**。
比如一个字符串中有 $6$ 个 `0`，位置分别在 $1,2,3,4,6,7$，则它一定可以转化为 `0` 的位置分别在 $1,10,101,102,1000,10101$ 的字符串。
那么，每次询问相当于求出一个区间内每个 `0` 在**以这个区间开头为奇下标**时的奇偶性。
我们对这个奇偶性进行 hash，就能快速比较两个区间内的信息是否一致了。
```cpp
#define Hash pair<modint, modint>
const Hash B = mp(131, 13331);
inline Hash operator + (Hash a, Hash b) { return mp(a.fi + b.fi, a.se + b.se); }
inline Hash operator - (Hash a, Hash b) { return mp(a.fi - b.fi, a.se - b.se); }
inline Hash operator * (Hash a, Hash b) { return mp(a.fi * b.fi, a.se * b.se); }
inline Hash operator + (Hash a, int b) { return mp(a.fi + b, a.se + b); }
const int N = 2e5 + 7;
int n, q, c[N];
char s[N];
Hash h[N][2], p[N];
inline Hash H(int l, int r, int o) {
return h[r][o] - h[l-1][o] * p[c[r]-c[l-1]];
}
int main() {
rd(n), rds(s, n), rd(q);
p[0] = mp((modint)1, (modint)1);
for (int i = 1; i <= n; i++) {
if (s[i] != '0') h[i][0] = h[i-1][0], h[i][1] = h[i-1][1], c[i] = c[i-1];
else h[i][0] = h[i-1][0] * B + ('0' + (i & 1)), h[i][1] = h[i-1][1] * B + ('0' + ((i & 1) ^ 1)), c[i] = c[i-1] + 1;
p[i] = p[i-1] * B;
}
while (q--) {
int l1, l2, len;
rd(l1), rd(l2), rd(len);
int r1 = l1 + len - 1, r2 = l2 + len - 1;
prints(H(l1, r1, l1 & 1) == H(l2, r2, l2 & 1) ? "Yes" : "No");
}
return 0;
}
```