Solution：AT_arc139_f [ARC139F] Many Xor Optimization Problems

· · 题解

第 5 道问号题，神秘 q-analog。

可以发现题解区内只有 \Theta(n) 和 \Theta(n\log^2 n)，所以来一个 \Theta(n\log n) 的式子。

以下称 i 在线性基内，当且仅当线性基内存在一个最高位为 2^i 的数。

考虑把 Xor Optimization Problem 的答案写成一些好计数的形式，容易发现答案只由原序列的线性基决定。但是由于一个序列可以对应多个线性基，我们要求线性基必须是行最简型，这样线性基就是唯一的。此时答案就是线性基内所有数的异或和。

这个异或和由两部分组成：如果 i 在线性基内，答案第 i 位一定是 1；否则看起来不好处理，但是容易发现如果 i 不超过所有数的最高位，第 i 位会有恰好一半的概率是 1（这个是容易感性理解的）。这样设在线性基内的位为 0\leq a_1<a_2\cdots<a_k<M，答案就是 \frac 12(2^{a_k}-1+\sum_i2^{a_i})。

我们把这个东西拆成两半，先考虑对于所有序列算 \sum_i2^{a_i} 的和。对于一个给定的大小为 k 的线性基，其对应的序列个数为 2^{\binom k2}[N]_2^{\underline k}，这就是秩为 k 的 k\times N 矩阵的数量。而给定在线性基内的 k 个位 a_i，考虑能自由选择的位置的个数，其对应的线性基个数显然就是 \prod_i2^{a_i-(i-1)}。于是答案是

\begin{aligned} &\sum_{k=0}^N2^{\binom k2}[N]_2^{\underline k}\sum_{0\leq a_1<a_2\cdots<a_k<M}\left(\sum_{i=1}^k2^{a_i}\right)\left(\prod_{i=1}^k2^{a_i-(i-1)}\right)\\ =&\sum_{k=0}^N[N]_2^{\underline k}\sum_{0\leq a_1<a_2\cdots<a_k<M}\left(\sum_{i=1}^k2^{a_i}\right)\left(\prod_{i=1}^k2^{a_i}\right) \end{aligned}

这个时候就可以开始拆贡献了，考虑把每个 a_i 的贡献拆出来，由 q-二项式定理 有

\begin{aligned} &\sum_{k=0}^N[N]_2^{\underline k}[x^k]\sum_{i=0}^{M-1}2^i\prod_{j=0}^{M-1}([j\neq i]+2^jx)\\ =&\sum_{k=0}^N[N]_2^{\underline k}[x^{k-1}]\left(\sum_{i=0}^{M-1}\frac{4^i}{1+2^ix}\right)\left(\sum_{j}2^{\binom j2}\binom{M}{j}_2x^j\right)\\ =&\sum_{k=0}^N[N]_2^{\underline k}[x^{k-1}]\left(\sum_{i}(-x)^i\frac{2^{(i+2)N}-1}{2^{i+2}-1}\right)\left(\sum_{j}2^{\binom j2}\binom{M}{j}_2x^j\right) \end{aligned}

直接卷积即可。

对于所有序列算 2^{a_k}-1，显然 a_k 就是序列所有数的最高位，随便容斥一下得到这部分的答案是

\sum_{i=1}^M(2^i-1)(2^{iN}-2^{(i-1)N})

把两个式子加起来除以 2 即为答案。

Code.

如果在上面的过程中我们拆贡献拆早了，一开始就枚举 2^{a_i} 的贡献而不把 a_i-(i-1) 里的 i-1 消掉，我们就不得不分开枚举小于 a_i 的数和大于 a_i 的数并得到一个丑而且完全推不出来的式子。这启示我们遇到枚举整个序列与拆贡献时不要急着拆贡献或太早地把枚举整个序列去掉。