卷与二进制学习总结
- 卷与二进制学习总结
- 基础
- 问题
- 更一般的点值表示？
- 与卷积
- 或卷积
- 异或卷积
- 扩展到 维的与/或/异或卷积
- 继续扩展
- 子集卷积
- 应用
- 集合幂级数
- 与或异或卷积
- 一点记号
- 洛谷P5406 [THUPC2019]找树
- 洛谷P5387 [Cnoi2019]人形演舞
- UOJ310 【UNR #2】黎明前的巧克力
- 一道题目
- 子集卷积
- 洛谷P6846 [CEOI2019] Amusement Park
- 子集卷积的高级操作
- LOJ154 集合划分计数
- 基础
卷与二进制学习总结
有些人啊，总是把什么前缀和，什么差分啊，取一个高大上的名字“FWT”，就搞不懂有什么意义。
以上为玩笑话。
基础
问题
给定长度为 \(2^w\) 下标从 \(0\sim 2^w-1\) 的两个数组 \(A,B\) ，分别求满足下列条件的数组 \(C\) ：
\[C_n=\sum_{i\land j=n}A_iB_j \]\[C_n=\sum_{i\lor j=n}A_iB_j \]\[C_n=\sum_{i\oplus j=n}A_iB_j \]\[C_n=\sum_{i\land j=0,i\lor j=n}A_iB_j \]更一般的点值表示？
要求某一个卷积 \(F*G\) ，如果可以构造出一个输入为数组（函数）输出为数组（函数）的一个函数 \(\operatorname{Trans}()\) ，并且 \(\operatorname{Trans}(F)\) 和 \(F\) 的转化比较容易实现，并且 \(\operatorname{Trans}(F*G)_i=\operatorname{Trans}(F)_i\times \operatorname{Trans}(G)_i\) ，那么就可以比较容易地求出 \(F*G\) 了。
认为 \(F\to \operatorname{Trans}(F)\) 为正变换， \(\operatorname{Trans}(F)\to F\) 为逆变换。
与卷积
\[C_n=\sum_{i\land j=n}A_iB_j \]考虑构造上面说的这样一个函数 \(\operatorname{Trans}()\) ，假设这个函数为 \(\operatorname{Trans}(H)_i=\sum_{j}f(j,i)H_j\) ，那么：
\[\operatorname{Trans}(C)_n=\operatorname{Trans}(A*B)_n\\ =\operatorname{Trans}(A)_n\times \operatorname{Trans}(B)_n\\ =\sum_{i}f(i,n)A_i\sum_{j}f(j,n)B_j\\ =\sum_{i,j}f(i,n)f(j,n)A_iB_j \]又由于有：
\[\operatorname{Trans}(C)_n=\sum_{k}f(k,n)C_k\\ =\sum_{k}f(k,n)\sum_{i\land j=k}A_iB_j\\ =\sum_{i,j}f(i\land j,n)A_iB_j \]所以我们可以得到：
\[f(i\land j,n)=f(i,n)f(j,n) \]相当于我们要构造的 \(f()\) 满足如上条件，并且 \(\operatorname{Trans}(H)\) 和 \(H\) 之间的转化需要比较容易。
怎么构造呢？这就要靠玄学了
可以构造出这样的一个 \(f()\) ：
\[f(i,n)=[i\land n=n] \]（就是说 \(f(i,n)=1\) 当且仅当 \(n\) 是 \(i\) 的子集）
不难发现这个显然是满足 \(f(i\land j,n)=f(i,n)f(j,n)\) 这个条件的，并且 \(\operatorname{Trans}(H)\) 和 \(H\) 之间的转化也及其容易，就仅仅只是后缀和和差分罢了（ \(\operatorname{Trans}(H)\) 是 \(H\) 的后缀和）。
时间复杂度为 \(\mathcal O(2^ww)\) 。
参考代码：
void FWT_and(int*F,int n,int rv){
if(!rv){
for(int mid=1;mid或卷积
\[C_n=\sum_{i\lor j=n}A_iB_j \]类似地，可以得到要构造的 \(f()\) 需满足：
\[f(i\lor j,n)=f(i,n)f(j,n) \]类似地，构造：
\[f(i,n)=[i\land n=i] \]（就是说 \(f(i,n)=1\) 当且仅当 \(i\) 是 \(n\) 的子集）
\(\operatorname{Trans}(H)\) 是 \(H\) 的前缀和。
时间复杂度为 \(\mathcal O(2^ww)\) 。
参考代码：
void FWT_or (int*F,int n,int rv){
if(!rv){
for(int mid=1;mid异或卷积
\[C_n=\sum_{i\oplus j=n}A_iB_j \]类似地，可以得到要构造的 \(f()\) 需满足：
\[f(i\oplus j,n)=f(i,n)f(j,n) \]好像构造类似不了了
设 \(\operatorname{bitcnt}(i)\) 表示 \(i\) 中 \(1\) 的个数，可以构造：
\[f(i,n)=(-1)^{\operatorname{bitcnt}(i\land n)} \]可以发现，这个式子满足上面所说的条件，然后 \(\operatorname{Trans}(H)\) 与 \(H\) 如何转化呢？
转化方法和前缀和差分是类似的，先考虑从 \(H\) 变成 \(\operatorname{Trans}(H)\) ，依次考虑每一个维度 \(i\) ，然后枚举状态 \(sta_0,sta_1\) 满足 \(sta_0+i=sta_1\) ，设 \(l=H_{sta_0},r=H_{sta_1}\) ，那么令 \(H_{sta_0}\gets l+r,H_{sta_1}\gets l-r\) ；从 \(\operatorname{Trans}(H)\) 变成 \(H\) 就是逆过程，相当于是已知 \(l+r\) 和 \(l-r\) 求 \(l,r\) ，那么 \(l=\frac{1}{2}((l+r)+(l-r)),r=\frac{1}{2}((l+r)-(l-r))\) ，也就是原过程求出来之后再额外乘以 \(\frac{1}{2}\) 。
时间复杂度为 \(\mathcal O(2^ww)\) 。
参考代码：
void FWT_xor(int*F,int n,int rv){
for(int mid=1;mid扩展到 \(k\) 维的与/或/异或卷积
如果看懂了上面所说的， FWT 扩展到 \(k\) 维其实还是挺简单的，依次构造的 \(f()\) 需要满足：
\[f(\min(i,j),n)=f(i,n)f(j,n) \]\[f(\max(i,j),n)=f(i,n)f(j,n) \]\[f((i+j)\bmod k,n)=f(i,n)f(j,n) \]前两个还是前缀和与差分，最后面的那个就是长度为 \(k\) 的循环卷积，暴力或者 Bluestein's Algorithm 都可以。
继续扩展
对于任意的卷积（ \(\operatorname{op}_1,\operatorname{op}_2\) 是运算符，其中 \(\operatorname{op}_2\) 需要满足分配律）：
\[C_n=\sum_{i\operatorname{op}_1j=n}A_i\operatorname{op}_2B_j \]构造出来的 \(f()\) 需要满足的条件：
\[f(i\operatorname{op}_1j,n)=f(i,n)\operatorname{op}_2f(j,n) \]如果多维度的每个维度的卷积定义不一样，仍然一个维度一个维度地做就行了。
子集卷积
\[C_n=\sum_{i\land j=0,i\lor j=n}A_iB_j \]这个式子可以转化为：
\[C_n=\sum_{\operatorname{bitcnt}(i)+\operatorname{bitcnt}(j)=\operatorname{bitcnt}(n),i\lor j=n}A_iB_j \]考虑分层做卷积，将 \(\operatorname{bitcnt}(i)\) 相等的作为一层，把 \(A,B\) 分成 \(w+1\) 层，每层都做一个“或正变换”，然后 \(A\) 的第 \(i\) 层和 \(B\) 的第 \(j\) 层对应点乘，加到 \(C\) 的第 \(i+j\) 层里面，最后再把 \(C\) 的每一层都“或逆变换”回去， \(C_n\) 的实际值就是 \(C\) 的第 \(\operatorname{bitcnt}(n)\) 层里面 \(n\) 这个位置的值。
时间复杂度为 \(\mathcal O(2^ww^2)\) 。
应用
集合幂级数
在 OI 中，一个二进制数一般是用来表示一个集合的，不妨认为全集 \(U=\{0,1,\dots,w-1\}\) ，方便起见记 \(2^w\) 表示 \(U\) 的所有子集组成的集合，类似形式幂级数，我们可以定义集合幂级数：
\[F(x)=\sum_{s\sube 2^w}f_sx^s \]集合幂级数的加减就是对应位置直接加减，乘法的话就是上面所讲的四种卷积，除法等一系列高级运算在“与或异或卷积”中由于转化为了点乘的形式，直接在对应位置进行即可（比如除法就是对应位置做除法（正变换过后如果有 0 那么没有逆元），开根就是对应位置开根等），但是在“子集卷积”中有点不太一样，这里另作讨论。
与或异或卷积
一点记号
为了方便起见，用 \(\operatorname{FWT}()\) 表示正变换， \(\operatorname{IFWT}()\) 表示逆变换，用 \(\bigoplus\) 表示异或卷积，如果 \(\prod\) 后面接的是 \(\operatorname{FWT}()\) 过后的式子这个 \(\prod\) 指的是对应位置点乘。
注意到变化过程中只用了加减操作，所以有：
\[\operatorname{FWT}(A)+\operatorname{FWT}(B)=\operatorname{FWT}(A+B) \]\[\operatorname{IFWT}(A)+\operatorname{IFWT}(B)=\operatorname{IFWT}(A+B) \]洛谷P5406 [THUPC2019]找树
直接暴力统计边权异或和为某个值的方案数，使用异或卷积，我们要求的就是这个：
\[\sum_{T}x^{\oplus_{e\in T}v_e}=\sum_{T}\bigoplus_{e\in T}x^{v_e} =\operatorname{IFWT}(\sum_{T}\prod_{e\in T}\operatorname{FWT}(x^{v_e})) \]恰好矩阵树定理求的就是若干边权的乘积，所以可以用矩阵树来求上面的这个东西，时间复杂度 \(\mathcal O(n^32^w+m2^w)\) （玄学跑过）。
洛谷P5387 [Cnoi2019]人形演舞
先求出 \(1\) 到 \(m\) 的每个数字的 \(\operatorname{SG}\) 函数，问题就变成了询问依次选出来的 \(|V|\) 个数异或起来不为 \(0\) 的方案数，后半部分就可以用异或卷积然后取 \(|V|\) 次方很快求出来。
如何求每个数字的 \(\operatorname{SG}\) 函数？不难发现 \(x\) 可以变成 \(y\) 当且仅当 \(0\le y
UOJ310 【UNR #2】黎明前的巧克力
考虑 Evan 和 Lyra 选择的巧克力的并集 \(S\) ， \(S\) 中的所有数异或起来必然等于 \(0\) ，并且 Evan 可以选择 \(S\) 的任意一个子集，所以可以认为 \(S\) 对答案的贡献就是 \(2^{|S|}\) ，于是问题就变成了求所有异或为 \(0\) 的集合的贡献和，也就是求：
\[[x^0]\bigoplus_{i=1}^n(2x^{a_i}+x^0)=[x^0]\operatorname{IFWT}(\prod_{i=1}^n\operatorname{FWT}(2x^{a_i}+x^0)) \]暴力 \(\operatorname{FWT}()\) 再点乘起来时间复杂度无法接受，考虑异或卷积实际上求的是什么：
\[[x^s]\operatorname{FWT}(2x^{a_i}+x^0)=2\times (-1)^{\operatorname{bitcnt}(s\land a_i)}+1\times (-1)^{\operatorname{bitcnt}(s\land 0)}=2\times (-1)^{\operatorname{bitcnt}(s\land a_i)}+1 \]对于不同的 \(s\) ， \([x^s]\operatorname{FWT}(2x^{a_i}+x^0)\) 只有两种可能的取值，即 \(3\) 或者 \(-1\) ，所以全部点乘起来得到的某个 \(x^s\) 前面的系数必然可以表示为 \(3^t(-1)^{n-t}\) 次方的形式：
\[[x^s]\prod_{i=1}^n\operatorname{FWT}(2x^{a_i}+x^0)=3^t(-1)^{n-t} \]要求某一位的系数也就是要求出 \(t\) ，考虑来点骚操作：
\[[x^s]\sum_{i=1}^n\operatorname{FWT}(2x^{a_i}+x^0)=3t-(n-t)=4t-n \]\[[x^s]\operatorname{FWT}(nx^0+2\sum_{i=1}^nx^{a_i})=4t-n \]由此一遍 \(\operatorname{FWT}()\) 就可以求出每一位的系数，然后再一遍 \(\operatorname{IFWT}()\) 回去就行了。
洛谷P6846 [CEOI2019] Amusement Park
先考虑求 DAG 方案数，关键是如何枚举 DAG 才能不重不漏，可以设 \(f_{S}\) 表示点集 \(S\) 形成 DAG 的方案数，考虑到如果 \(S\) 是 DAG ，那么必然会存在入度为 \(0\) 的点，但是将入度为 \(0\) 的点删掉并不能保证剩下的入度为 \(0\) 的点和这些点之间有连边，不过可以容斥求这个东西，注意到有 \(\sum_{i=1}^n(-1)^{i-1}{n\choose i}=[n>0]\) ，所以可以写出转移式子：
\[f_S=\sum_{T\sube S,T\ne \varnothing}(-1)^{|T|-1}[\forall (u,v)\in E,u\not\in T\lor v\not\in T]f_{S/T} \]注意到子集卷积的具体实现过程中是分层做卷积的，可以边子集卷积边 dp 。
时间复杂度 \(\mathcal O(2^nn^2)\) 。
子集卷积的高级操作
由于我们在实现“子集卷积”的时候是通过一种比较复杂的方式实现的，并不像“与或异或卷积”一样方便地正变换后对应位置做乘除即可，在“子集卷积”的具体实现过程中，可以理解为我们还给每个对应位置加了一维（上面所说的“层数”），而两个对应位置卷起来同时它们的层数还会对应相加（第 \(i\) 层的位置 \(s\) 和第 \(j\) 层的位置 \(s\) 乘起来会贡献到第 \(i+j\) 的位置 \(s\) ），但是可以发现此时不同位置之间仍然是互不相关的，所以可以把每个位置分开考虑，某个位置的操作恰好就是一般我们说的多项式（形式幂级数）的卷积，所以每个位置依次按照形式幂级数的方式进行操作即可。
具体来说，如果要对“子集卷积”进行操作，先分层，然后每层都“或卷积”正变换过去，接着每个位置分开考虑，用形式幂级数的方式堆每个位置进行操作，然后再每层“或卷积”逆变换回去，再将所有层合并即可。
还有需要注意的一点就是，一开始的变换导致了时间复杂度的下界为 \(\mathcal O(2^ww^2)\) ，不能再小了，而在对形式幂级数进行操作的时候我们是在对 \(2^w\) 个长度为 \(w+1\) 的形式幂级数进行操作的，所以把这个操作用 FFT 之类的优化成 \(\mathcal O(w\log_2w)\) 是没有意义的，所以此时的操作建议使用 \(\mathcal O(w^2)\) 的暴力递推（暴力递推的一些操作可以看）。
LOJ154 集合划分计数
一个子集卷积的高级操作的例子。
设 \(F=\sum_{i=0}^{m-1}x^{s_i}\) ，注意到 \(1\le s_i\) ，所以 \(F_0=0\) ，题目要求的就是这个东西：
\[[x^{2^n-1}]\sum_{i=0}^k\frac{F^i}{i!} \]推式子：
\[H=\sum_{i=0}^k\frac{F^i}{i!} \]\[H'=\sum_{i=1}^{k}\frac{iF^{i-1}}{i!}F' \]\[H'=F'\sum_{i=1}^k\frac{F^{i-1}}{(i-1)!} \]\[H'=F'\sum_{i=0}^{k-1}\frac{F^i}{i!} \]\[H'=F'(H-\frac{F^k}{k!}) \]\[nH_n=\sum_{i+j=n}iF_i(H_j-(\frac{F^k}{k!})_j) \]其中 \(H_0=1\) ， \(F^k\) 直接多项式快速幂。