CF2155C

cjdstttttt

2025-10-06 04:07:52

发布于：广东

34阅读

0回复

0点赞

神人诈骗题。

假设第 $i$ 个巫师面向的方向为 $B_i(B_i\in\{0,1\})$ ，则根据题意可以列出如下方程：

$\begin{equation*} \begin{cases} B_2+B_3+...+B_n=A_1\\ (1-B_1)+B_3+B_4+...+B_n=A_2\\ (1-B_1)+(1-B_2)+B_4+B_5+...+B_n=A_3\\ \vdots \end{cases} \end{equation*}$

情况数就是解的数量。

注意到解的数量不超过 $2$ ，所以那个对 $676767677$ 取模毛用没有。

注意到当 $A_1=A_2=A_3=...=A_n=\frac{n+1}{2}$ 时，方程有两个解，其余时候最多只有一个解。

我们可以特判掉两个解的情况。

然后考虑如何解这个方程。

注意到 $1$ 式与 $2$ 式差别就在于 $B_2$ 与 $(1-B_1)$ ，然后因为 $B_i$ 的范围可得出 $A_1,A_2$ 的差的绝对值应不超过 $1$ ，而且 $A_1,A_2$ 相等时， $B_2=1-B_1$ ，否则 $B_2=B_1$ 。

同理，也可以推出 $B_i$ 与 $B_{i-1}$ 的关系。

然后注意了，需要验证这些解成不成立！

我们分别假设 $B_1=0,1$ ，判断等式成不成立即可。如果其中一个成立，则说明有一个解，否则说明没有解。

// 哇还有解方程环节 
// 666解不出来 
// a_i一定是连续的 
#include <iostream>
#include <cstdio>
#define int long long
using namespace std;
const int mod = 676767677;
int a[100005];
int b[100005];
int pre[100005];
int n;
bool check(){
	for(int i = 1; i <= n; i++) pre[i] = 0;
	for(int i = 1; i <= n; i++){
		pre[i] = pre[i - 1] + b[i];
	}
	for(int i = 1; i <= n; i++){
		if(pre[n] - pre[i] + i - pre[i - 1] != a[i]) return 0;
	}
	return 1;
}
void solve(){
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i];
	bool flag = 1;
	if(n % 2 == 0) flag = 0;
	for(int i = 1; i <= n; i++){
		if(i > 1 && abs(a[i] - a[i - 1]) > 1){
			cout << "0\n";
			return;
		}
		if(a[i] != n / 2 + 1) flag = 0;
	}
	if(flag){
		cout << "2\n";
		return;
	}
	for(int i = 2; i <= n; i++){
		if(abs(a[i] - a[i - 1]) == 1){
			b[i] = b[i - 1];
		}else b[i] = b[i - 1] ^ 1;
	}
	if(check()){
		cout << "1\n";
		for(int i = 1; i <= n; i++){
			b[i] = 0;
		}
		return;
	}
	for(int i = 1; i <= n; i++){
		b[i] ^= 1;
	}
	if(check()){
		cout << "1\n";
		for(int i = 1; i <= n; i++){
			b[i] = 0;
		}
		return;
	}
	cout << "0\n";
	for(int i = 1; i <= n; i++){
		b[i] = 0;
	}
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int t;
	cin >> t;
	while(t--) solve();

	return 0;
}