Flippy Sequence

Sample Input

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).

题意描述：

给出两个长度为n的01串，通过一种变化，每次可将一个连续区间里的0变为1，1变为0。求若经过两次这种变化，使得两个01串完全相同共有多少中方法。

解题思路：

将两个01串通过按位异或，得到一个新的01串，0代表此位置两个01串相同，1代表此位置两个01串不同。通过按位异或得到的01串其中0可经过两次变化还为0，即此位置还是相同的，1可经过一次变化，此位置变为相同。通过找规律可知，因求的是经过两次变化01串相同的方法，若1被分为三段或三段以上则经过两次无法实现使得两个01串相同。若1被分为两段，可知共有6种方法；当1只有一段且含有0段时，共有（n-1）*2种方法；当全为0时共有（n+1）*n/2方法；当全为1时共有(n-1)*2种方法。

程序代码：

#include<stdio.h>
#define N 1000020
char a[N],b[N];
int c[N];
int main()
{
	long long t,n,i,sum,temp;
	scanf("%lld",&t);
	while(t--)
	{
		sum=0;
		scanf("%lld",&n);
		scanf("%s %s",a,b);
		for(i=0;i<n;i++)
		{
			c[i]=(a[i]-'0')^(b[i]-'0');
			sum+=c[i];
		}
		if(sum==n)
		{
			printf("%lld\n",(n-1)*2);
			continue;
		}
		if(sum==0)
		{
			printf("%lld\n",n*(n+1)/2);
			continue;
		}
		temp=0;
		if(c[0]==1)
			temp++;
		for(i=1;i<n;i++)
		{
			if(c[i]==1&&c[i-1]!=1)
				temp++;
			if(temp>2)
				break;
		}
		if(temp>2)
		{
			printf("0\n");
			continue;
		}
		if(temp==1)
		{
			printf("%lld\n",(n-1)*2);     
		}
		else if(temp==2)
		{
			printf("6\n");
		}
	}
	return 0;
}