SS241031C. 博弈（game）
题意
博弈的规则是，有 \(3\) 个数字 \(x,y,z\)，每次可以选择其中两个数字 \(x,y\)，改成 \(x',y'\)，满足和不变差严格变小，即 \(x+y=x'+y',|x-y|>|x'-y'|\)。无法操作的失败。给你 \(n\) 个数字，问有多少种选 \(3\) 个数字的方案使得先手必胜。
solution
首先可以设状态 \(x,y,z\) 然后爆搜 \(SG\) 函数，复杂度 \(O(V^4)\) 左右吧。
一个优化是钦定 \(x\le y\le z\)。
这种东西考虑直接打表，输出后手必败的状态，看看有没有什么规律。
赛场上我打了 \(V|3\) 的一些情况，发现对于每个 \(x\in[0,\frac{V}{3}]\)，恰好有一种状态先手必败。且所有 \(x-((\frac{V}{3}-2)\bmod 4)|4\) 的 \(x\) 的先手必败的状态都是 \(x,y=\frac{V-x}{2},z=V-x-y\)，以及一部分 \(x-(\frac{V}{3}\bmod 4)|4\) 的 \(x\) 也满足这种情况。然后其他状态都是形如 \(x,x,V-2x\)。
这样打表可以发现必须要存在两个相等（或者相差 \(1\)？）的数字才有必败态，特殊性质保证所有 \(a_i\) 互不相同，于是我们相信这种情况不存在必败态，直接输出 \(\binom{n}{3}\) 获得 \(15pts\)。
然而我并没有找出可靠的规律。
考虑换一种打表方式。
状态不设三维，其实两维足够了。
钦定 \(x\ge y \ge z\)。
设成 \((a,b)=(x-y,y-z)\)。
终态就是 \(a\le 1\) and \(b\le 1\) and \(a+b\le 1\)。
- 修改 \(x,y\)：\(x'\gets x-1,y'\gets y+1,a>1 \Rightarrow (a',b')=(a-2,b+1)\)
- 修改 \(y,z\)：\(y'\gets y-1,z'\gets z+1,b>1 \Rightarrow (a',b')=(a+1,b-2)\)
- 修改 \(x,z\)：\(x'\gets x-1,z'\gets z+1,a+b>1 \Rightarrow (a',b')=(a-1,b-1)\)
一次操作就是执行若干次修改。
发现修改 \(1,2\) 是对称的，\(a,b\) 也是对称的，因此只考虑一种修改。
干脆钦定 \(a\ge b\)。
其中修改 \(x,z\) 如果改多了会出现 \(x<y\) 或者 \(y<z\) 的情况，也就是出现 \(b<0\)。由于我们钦定了 \(x\ge y\ge z\)，因此此时再继续操作其实是在做上一种操作了。
然后根据惊人的注意力可以发现，如果 \(a,b>0\)，那么状态必胜。因为你可以一直做修改 \(3\)，直到 \(b=0\)，如果此时的状态是必败态，就停止，否则如果此时是必胜状态，就直接模仿必胜态的操作做就可以了。
因此可以证明 \(a_i\) 互不相同的部分分。
接下来我们研究 \(b=0\) 的状态。此时你下一次操作必须使 \(a'=0\)，否则会因为 \(a',b'>0\) 使得后手必胜了。
于是 \(a'=0,b'=\frac{a}{2}\)。然后因为钦定了 \(a\ge b\)，因此得到 \((\frac{a}{2},0)\)。
根据刚刚的结论以及终态，可以得出 \(a\) 的二进制最低的一个 \(1\) 在从低数起偶数位上面，就是必胜状态，否则必败。
那么可以做了，我们用 \(\binom{n}{3}\) 减去必败状态的数量。
把所有数字从低位开始插入 01trie。我们需要求出状态 \(x,x,y\) 满足 \(|x-y|\) 的二进制低位起第一个 \(1\) 在奇数位的方案数。以及三个数字相等的方案数。
在 trie 上数数，遇到一个奇数高度的岔路，分左子树选两个 \(x\)，右子树选一个 \(y\)，和右子树选两个 \(x\)，左子树选一个 \(y\) 计数。以及数三个数字相等的情况。
code
挺好写的。马蜂优良。
#include<bits/stdc++.h>
// #define LOCAL
#define sf scanf
#define pf printf
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x-y;x>=z;x--)
using namespace std;
typedef long long ll;
#define isdigit(x) (x>='0'&&x<='9')
#define gc getchar_unlocked
template <typename T>
void read(T &x) {
x=0;
char ch=gc();
for(;!isdigit(ch);ch=gc()) ;
for(;isdigit(ch);ch=gc()) x=(x<<3)+(x<<1)+ch-'0';
}
constexpr int N=5e5+7;
int t,n;
ll a[N];
ll ans;
ll C(int n,int m) {
if(n<m) return 0;
ll s=1;
rep(i,0,m-1) s=s*(n-i);
rep(i,1,m) s=s/i;
return s;
}
ll s[N<<6];
int son[N<<6][2];
ll s2[N<<6];
int cnt;
void clear() {
rep(i,1,cnt) s[i]=0,son[i][0]=son[i][1]=0;
cnt=1;
}
void insert(ll x) {
int p=1;
rep(k,0,63){
int op=x&1;
if(!son[p][op]) son[p][op]=++cnt;
p=son[p][op];
x>>=1;
}
s[p]++;
}
void dfs(int u,int dep) {
ans-=C(s[u],3);
s2[u]=C(s[u],2);
if(son[u][0]) dfs(son[u][0],dep+1), s[u]+=s[son[u][0]], s2[u]+=s2[son[u][0]];
if(son[u][1]) dfs(son[u][1],dep+1), s[u]+=s[son[u][1]], s2[u]+=s2[son[u][1]];
if(dep&1) ans-=s2[son[u][0]]*s[son[u][1]]+s2[son[u][1]]*s[son[u][0]];
}
void init(){
clear();
ans=0;
}
void solve() {
init();
ans=C(n,3);
rep(i,1,n) insert(a[i]);
dfs(1,1);
pf("%lld\n",ans);
}
int main() {
#ifdef LOCAL
freopen("my2.out","w",stdout);
#else
freopen("game.in","r",stdin);
freopen("game.out","w",stdout);
#endif
read(t);
while(t--) {
ans=0;
read(n);
rep(i,1,n) sf("%lld",&a[i]);
solve();
}
}