专栏文章

哈集幂难被掳夺

tty_mxzhn
算法·理论参与者 7已保存评论 6

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
6 条
当前快照
1 份
快照标识符
@mlqup6is
此快照首次捕获于
2026/02/18 01:02
昨天
此快照最后确认于
2026/02/19 01:01
11 小时前
查看原文

黎明前的巧克力

题意

原题链接。
选出长度为 nn 的序列 aa 中的两个可空不交子序列，使得这两个子序列的异或和相等。0≤ai<2V0\le a_i<2^V。

做法

考虑集合幂级数。我们要选出一个子序列，这个子序列的异或和为 00，子序列内部的数可以选择选入第一个子序列或者第二个子序列。
不难发现这是在求 [x0]∏i=1n(1+2xai)\displaystyle [x^0]\prod_{i=1}^n(1+2x^{a_i})。
由于 FWT 的性质不足，考虑一种暴力也就是做 nn 次 FWT 后点乘再 IFWT。
考虑 FWT 的定义式：F^i=∑j=02V−1Fj(−1)i∩j\displaystyle \hat{F}_i=\sum_{j=0}^{2^V-1}F_j(-1)^{i\cap j}。
容易发现对 1+2xai1+2x^{a_i} 做 FWT 后只有两种数也就是 −1-1 和 33。
考虑点乘后的，IFWT 前的序列中，每一项的贡献为 (−1)z3n−z(-1)^{z}3^{n-z}。
考虑算出 zz。我们把所有 aia_i 放到一个序列 bb 中做 FWT，根据 b^i\hat{b}_i 的值算出 ziz_i 即可。

总结

这个做法还可以用到 Triple 上。
稍微拓展一下就是 goods。

我的 XOR 卷积人生

题意

原题链接。
你要在两个长度为 2n2^n 的矩阵序列上做 xor 卷积，没有任何手段获取乘法逆元。
要求为 O(n22n)O(n^22^n)。

Part 1

考虑 n=1n=1 怎么做。
对于序列 [a0,a1][a_0,a_1] 与 [b0,b1][b_0,b_1] 做异或卷积可以得到 [a0b0+a1b1,a0b1+a1b0][a_0b_0+a_1b_1,a_0b_1+a_1b_0]。
考虑如何把这个过程拆分成点乘。
设计一个形式元 xx，计算 (a0+a1x)(b0+b1x)(a_0+a_1x)(b_0+b_1x)。
得到的结果是 a0b0+a1b0x+a0b1x+a1b1x2a_0b_0+a_1b_0x+a_0b_1x+a_1b_1x^2。
我们想要的结果是 f(x)=a0b0+a1b0x+a0b1x+a1b1f(x)=a_0b_0+a_1b_0x+a_0b_1x+a_1b_1。
朴素的做法是设计 x2=1x^2=1，然后让 x=1,−1x=1,-1。这两个根为 α,β\alpha,\beta。
求出 f(α),f(β)f(\alpha),f(\beta) 后再插值还原 ff。

Part 2

对于 nn 为任意的情况。我们设计 xSx^{S} 表示 ∏i∈Sxi\displaystyle \prod_{i\in S}x_i。所以 xx 其实是一个长度为 nn 的向量 [x0,x1,...,xn−1][x_0,x_1,...,x_{n-1}]。
设计集合幂级数 f(x)=∑i=02n−1Aixif(x)=\displaystyle \sum_{i=0}^{2^n-1} A_ix^i。
我们再设计 2n2^n 个根 XpX_p。定义 Xp=∏i=0n−1[pi=0]α+[pi=1]βX_p=\displaystyle \prod_{i=0}^{n-1}[p_i=0]\alpha+[p_i=1]\beta。
代入这些根后得到 2n2^n 个结果 Yp=f(Xp)Y_p=f(X_p)。代入根的过程容易用分治加速。
得到 YY 后，插值的过程也容易用分治加速。
对于 xor 卷积，要解方程 x2=1x^2=1，根是 α=1,β=−1\alpha=1,\beta=-1。
对于 or 卷积，要解方程 x2=xx^2=x，根是 α=0,β=1\alpha=0,\beta=1。

Part 3

考虑子集卷积。
要解的方程是 x2=0x^2=0，这是重根，无法插值。
设根为 α=0,β=ϵ\alpha=0,\beta=\epsilon。维护含有 ϵ\epsilon 的多项式即可。
插值时可以求逆。具体的，我们让 Y0=f(0),Y1=f(ϵ)Y_0=f(0),Y_1=f(\epsilon)。
拉格朗日插值得到 Y0x−X1X0−X1+Y1x−X0X1−X0Y_0\dfrac{x-X_1}{X_0-X_1}+Y_1\dfrac{x-X_0}{X_1-X_0}。容易求解。
最后得到答案后再让 ϵ←0\epsilon\leftarrow 0 即可。

Part 4

我们让原题的 α=1,β=ϵ−1\alpha=1,\beta=\epsilon-1。
此时要做多项式操作，复杂度变为 O(n32n)O(n^32^n)。

Part 4.5

不妨把 xx 平移一位，也就是 a0+a1(x+1−1)a_0+a_1(x+1-1)。我们让 a0←a0+a1a_0\leftarrow a_0+a_1，这样变成 a0+a1(x−1)a_0+a_1(x-1)。
这个时候我们让 (x−1)2=1(x-1)^{2}=1，解得 α=0,β=2\alpha=0,\beta=2。
我们设 β=ϵ\beta=\epsilon，跑一遍子集卷积，最后再让 ϵ←2\epsilon\leftarrow 2 即可。最后再还原真正的 c0,c1c_0,c_1。
时间复杂度可以复用子集卷积的实现得到 O(n22n)O(n^22^n)。

总结

这个题把 FWT 看成了一种多项式多点求值方法，把 IFWT 看成了一种多项式插值方法。是一道不可多得的好题。

3^N Minesweeper

题意

原题链接。

做法

我们来考虑用矩阵表示 FWT。
一般来讲，FWT 可以看成 F^i=∑j=03n−1c(j,i)Fj\displaystyle \hat{F}_i=\sum_{j=0}^{3^n-1} c(j,i) F_j。
然后我们要对这个矩阵 cc 求逆来得到逆变换（IFWT）。
考虑拆出一个 3×33\times 3 的矩阵 c0c_0 表示 n=1n=1 时的矩阵。c1c_1 表示 c0c_0 的逆矩阵。
那么我们把 c(j,i)c(j,i) 表示成 ∏v=0n−1c0(jv,iv)\displaystyle \prod_{v=0}^{n-1} c_0(j_v,i_v)。
接下来证明 c−1(j,i)=∏v=0n−1c1(jv,iv)\displaystyle c^{-1}(j,i)=\prod_{v=0}^{n-1} c_1(j_v,i_v)：
Fi=∑j=03n−1c−1(j,i)∑k=03n−1c(k,j)FkFi=∑j=03n−1(∏v=0n−1c1(jv,iv))∑k=03n−1(∏v=0n−1c0(kv,jv))FkFi=∑k=03n−1∑j=03n−1(∏v=0n−1c1(jv,iv))(∏v=0n−1c0(kv,jv))FkFi=∑k=03n−1∑j=03n−1I(k,j)I(j,i)FkF_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 的矩阵形式。
F^i=∑j=03n−1c(j,i)FjF^i=∑j=03n−1(∏v=0n−1c0(jv,iv))FjF^i=∑j=03n−1−1c0(0,in−1)(∏v=0n−2c0(jv,iv))Fj+∑j=3n−12×3n−1−1c0(1,in−1)(∏v=0n−2c0(jv,iv))Fj+∑j=2×3n−13n−1c0(2,in−1)(∏v=0n−2c0(jv,iv))Fj\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 \\
考虑预处理 Fi′=∑j=03n−1(∏v=0n−2c0(jv,iv))[jn−1=in−1]Fj\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。
这样可以得到 F^i=c0(0,iv)Fa′+c0(1,iv)Fb′+c0(2,iv)Fc′\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,ca,b,c 为改变 ii 的位 n−1n-1 变为 0/1/20/1/2 后得到的三进制数。这就是 FWT。

总结

矩阵形式的 FWT 可以用来描述一些更一般的问题。
欧伊昔说了任意运算表的情况，但我不会。其实大概意思就是把每一维拆成更多矩阵但是先不写了。

集合划分计数

题意

原题链接。
在长度为 mm 的序列 aa 中选至多 kk 个 [0,2n−1][0,2^n-1] 的二进制数使得他们两两的按位与为 00，按位或为 2n−12^n-1。

做法

弱化问题是“不交并”集合幂级数的 exp⁡\exp。这也是最常说是集合幂级数的运算。
先理解一下 O(n22n)O(n^22^n) 做 exp⁡\exp 这件事情。
我们设计了一个新的元 yy。这其实就是之前说的 ϵ\epsilon。
但是现在换个角度，我们先对 xx 这一维做 or-FWT。
什么意思？就是每一维代入 00 和 11 做点求值就懂了。
这个时候我们 yy 这一元一直没有变，所以我们就是做了 nn 次 or-FWT，点求值出来其实 11 代表的是当前这个维度的 yiy^i。
这样子我们求完后就要求出 2n2^n 个点值的答案。这就是在 yy 这一维上做一遍 exp⁡\exp。
然后我们再 IFWT 回去就好了。
那么这个题就是把里面的那次操作改了一下。

总结

可以逐点牛顿迭代法，但我不会。
FWT + IFWT 是一种插值方法，这个东西是有用且直观的。

总结

好多难的东西还没写，但是新年快乐！

评论

共 6 条评论，欢迎与作者交流。

正在加载评论...