Problem Link

题目大意

给 $2^n-1$ 个动点，权值为 $1\sim 2^n-1$ 的排列，对于每个点，设其左右两边所有点权异或和分别为 $L,R$，那么他会向较大 $L/R$ 较大的一边移动，如果 $L=R$ 则静止不动。

所有点运动速度一定，如果两个点相遇那么他们会合成一个新点，权值为他们的异或和。

在左右无穷点处放两个权值为 $x$ 的静点（$x\in[0,2^n)$）求有多少 $x$ 使得最终所有点都静止。

数据范围：$n\le 18$。

思路分析

注意到权值异或总和为 $0$，因此设前缀异或和为 $s_i$，那么 $i$ 左边和右边的点权异或和就是 $s_{i-1}$ 和 $s_i$。

那么如果两个点 $i,i+1$ 合成之后相当于删掉 $s_i$，这要求 $s_i\ge s_{i-1}$ 且 $s_i\ge s_{i+1}$ 且三个数不全相等。

那么整个排列会不断操作直到所有 $s$ 相等或呈单谷。

如果 $s$ 单谷那么说明谷低左侧的点向左无限运动，必然不合法。

因此我们要使得最终所有 $s$ 相等，显然这个相等的值就是 $\min_{i=1}^n s_i$，那么这些点能静止当且仅当 $s_{\min}\ge x$。

因此我们要计数有多少 $x$ 使得所有 $s_i\oplus x\ge x$，这只要 $s_i$ 最高位不属于 $x$ 即可。

求出所有 $s_i$ 最高位的并，剩下的位可以随便选。

时间复杂度 $\mathcal O(2^n)$。

代码呈现

#include<bits/stdc++.h>
using namespace std;
signed main() {
	int n;
	scanf("%d",&n),n=1<<n;
	int q=n-1;
	for(int i=1,x=0,y=0;i<n-1;++i) {
		scanf("%d",&y),x^=y;
		if(x) q&=~(1<<(31-__builtin_clz(x)));
	}
	printf("%d\n",1<<__builtin_popcount(q));
	return 0;
}