2023 ICPC 网络赛 第一场（补题：F）

7题罚时879， 队排235，校排79。
除了I题dp没注意空间限制第一发没有用滚动数组MLE，以及G题启发式合并脑抽用set当容器T一发，以及K没注意是平方的期望白wa4发这些应当避免的失误外，基本满意。剩下的题基本都是当时写不出的了，在这里补一发F的题解。

本题解学自：知乎-CurryWOE

F. Alice and Bob（博弈 + 计数）

很妙的一个博弈思维题，并没有多难的算法，只是利用了题目的性质与博弈的基本思想，以及巧妙的计数方法，但实际比赛中还是很难想到的，银牌题中上的难度。

题意

给定大小为 $n$ 的数组 $a$，Alice先手，两人轮流走步，每次可以选择两个数 $a_i,a_j$，将其任意改变（只能变为整数），设改变后为 $a_{i_2},a_{j_2}$，要求改变后满足 $a_i+a_j=a_{i_2}+a_{j_2}$，且 $|a_i-a_j|<|a_{i_2}-a_{j_2}|$. 最后不能走步的人输。
为了帮助Alice胜利，你可以选择保留任意 $3$ 个数，移除其他数，问有多少方案使得Alice必胜。

思路

以上规则翻译过来就是，每次选的两个数必须使得两者差距变小，这样我们发现答案与数的大小无关，只与数的相对大小有关。于是我们可以分情况讨论什么样的三元组使得Alice必胜或必败。

设三元组为 $(x,y,z)(x\le y\le z)$. 因为只与相对大小有关，可以通过平移转换为 $(0,x,x+y)$，并且若 $x>y$ 可以对称转换一下，使得 $x<y$ 例如：$(0,3,5)\to (-5,-3,0)\to (0,2,5)$.

接下来要用到博弈的思想：
1.所有终止状态都为必败态。
2.只要能转移到必败态的状态就是必胜态。
3.只能转移到必胜态的状态就是必败态。

分情况讨论

1. $x>0,y>0$，三元组为 $(0,x,x+y)$
   我们考虑该三元组的下一个状态，有两种可能即 $(y,x,x)$ 或者 $(x+k,x,y-k)$. 再考虑状态 $(y,x,x)$ 的后继，只能为 $(x+k,x,y-k)$.
   若 $(y,x,x)$ 为必败态，则当前状态可以转移到该必败态，当前为必胜态。
   若 $(y,x,x)$ 为必胜态，由于其只有一个后继，说明该后继一定为必败态，而当前状态又能转移到该必败态，当前状态同样必胜。
   综上，$(0,x,x+y)$ 一定为必胜态。

2. $x>0,y=0/x=0,y>0$，三元组为 $(0,0,x)$（$x>0$）
   为何 $(0,x,x)$ 同样为该状态，还是考虑平移与对称变化：$(0,x,x)\to (-x,0,0)\to (x,0,0)$. 而 $y>0$ 的情况因为只是一个变量名，将其名称与 $x$ 交换即可。
   （1）若 $x$ 为奇数当前状态的后继最多为 $(0,\lfloor \frac{x}{2}\rfloor ,\lceil \frac{x}{2}\rceil )$ 即可以表示为 $(0,x,y)(x<y)$. 而情况1 已经证明了该后继状态为必胜态，则当前状态为必败态。
   （2）若 $x$ 为偶数当前状态后继若选择变为 $(0,x,y)$，则必败。考虑另一种情况即将 $x$ 一分为二变为 $(0,\frac{x}{2},\frac{x}{2})$，此时我们发现又一次变为了情况2，说明这是一个递归的过程，而答案只与 $x$ 包含的 $2$ 的幂次有关。
   综上归纳整理有：若 $x$ 包含的 $2$ 的幂次为偶数先手必败，否则先手必胜。

合并起来看：

1. 三元组 $(x,y,z),(x<y<z)$，必胜。
2. 三元组 $(x,y,z),(x=y/y=z)$，若 $(z-x)$ 包含的 $2$ 的幂次为偶数必败，否则必胜。
3. 三元组 $(x,y,z),(x=y=z)$，必败。

现在我们考虑如何计数，直接求必胜态数量不好求，我们考虑容斥求出必败态数量再用总数减去。情况3的必败态数量很好求，我们只需要考虑情况2的。
遍历所有数，设当前数为 $x$，那么我们只需要求 $(p,x,x)(x>p)$ 和 $(x,x,z)(z>x)$ 三元组中满足 $x-p$ 和 $z-x$ 包含的 $2$ 的幂次为偶数的个数即可，可以考虑用01字典树来维护。
$2$ 的幂次的奇偶只与数末尾 $0$ 的个数的奇偶有关，而二进制减法中 $x-y=z$，$z$ 末尾的第一个 $1$ 出现在 $x,y$ 从末尾开始第一个数字不同的数位，我们倒序将数的数位插入字典树，查询数目后就是简单的组合数学问题了。
时间复杂度为 $O(nlogn)$，对于 $n\le 5e5,\sum n\le 3e6$ 的数据范围还是很轻松能通过的。
具体实现见代码，有详细注释。

代码

/*
1. 三元组 (x,y,z),(x<y<z)，必胜。
2. 三元组 (x,y,z),(x=y/y=z)，若 (z - x) 包含的 2 的幂次为偶数必败，否则必胜。
3. 三元组 (x,y,z),(x=y=z)，必败。 
*/
#include <bits/stdc++.h>
using namespace std;#define ll long long
const int N = 5e5 + 10;ll a[N];
int son[N * 62][2], cnt[N * 62], tot;
void clear(int p){if(son[p][0]) clear(son[p][0]);if(son[p][1]) clear(son[p][1]);son[p][0] = son[p][1] = cnt[p] = 0;
}void insert(ll x){int p = 0;for(int i = 0; i <= 60; i ++){ // 倒序插入int u = x >> i & 1;if(!son[p][u]) son[p][u] = ++ tot;p = son[p][u];cnt[p] ++;}
}ll search(ll x, int idx, int p, int ode){ // 查询的数x, 当前数位，字典树地址， 奇偶性ll sum = 0;int u = x >> idx & 1;if(son[p][!u] && !ode){ // 下一位数不同，且当前0的个数为偶数，即为差包含偶数次2的幂次，加入答案sum += cnt[son[p][!u]];}if(son[p][u]) sum += search(x, idx + 1, son[p][u], ode ^ 1); // 继续搜索return sum;
}ll C2(ll sum){ // C(sum, 2)return sum * (sum - 1) / 2LL;
}
ll C3(ll sum){ // C(sum, 3)return sum * (sum - 1) * (sum - 2) / 6LL;
}void solve(){int n;cin >> n;clear(0); tot = 0;for(int i = 1; i <= n; i ++){cin >> a[i];insert(a[i]);}sort(a + 1, a + 1 + n);ll ans = C3(n); // 总方案数for(int i = 1, r = 1; i <= n; i ++){while(r + 1 <= n && a[r + 1] == a[i]) r ++;ans -= C2(r - i + 1) * search(a[i], 0, 0, 0); // 情况2的必败数ans -= C3(r - i + 1); // 情况3的必败数i = r;}cout << ans;
}int main(){ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);int t;cin >> t;for(int i = 1; i <= t; i ++){solve();if(i != t) cout << "\n";}return 0;
}