[Mivik Round / Secret Sky] [题解] Virtual Self

· · 题解

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 分代码 / 满分代码