XorCards

作者：熊云帆汪乐平

关键字：解方程组，高斯消元线性基

题目简述

输入一个含有 $n$ 个元素的可重集 $A$ 以及一个非负整数 $m$ 。求集合 $A$ 有多少个子集满足集合中所有元素的异或和不大于 $m$ 。 $n$ 小于等于 $50$ ，集合中的元素和 $m$ 小于等于 $10^{15}$ 。

答案可由两部分组成：

对于异或和等于 $m$ 的方案数，我们可以设 $x_{i}$ 表示所取得子集中是否包含第 $i$ 个元素，设 $c_{i,j}$ 表示第 $i$ 个数的第 $j$ 个二进制位，设 $d_i$ 表示m的第 $i$ 个二进制位。

可得方程： $\sum_{i=1}^{50} x_i*c_{i,j}=d_j$

该方程的每一个解即对应一个合法的子集。

对于异或和小于 $m$ 的方案数，设 $a$ 的前 $x$ 个二进制位和 $m$ 相同。

当 $m$ 的第 $x+1$ 个二进制位是 $0$ 时， $a$ 的第 $x+1$ 位只能是 $0$ ，此时无法确定 $a$ 与 $m$ 的大小关系。
当 $m$ 的第 $x+1$ 个二进制位是 $1$ 时，若 $a$ 的第 $x+1$ 位是 $0$ ，则 $a$ 一定小于 $m$ 。若 $a$ 的第 $x+1$ 位是 $1$ ，则 $a$ 不一定小于 $m$ 。

对于一定小于 $m$ 的情况，我们可以根据已经确定的 $x+1$ 位列出方程求出解的个数。对于不一定小于 $m$ 的情况，继续枚举下一位求解。

即我们只需要在 $m$ 中为 $1$ 的二进制位统计答案即可。

解方程的时间复杂度是 $O(n^3)$ 的，一共要解 $O(log_2m)$ 次方程。所以总的时间复杂度是 $O(n^3log_2m)$ 。

时间复杂度： $O(n^3log_2m)$ 。

直接用bitset优化高斯消元可以使得解方程的复杂度降到 $O(n^3/32)$ 。

时间复杂度： $O(n^3log_2m/32)$ 。

都有高斯消元和bitset了怎么可能想不到线性基呢……

求出原数组的线性基，这里的线性基必须消到每一位上最多只有 $1$ 个 $1$ 。把被消出来的 $0$ 加回去再按升序排序，于是我们得到一个 $n$ 个数的单调不降的数组 $b$ 。数组 $b$ 满足两个性质：

$1.$ 原数组所有子集的异或和组成的多重集等于数组 $b$ 所有子集的异或和组成的多重集。

$2.$ 对于 $\forall 1\leq K<2^{n}-1$ ，都满足 $\forall 0\leq i<n$ ， $b[i]$ 在异或和第 $K$ 小的 $b$ 的子集内的充要条件是 $K and 2^{i}=2^{i}$ ，这里的 $and$ 指按位与。

于是我们可以使用按位枚举的方法快速地求出最大的 $K$ 满足 $第K小的异或和\leq m$ 。然后因为这里没有考虑空集，所以答案就是 $K+1$ 。

求线性基的时间复杂度是 $O(nlog_2m)$ ，计算答案的时间复杂度是 $O(n)$ ，所以总的时间复杂度就是 $O(nlog_2m)$ 。