ZOJ

DreamGrid has just found two binary sequences $s_1, s_2, \dots, s_n$ and $t_1, t_2, \dots, t_n$ ($s_i, t_i \in \{0, 1\}$ for all $1 \le i \le n$) from his virtual machine! He would like to perform the operation described below exactly twice, so that $s_i = t_i$ holds for all $1 \le i \le n$ after the two operations.
The operation is: Select two integers $l$ and $r$ ($1 \le l \le r \le n$), change $s_i$ to $(1 - s_i)$ for all $l \le i \le r$.
DreamGrid would like to know the number of ways to do so.
We use the following rules to determine whether two ways are different:
Let $A = (a_1, a_2, a_3, a_4)$, where $1 \le a_1 \le a_2 \le n, 1 \le a_3 \le a_4 \le n$, be a valid operation pair denoting that DreamGrid selects integers $a_1$ and $a_2$ for the first operation and integers $a_3$ and $a_4$ for the second operation;
Let $B = (b_1, b_2, b_3, b_4)$, where $1 \le b_1 \le b_2 \le n, 1 \le b_3 \le b_4 \le n$, be another valid operation pair denoting that DreamGrid selects integers $b_1$ and $b_2$ for the first operation and integers $b_3$ and $b_4$ for the second operation.
$A$ and $B$ are considered different, if there exists an integer $k$ ($1 \le k \le 4$) such that $a_k \ne b_k$.
Input
There are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case:
The first line contains an integer $n$ ($1 \le n \le 10^6$), indicating the length of two binary sequences.
The second line contains a string $s_1s_2\dots s_n$ ($s_i \in \{\text{‘0’}, \text{‘1’}\}$) of length $n$, indicating the first binary sequence.
The third line contains a string $t_1t_2\dots t_n$ ($t_i \in \{\text{‘0’}, \text{‘1’}\}$) of length $n$, indicating the second binary sequence.
It’s guaranteed that the sum of $n$ in all test cases will not exceed $10^7$.
Output
For each test case, output an integer denoting the answer.
Sample Input
3
1
1
0
2
00
11
5
01010
00111
Sample Output
0
2
6
Hint
For the second sample test case, there are two valid operation pairs: (1, 1, 2, 2) and (2, 2, 1, 1).
For the third sample test case, there are six valid operation pairs: (2, 3, 5, 5), (5, 5, 2, 3), (2, 5, 4, 4), (4, 4, 2, 5), (2, 4, 4, 5) and (4, 5, 2, 4).

题目大意：有两个01相同长度的01串，可以分别对两串执行一次操作，问有多少种方案使得两串在操作后相等。一次操作是指选取某个串的一个区间，将区间中的串按位取反。

解决方案：分情况讨论：

  1. 两个串初始是相等的。
    那么此时，两次操作的区间要相同才能使操作后的两串相等。所以问题变成满足题意得$l,r$有多少种不同得组合。$Ans=(n)+(n-1)+\cdots +(1)=(n+1)*n/2$

  2. 两个串初始只有一个连续的区间不同
    那么此时，操作的目的就是把这段不同的区间变为相同。由于是01串，所以连续的不同的区间操作一次就相同了。设区间$[x,y]$为不相同的区间，如下图所示。

    1
    2
    3
    4
    graph LR
    A((1))--l---B((x))
    B--m---C((y))
    C--r---D((n))

    由于不相同的区间只能操作一次，相同的区间必须呗操作0次或两次，设操作第一个串操作区间在左边，第二个在右边，那么，有三种操作类型。一是第一次操作覆盖$[l,x)$，第二次操作覆盖$[l,y]$，其中$1\leq l <x$，此时有$(x-1)$种可能；二是第一次操作覆盖$[x,r]$，第二次操作覆盖$(y,r]$，其中$y<r\leq n$，此时有$(n-y+1-1)$种可能；三是第一次操作覆盖$[x,m]$，第二次操作覆盖$(m,y]$此时有$(y-x)$种可能。综合三种情况相加，共有$(n-1)$中可能，根据对称性，第二次操作区间在第一次左边也是$(n-1)$种可能，所以$Ans=2*(n-1)$。

  3. 两个串有两个连续区间不相同。画个图数一数固定6种，和长度无关。

  4. 连续不同的区间超过2个。就两次操作机会，不可能还原的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<iostream>
#include<vector>
using namespace std;

char s[1000010], t[1000010];
int T;
long long n;

int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%lld", &n);
		scanf("%s", s);
		scanf("%s", t);
		int Dif = 0, Length = 0;
		bool flag = false;
		for (int i = 0; i < n; ++i) {
			if (s[i] == t[i]) {
				if (Length != 0) {
					++Dif;
					Length = 0;
				}
			}
			else {
				++Length;
			}
		}
		if (Length != 0) {
			++Dif;
		}
		switch (Dif)
		{
		case 0: {
			printf("%lld\n", n * (n + 1) / 2);
			break;
		}
		case 1: {
			printf("%lld\n", 2 * (n - 1));
			break;
		}
		case 2: {
			puts("6");
			break;
		}
		default: {
			puts("0");
			break;
		}
		}
	}
}