GalaxyOJ8699 lolipop

挺高妙的题，思维套结论。

题意：给定 $n$ 个数，求在其中选三个不交的子集，使得其异或和相等的方案数。

三个不交的集合异或和相等 $\Leftrightarrow$ 两两异或和为 $0$ 。

观察两个异或和为 $0$ 的集合 $S,T(\not=\varnothing)$ 和答案有什么关系。

设 $R=S\cap T$ ，则有 $\bigoplus_{i\in R} a_i=\bigoplus_{i\in S\setminus R}a_i=\bigoplus_{i\in T\setminus R}a_i$ 。

再考虑分出来这三个集合被计算了多少遍。发现一共有 $6$ 中不同的 $(S,T)$ 会得到这三个集合，也正好该集合的轮换数量。所以可以看作每对 $(S,T)$ 都对答案产生了 $1$ 的贡献。于是 $A,B,C$ 都不为 $\varnothing$ 的情况就计数完了。

因为三个非空集合的情况已经计数完了，无交的情况就考虑计数 $A,B,C$ 有一个为空集的情况。发现相互包含本质上就是小集合并上另一个集合等于大集合。

和上面类似的，发现每个集合仍然被算了 $6$ 次。

综上，得出结论：最多有一个为 $\varnothing$ 的三元组个数 $=$ 选 $S,T$ 的方案数。

剩下两种情况也很好算，就不展开讲了。

upd：发现其实有一种简单很多的做法……

发现 $A,B,C$ 无交，所以 $(A,B,C)\Leftrightarrow (A\cup B,B\cup C)$ 双射。

所以答案即为 $(S,T)$ 的个数的平方。这是个线性基经典问题，解决。

感谢您的支持，我会继续努力的!