题意:给定n个整数,求满足子集异或和为0的子集大小之和。 题解:相当于求每个数出现在子集中的次数之和。 先对n个数求线性基,设线性基大小为r,可以分别计算线性基内数的贡献和线性基外数的贡献 1.线性基外:共n-r个数,枚举每个数x,将线性基外剩余的n-r-1个数任意排列,显然共有 个集合,这些集合再异或x的结果还是能被线性基异或出,所以x的贡献为 。 2.线性基内:枚举每个数x,将所有剩余的n-1个数再求一次线性基,设为B,分两种情况: (1) x不能被B异或出。那么显然x不能在任意一个集合中出现,x的贡献为0。 (2) x可以被B异或出。此时B的大小必定也为r,因为B已经能表示所有n个数了。...