C - Flippy Sequence (思维)

先将两个数组异或一下，这样值为1的位置就需要翻转。

因为要刚好区间翻转两次，分类讨论。

区间翻转显然是一段一段的。

讨论连续1的段数 c n t cnt cnt：

1. c n t = 0 cnt=0 cnt=0：

表示两串相同，肯定要两次翻转相同的区间，而去区间个数显然有 n ( n + 1 ) 2 dfrac{n(n+1)}{2} 2n(n+1)​

2. c n t = 1 cnt=1 cnt=1：

表示整个区间需要由两次翻转区间组成，显然两个区间构成 [ 1 , n ] [1,n] [1,n]且每个区间要存在，有 ( n − 1 ) (n-1) (n−1)种情况，因为顺序不同也算，所以有 ( n − 1 ) × 2 (n-1)times 2 (n−1)×2种。

3. c n t = 2 cnt=2 cnt=2：

111...00000....111 111...00000....111 111...00000....111

有 3 × 2 3times 2 3×2种。

p1：两个区间翻转两段1。

p2：在p1基础上两个区间扩充到0000部分。

p3：第一个区间翻转三段，第二个区间翻转第二段。

然后顺序影响： 3 × 2 = 6 3times 2 =6 3×2=6。

4.其他情况无解。

// Problem: C - Flippy Sequence
// Contest: Virtual Judge - 2018ICPC青岛 [Cloned]
// URL: https://vjudge.net/contest/460901#problem/C
// Memory Limit: 65 MB
// Time Limit: 1000 ms
// Date: 2021-10-05 16:23:09
// --------by Herio--------

#include
using namespace std;
typedef long long ll;
typedef unsigned long long ull; 
const int N=1e6+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define PII pair
#define PLL pair
#define x first
#define y second
#define pb emplace_back
#define SZ(a) (int)a.size()
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define per(i,a,b) for(int i=a;i>=b;--i)
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr) 
void Print(int *a,int n){
	for(int i=1;i>1);
		else if(y==1) printf("%lldn",(n-1)<<1);
		else if(y==2) puts("6");
		else puts("0");
	}
	return 0;
}