自动搬运

查看原文

来自洛谷，原作者为

	Mivik AFO

搬运于2025-08-24 22:30:42，当前版本为作者最后更新于2021-04-15 23:54:00，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

Subtask 1

一共只有 $n$ 种选择方案，直接统计并输出即可。

Subtask 2

记 $f_{i,j,k}$ 为考虑了前 $i$ 个数，用到了 $j$ 个，异或值为 $k$ 的方案数。直接 $O(2^wn^2)$ 暴力转移即可。

Subtask 3

先不考虑不能选同一个数的条件，那么令 $c_i$ 为 $i$ 在给定的数中的出现次数，答案就是 $c*c$（$*$ 是异或卷积）。用 $\mathrm{FWT}$ 算出这个后我们再减去选到同一个数的情况就好了。

Subtask 4

下文我们令 $L=2^w$。定义一个序列的权值向量为一个长度为 $L$ 的向量，其中序列的第 $i$ 位为 $i$ 在原序列中出现的次数；并额外定义一个数 $c$ 的权值向量就是 $[c]$ 的权值向量。那么 $k$ 个数的异或就是它们的权值向量 $\mathrm{FWT}$ 后逐位相乘再 $\mathrm{FWT}$ 回去。然后我们对这个向量逐位考虑。根据 $\mathrm{FWT}$ 的定义我们知道

$$\mathrm{FWT}(v)_i=\sum_{j=0}^{L-1}(-1)^{\mathrm{pop}(i\&j)}v_j $$

其中 $\mathrm{pop}(v)$ 是 $v$ 二进制下 $1$ 的个数，$i\&j$ 是位与（Bit-And）运算。其次我们知道 $\mathrm{FWT}$ 是一个线性变换，也就是说 $\mathrm{FWT}(a)+\mathrm{FWT}(b)=\mathrm{FWT}(a+b)$，我们要算答案可以把所有情况的 $\mathrm{FWT}$ 加起来得到答案的 $\mathrm{FWT}$。

不难发现一个正整数的权值向量 $\mathrm{FWT}$ 后每一项只能是 $\pm1$。对于答案 $\mathrm{FWT}$ 中的每一个位置，我们相当于是要从一些 $1$ 和 $-1$ 中选出 $m$ 个，然后算乘积，并对所有方案求和。假设我们知道这一个位置上有 $a$ 个 $-1$，$(n-a)$ 个 $1$，于是答案的 $\mathrm{FWT}$ 上这一位的值就是

$$\begin{aligned} &[x^m](1-x)^a(1+x)^{n-a}\\ =&\sum_{i=0}^m(-1)^i\binom ai\binom{n-a}{m-i} \end{aligned} $$

这个可以 $O(m)$ 计算。现在问题是我们怎么对每一个位置都算出 $a$。不难发现每一个位置上面数的和是

$$s_i=\sum_{j=1}^n(-1)^{\mathrm{pop}(i\&v_j)}$$

这个是可以一遍 $\mathrm{FWT}$ 算出来的，然后解一下方程就可以知道 $a$ 了。于是我们就可以 $O(Lm)$ 得到答案的 $\mathrm{FWT}$，然后 $O(Lw)$ 得到答案。总时间复杂度 $O(Lm)$。

Subtask 5

不难发现我们可以对每一个可能的 $a$（即 $[0,n]$ 间任意整数）用 $\mathrm{FFT}$ 预处理出上面那个式子的值，于是我们就在 $O(n\log n+Lw)$ 的时间复杂度内通过了这一 Subtask。

Subtask 6

好耶，是防 AK

不难发现上面那个式子是关于 $a$ 的一个 $m$ 次多项式，我们可以预先对 $a\in[0,m]$ 求出点值然后插值得到多项式，最后我们再多点求值求至多 $L$ 个点值即可。

不过我们注意到由于 $n$ 是 $10^9$ 级别，我们没法以朴素形式为基础直接卷积得到点值，于是我们对原式变形：

$$\begin{aligned} &\sum_{i=0}^m(-1)^i\binom ai\binom{n-a}{m-i}\\ =&\sum_{i=0}^m(-1)^i\frac{a!(n-a)!}{i!(a-i)!(m-i)!(n-a-m+i)!}\\ =&a!\sum_{i=0}^m\frac{(-1)^i}{i!(m-i)!}\frac{(n-a)^{\underline{m-i}}}{(a-i)!}\\ =&\frac{a!}{n^{\underline a}}\sum_{i=0}^m\frac{(-1)^i}{i!(m-i)!}\frac{n^{\underline{m+(a-i)}}}{(a-i)!} \end{aligned} $$

于是就可以正常卷积了。时间复杂度 $O(m\log^2m+Lw)$。

mivik.h / 98 分代码 / 满分代码