哈集幂难被掳夺
ty_mxzhn
·
·
算法·理论
黎明前的巧克力
题意
原题链接。
选出长度为 n 的序列 a 中的两个可空不交子序列，使得这两个子序列的异或和相等。0\le a_i<2^V。
做法
考虑集合幂级数。我们要选出一个子序列，这个子序列的异或和为 0，子序列内部的数可以选择选入第一个子序列或者第二个子序列。
不难发现这是在求 \displaystyle [x^0]\prod_{i=1}^n(1+2x^{a_i})。
由于 FWT 的性质不足，考虑一种暴力也就是做 n 次 FWT 后点乘再 IFWT。
考虑 FWT 的定义式：\displaystyle \hat{F}_i=\sum_{j=0}^{2^V-1}F_j(-1)^{i\cap j}。
容易发现对 1+2x^{a_i} 做 FWT 后只有两种数也就是 -1 和 3。
考虑点乘后的，IFWT 前的序列中，每一项的贡献为 (-1)^{z}3^{n-z}。
考虑算出 z。我们把所有 a_i 放到一个序列 b 中做 FWT，根据 \hat{b}_i 的值算出 z_i 即可。
总结
这个做法还可以用到 Triple 上。
稍微拓展一下就是 goods。
我的 XOR 卷积人生
题意
原题链接。
你要在两个长度为 2^n 的矩阵序列上做 xor 卷积，没有任何手段获取乘法逆元。
要求为 O(n^22^n)。
Part 1
考虑 n=1 怎么做。
对于序列 [a_0,a_1] 与 [b_0,b_1] 做异或卷积可以得到 [a_0b_0+a_1b_1,a_0b_1+a_1b_0]。
考虑如何把这个过程拆分成点乘。
设计一个形式元 x，计算 (a_0+a_1x)(b_0+b_1x)。
得到的结果是 a_0b_0+a_1b_0x+a_0b_1x+a_1b_1x^2。
我们想要的结果是 f(x)=a_0b_0+a_1b_0x+a_0b_1x+a_1b_1。
朴素的做法是设计 x^2=1，然后让 x=1,-1。这两个根为 \alpha,\beta。
求出 f(\alpha),f(\beta) 后再插值还原 f。
Part 2
对于 n 为任意的情况。我们设计 x^{S} 表示 \displaystyle \prod_{i\in S}x_i。所以 x 其实是一个长度为 n 的向量 [x_0,x_1,...,x_{n-1}]。
设计集合幂级数 f(x)=\displaystyle \sum_{i=0}^{2^n-1} A_ix^i。
我们再设计 2^n 个根 X_p。定义 X_p=\displaystyle \prod_{i=0}^{n-1}[p_i=0]\alpha+[p_i=1]\beta。
代入这些根后得到 2^n 个结果 Y_p=f(X_p)。代入根的过程容易用分治加速。
得到 Y 后，插值的过程也容易用分治加速。
对于 xor 卷积，要解方程 x^2=1，根是 \alpha=1,\beta=-1。
对于 or 卷积，要解方程 x^2=x，根是 \alpha=0,\beta=1。
Part 3
考虑子集卷积。
要解的方程是 x^2=0，这是重根，无法插值。
设根为 \alpha=0,\beta=\epsilon。维护含有 \epsilon 的多项式即可。
插值时可以求逆。具体的，我们让 Y_0=f(0),Y_1=f(\epsilon)。
拉格朗日插值得到 Y_0\dfrac{x-X_1}{X_0-X_1}+Y_1\dfrac{x-X_0}{X_1-X_0}。容易求解。
最后得到答案后再让 \epsilon\leftarrow 0 即可。
Part 4
我们让原题的 \alpha=1,\beta=\epsilon-1。
此时要做多项式操作，复杂度变为 O(n^32^n)。
Part 4.5
不妨把 x 平移一位，也就是 a_0+a_1(x+1-1)。我们让 a_0\leftarrow a_0+a_1，这样变成 a_0+a_1(x-1)。
这个时候我们让 (x-1)^{2}=1，解得 \alpha=0,\beta=2。
我们设 \beta=\epsilon，跑一遍子集卷积，最后再让 \epsilon\leftarrow 2 即可。最后再还原真正的 c_0,c_1。
时间复杂度可以复用子集卷积的实现得到 O(n^22^n)。
总结
这个题把 FWT 看成了一种多项式多点求值方法，把 IFWT 看成了一种多项式插值方法。是一道不可多得的好题。
3^N Minesweeper
题意
原题链接。
做法
我们来考虑用矩阵表示 FWT。
一般来讲，FWT 可以看成 \displaystyle \hat{F}_i=\sum_{j=0}^{3^n-1} c(j,i) F_j。
然后我们要对这个矩阵 c 求逆来得到逆变换（IFWT）。
考虑拆出一个 3\times 3 的矩阵 c_0 表示 n=1 时的矩阵。c_1 表示 c_0 的逆矩阵。
那么我们把 c(j,i) 表示成 \displaystyle \prod_{v=0}^{n-1} c_0(j_v,i_v)。
接下来证明 \displaystyle c^{-1}(j,i)=\prod_{v=0}^{n-1} c_1(j_v,i_v)：
F_i=\sum_{j=0}^{3^n-1}c^{-1}(j,i)\sum_{k=0}^{3^n-1} c(k,j) F_k\\
F_i=\sum_{j=0}^{3^n-1}\left(\prod_{v=0}^{n-1} c_1(j_v,i_v)\right)\sum_{k=0}^{3^n-1} \left( \prod_{v=0}^{n-1} c_0(k_v,j_v)\right) F_k\\
F_i=\sum_{k=0}^{3^n-1} \sum_{j=0}^{3^n-1}\left(\prod_{v=0}^{n-1} c_1(j_v,i_v)\right)\left( \prod_{v=0}^{n-1} c_0(k_v,j_v)\right) F_k\\
F_i=\sum_{k=0}^{3^n-1} \sum_{j=0}^{3^n-1}I(k,j)I(j,i) F_k\\
这个显然成立。由于逆矩阵如果存在就唯一所以得解。
考虑快速计算。接下来我们引入 FWT 的矩阵形式。
\hat{F}_i=\sum_{j=0}^{3^n-1} c(j,i)F_j\\
\hat{F}_i=\sum_{j=0}^{3^n-1} \left( \prod_{v=0}^{n-1} c_0(j_v,i_v)\right)F_j\\
\hat{F}_i=\sum_{j=0}^{3^{n-1}-1} c_0(0,i_{n-1})\left( \prod_{v=0}^{n-2} c_0(j_v,i_v)\right)F_j +\sum_{j=3^{n-1}}^{2\times 3^{n-1}-1} c_0(1,i_{n-1})\left( \prod_{v=0}^{n-2} c_0(j_v,i_v)\right)F_j+\sum_{j=2\times 3^{n-1} }^{3^n-1} c_0(2,i_{n-1})\left( \prod_{v=0}^{n-2} c_0(j_v,i_v)\right)F_j \\
考虑预处理 \displaystyle F'_i=\sum_{j=0}^{3^n-1} \left( \prod_{v=0}^{n-2} c_0(j_v,i_v)\right)[j_{n-1}=i_{n-1}]F_j。
这样可以得到 \hat{F}_i=c_0(0,i_v)F'_a+c_0(1,i_v)F'_b+c_0(2,i_v)F'_c。其中 a,b,c 为改变 i 的位 n-1 变为 0/1/2 后得到的三进制数。这就是 FWT。
总结
矩阵形式的 FWT 可以用来描述一些更一般的问题。
欧伊昔说了任意运算表的情况，但我不会。其实大概意思就是把每一维拆成更多矩阵但是先不写了。
集合划分计数
题意
原题链接。
在长度为 m 的序列 a 中选至多 k 个 [0,2^n-1] 的二进制数使得他们两两的按位与为 0，按位或为 2^n-1。
做法
弱化问题是“不交并”集合幂级数的 \exp。这也是最常说是集合幂级数的运算。
先理解一下 O(n^22^n) 做 \exp 这件事情。
我们设计了一个新的元 y。这其实就是之前说的 \epsilon。
但是现在换个角度，我们先对 x 这一维做 or-FWT。
什么意思？就是每一维代入 0 和 1 做点求值就懂了。
这个时候我们 y 这一元一直没有变，所以我们就是做了 n 次 or-FWT，点求值出来其实 1 代表的是当前这个维度的 y^i。
这样子我们求完后就要求出 2^n 个点值的答案。这就是在 y 这一维上做一遍 \exp。
然后我们再 IFWT 回去就好了。
那么这个题就是把里面的那次操作改了一下。
总结
可以逐点牛顿迭代法，但我不会。
FWT + IFWT 是一种插值方法，这个东西是有用且直观的。
总结
好多难的东西还没写，但是新年快乐！