题目链接：传送门
题目大意：
两个长度为n的二进制串s，t，每次操作可以将s串的一段区间取反。求操作exactly twice后使得s=t的方法数。
思路：
连续的尽可能长的 s ≠ t 的区间简称A，连续的尽可能长的 s = t 的区间简称B。
则1-n可以划分为若干个AB交替出现，要求操作exactly twice后s=t，就是消去所有的A。
发现每次操作最多只能使得A的数量减少1个。
所以若对于给出的s，t：
① cnt(A) ≥ 3：
不能完成，方法数为0。
② cnt(A) = 2：
有2 × 3 = 6种：（下划线表示反转，顺序对调就翻一倍）
1）ABA + ABA
2）ABA + ABA
3）ABA + ABA
③ cnt(A) = 1：
只要第一次操作能使得A的数量还是1即可：
1）把A分两次翻转，有2 × (len(A)-1)种；
2）翻转B的一段+A，有2 × (N-len(A))种；
④ cnt(A) = 0：
此时整个1-n为B，任意取一段区间翻两次，有n × (n+1) / 2种。
代码：
#include <bits/stdc++.h> using namespace std;
typedef long long ll;
const int MAX_N = 1e6 + ; char s[MAX_N], t[MAX_N]; int main()
{
int T;
cin >> T;
while (T--) {
int N;
scanf("%d", &N);
scanf("%s%s", s+, t+);
int l, r, cntdif = ;
for (int i = ; i <= N; i++) {
if (s[i] != t[i]) {
cntdif++;
if (cntdif == )
break;
l = r = i;
while (i+ <= N && s[i+] != t[i+]) {
r++;
i++;
}
}
}
if (cntdif == ) {
puts("");
}
else if (cntdif == ) {
puts("");
}
else if (cntdif == ) {
int len = r-l+;
ll ans = ;
ans += (len-)*;
ans += (N-len)*;
printf("%lld\n", ans);
}
else if (cntdif == ) {
ll ans = 1LL * N * (N+)/;
printf("%lld\n", ans);
}
// puts("");
}
return ;
}
/*
10
1
1
0
2
00
11
5
01010
00111
3
111
111
7
1010101
1111111
*/