基本概念

定義

• \(2^{X}\) 表示 \(X\) 的所有子集組成的集合。注意，此時(shí)元素是集合。

本質(zhì)就是全集的各個(gè)子集到值域的映射。

形式化地來(lái)說(shuō)就是，域 \(F\) 上的集合冪級(jí)數(shù)是 \(2^U\to F\) 的函數(shù)，對(duì)于每個(gè) \(S\subseteq U\)，都有 \(f_s \in F\)。

從多項(xiàng)式的角度理解，就是把之前的下標(biāo)為某個(gè)數(shù)字改為為某個(gè)具體集合。

表示

我們用 \(cx^s\) 表示 \(f_s=c\)，于是集合冪級(jí)數(shù)就可以表示為 \(f=\sum\limits_{S\in U}f_sx^s\)。

加法與乘法

加法直接對(duì)應(yīng)系數(shù)相加即可，注意此時(shí) \(f\) 與 \(g\) 必須全集相同。

乘法 \(h=f\times g=(\sum\limits_{L\in 2^U}f_Lx^L)\times(\sum\limits_{R\in 2^U}g_Rx^R)\)。當(dāng)集合冪級(jí)數(shù)的乘法對(duì)加法有分配律的時(shí)候有，

我們?cè)O(shè) \(f_Lx^L\times g_Rx^R=(f_L\times g_R)x^{L*R}\)，其中 \(\times\) 就是 \(F\) 域乘法，\(*\) 就是集合域運(yùn)算，且滿足結(jié)合律和交換律。

根據(jù) \(*\) 的不同有不同算法，以下一一介紹。

集合并卷積 / OR 卷積

就是把上述 \(*\) 定義為 \(\bigcup\)，然后我們就可以得到 $$h_s=\sum\limits_{L\in 2^U}\sum\limits_{R\in 2^U}[L\cup R=S]f_Lg_R$$
暴力計(jì)算時(shí)間復(fù)雜度 \(O(4^n)\)。

莫比烏斯變換（FMT）

定義快速莫比烏斯變換，\(f'={\rm FMT}(f)\)，為 \(f'_i=\sum\limits_{j\subset i}f_j\)，也就是子集求和。

定義快速莫比烏斯反演，\(f'={\rm FMI}(f)\)，為 \(f'_i=\sum\limits_{j|i=i}(-1)^{|i|-|j|}f_j\)。

其中 FMT 和 FMI 互為逆變換。對(duì)于 OR 卷積，我們只需要把 \(f\) 和 \(g\) 做一下 FMT，然后 \(h_i\gets f_i\times g_i\)，最后對(duì)于 \(h\) 做一個(gè) FMI 就解決了。

莫比烏斯變換可以通過(guò)高維前綴和來(lái)實(shí)現(xiàn)，所以我們對(duì)于 FMT 就是做一個(gè)系數(shù)為 \(1\) 的高維前綴和，對(duì)于 FMI 就是做一個(gè)系數(shù)為 \(-1\) 的高維前綴和。

莫比烏斯變換的本質(zhì)是容斥原理，原先 \(L\cup R=S\) 這個(gè)限制條件使得我們難以拆開 \(f\) 和 \(g\)，因?yàn)槎呋ハ嚓P(guān)聯(lián)。考慮使用容斥原理，我們欽定 \(S\) 中為 \(0\) 的位置，在 \(L\cup R\) 的結(jié)果中也為 \(0\)。于是我們就把限制寬松到了兩個(gè)子集，只需要滿足 \(L\subset S\) 和 \(R\subset S\) 即可，這就可以通過(guò)做一次高維前綴和（FMT），然后對(duì)應(yīng)位置相乘就行了。你欽定完之后，還需要設(shè)計(jì)容斥系數(shù)（FMI），系數(shù)是 \((-1)^{(n-|L|)-(n-|S|)}=(-1)^{|S|-|L|}\)。

沃爾什變換（FWT）

對(duì)于卷積 \(h\gets f\times g\)，我們按照二進(jìn)制最高位的奇偶性分為 \(f_0,f_1,g_0,g_1,h_0,h_1\)。

發(fā)現(xiàn)以上都可以通過(guò) \((f_0+f_1)\times (g_0+g_1)\) 和 \(f_0\times g_0\) 求解出來(lái)。

進(jìn)行如下變換，

變換之后，遞歸求 \(I_0=f'_0\times g'_0\) 和 \(I_1=f'_1\times g'_1\) 即可。遞歸到底層的時(shí)候就是對(duì)應(yīng)位置直接乘就行了。回溯的時(shí)候進(jìn)行如下變換，

很容易寫出一個(gè)分治的形式，但是常數(shù)很大，我們將其改成非遞歸形式。

容易發(fā)現(xiàn)其實(shí)往下遞歸的時(shí)候是 \(f_0\) 不變，\(f_1\gets f_0+f_1\)，往上回溯的時(shí)候也是 \(f_0\) 不變，\(f_1\gets f_1-f_0\)。我們可以將這兩部分的代碼，傳入一個(gè)系數(shù) \(t=1\) 或者 \(t=mod-1\)。

為了模擬遞歸，我們先要枚舉遞歸層數(shù)，也就是正在處理的這一位 \(2^k\)，然后分開枚舉 \(>2^k\) 和 \(<2^k\) 的值就行了。拼在一起就是當(dāng)前正在做的數(shù)字。

for(int k=1;k<full;k<<=1)
    for(int i=0;i<full;i+=(k<<1))
        for(int j=0;j<k;j++) 
            add(f[i|j|k],1ll*f[i|j]*t%mod);

集合交卷積 / AND 卷積

就是把上述 \(*\) 定義為 \(\bigcap\)，然后我們就可以得到 $$h_s=\sum\limits_{L\in 2^U}\sum\limits_{R\in 2^U}[L\cap R=S]f_Lg_R$$

不管是理解還是推導(dǎo)方面，都和 OR 卷積是一樣的，就不過(guò)多贅述了。

莫比烏斯變換（FMT）

把 OR 卷積中系數(shù)為 \(+1\) 和 \(-1\) 的高維前綴和，改為系數(shù)為 \(+1\) 和 \(-1\) 的高維后綴和即可。

容斥的時(shí)候欽定 \(L\cap R\) 中為 \(1\) 的位置是 \(S\) 即可。

沃爾什變換（FWT）

也是幾乎和 OR 卷積一模一樣。

先進(jìn)行 FWT，

再進(jìn)行 IFWT，

集合對(duì)稱差卷積 / XOR 卷積

就是把上述 \(*\) 定義為 \(\bigoplus\)，然后我們就可以得到

暴力計(jì)算時(shí)間復(fù)雜度 \(O(4^n)\)。關(guān)于 XOR 卷積就沒有 FMT 了，只能進(jìn)行 FWT。

沃爾什變換（FWT）

定義沃爾什變換 \(f'={\rm FWT(f)}\)，為 \(f'_s=\sum\limits_{T\in 2^U}f_T(-1)^{\lvert S\cap T\rvert}\)。
定義沃爾什逆變換，\(f'={\rm IFWT(f)}\)，為 \(f'_s=\dfrac{1}{2^n}\sum\limits_{T\in 2^U}f_T(-1)^{\lvert S\cap T\rvert}\)。

對(duì)于卷積 \(h\gets f\times g\)，我們按照二進(jìn)制最高位的奇偶性分為 \(f_0,f_1,g_0,g_1,h_0,h_1\)。

發(fā)現(xiàn)以上都可以通過(guò) \((f_0+f_1)\times (g_0+g_1)\) 和 \((f_0-f_1)\times (g_0-g_1)\) 組合出來(lái)。

進(jìn)行如下變換，

變換之后，遞歸求 \(I_0=f'_0\times g'_0\) 和 \(I_1=f'_1\times g'_1\) 即可。遞歸到底層的時(shí)候就是對(duì)應(yīng)位置直接乘就行了。回溯的時(shí)候進(jìn)行如下變換，

將上面這個(gè)遞歸形式改成非遞歸形式就行了。\(\dfrac{1}{2}\) 提取出來(lái)放到最后乘，每一位都要乘以 \(\dfrac{1}{2}\)，所以總計(jì)是乘以 \(\dfrac{1}{2^n}\)。

void FWT(int *f,bool type){
	for(int k=1;k<full;k<<=1)
		for(int i=0;i<full;i+=(k<<1))
			for(int j=0;j<k;j++){
				int x=f[i|j],y=f[i|j|k];
				f[i|j]=(x+y)%mod; f[i|j|k]=(x-y+mod)%mod;
			}
	if(!type) return ;
	for(int i=0;i<full;i++) f[i]=1ll*f[i]*invp%mod;
}

線性代數(shù)角度的 FWT

我們?cè)O(shè) \(f'_s=\sum\limits_{T\in 2^U}c_{s,t}f_T\)。

由于變換后對(duì)應(yīng)位置相乘需要滿足 \(*\) 運(yùn)算，所以 \(c_{i,j*k}=c_{i,j}c_{i,k}\)。還是和之前拆位思想相同。我們對(duì)于每一位獨(dú)立進(jìn)行上述變化。此時(shí)只需要考慮 \(s,t\) 的某一個(gè)二進(jìn)制位，所以下標(biāo)取值只有 \(0/1\)，故這是一個(gè) \(2\times 2\) 的矩陣。

按位或矩陣

其逆矩陣為

按位與矩陣

其逆矩陣為

按位異或矩陣

其逆矩陣為（為了減少常數(shù)，可以把 \(\frac{1}{2}\) 提取出來(lái)，最后再乘）

其實(shí)很好理解，根據(jù)之前的推導(dǎo)，OR 卷積和 AND 卷積的變換應(yīng)該是要求一個(gè)是對(duì)于子集求和，一個(gè)是對(duì)于超集求和。或矩陣中的 \(10,01,11\to 1\) 和 \(00\to 0\) 恰好對(duì)應(yīng)子集求和的形式。與矩陣同理。異或矩陣也符合我們推到的 FWT 的系數(shù)。

從這個(gè)角度，我們可以看出 FWT 是一種線性變換。

子集卷積 集合冪級(jí)數(shù) exp/ln/求逆

前置知識(shí)，\(n^2\) 多項(xiàng)式操作

子集卷積

要求就是不相交集合的并。也就是要求 \(L\bigcup R=S\) 且 \(\lvert L\rvert+\lvert R\rvert=\lvert S\rvert\)。

exp

組合意義：將大集劃分為無(wú)序小集合的方案數(shù)，也就是

ln

組合意義：把元素組合成集合的方案數(shù)。

求逆

做法

我們對(duì)于每種大小的集合冪級(jí)數(shù)進(jìn)行 FMT/FWT，然后關(guān)于大小那一個(gè)維度進(jìn)行 \(O(n^2)\) 多項(xiàng)式各種操作，最后再 FMI/IFWT 回去。由于 \(n\) 很小，所以暴力多項(xiàng)式操作的時(shí)間復(fù)雜度是正確的。

最后 \(h_s\) 取大小為 \(\operatorname{popcount}(s)\) 集合冪級(jí)數(shù)中的 \(s\) 即可。

這樣子就是有 \(n\) 種集合冪級(jí)數(shù)進(jìn)行變換。時(shí)間復(fù)雜度 \(O(n^22^n)\)。

題目

五道模板題：FMT/FWT，子集卷積，exp，ln，求逆。

P13275 [NOI2025] 集合

存在使用集合冪級(jí)數(shù)硬推的做法，但是本題解從更容易入手的容斥原理來(lái)做。

這種很多限制導(dǎo)致難以計(jì)算的題目很容易去想容斥，問題來(lái)了？我們?cè)搶?duì) $P\cap Q=\emptyset $ 容斥，還是對(duì)于 \(f(P)=f(Q)\) 容斥。都試一試，發(fā)現(xiàn)對(duì)于前者是 \(2^{2^n}\) 的，沒有前途。所以考慮后者，你直接對(duì)于 \(f(P)=f(Q)\) 這個(gè)東西想葉也很難直接做，比如說(shuō)你欽定什么，對(duì)具體哪個(gè)東西容斥？

再來(lái)一步枚舉，這個(gè)題就變得就清晰了。我們枚舉 \(S\)，考慮 \(f(P)=S，f(Q)=S\) 這種情況的答案，如果 \(f(P)\) 恰好等于 \(S\) 是難做的，故考慮容斥，枚舉 \(U\)，欽定 \(f(P)\) 的結(jié)果中 \(U\) 中的 \(1\) 必須出現(xiàn)，系數(shù)是 \((-1)^{|U|-|S|}\)。對(duì)于 \(f(Q)\) 的限制，也是同理枚舉 \(V\)。所以二元組 \((U,V)\) 對(duì)于 \(S\) 的容斥系數(shù)就是 \((-1)^{|U|+|V|-2|S|}=(-1)^{|U|+|V|}\)。接下來(lái)要考慮貢獻(xiàn)，由于是欽定，我們只需要對(duì)于 \(V\subset i\) 或者 \(U\subset i\) 的 \(i\) 進(jìn)行決定是否選擇，對(duì)于只是 \(U,V\) 中的一個(gè)的超集的 \(i\)，其方案數(shù)是 \(a_i+1\)，對(duì)于同時(shí)是 \(U,V\) 超集的 \(i\)，其方案數(shù)是 \(2a_i+1\)（要么不選，要么先選 \(U\) 還是 \(V\)，再選 \(a_i\) 種方案）。

暴力枚舉 \((U,V)\) 和 \(S\) 是 \(O(8^n)\) 的，由于 \(S\) 是 \(U\cap V\) 的子集，有一個(gè)想法是算出 \((U,V)\) 的方案和系數(shù)，貢獻(xiàn)到 \(U\cap V\) 這個(gè)集合上，然后再做一次高維后綴和對(duì)于每一個(gè) \(S\) 都統(tǒng)計(jì)出貢獻(xiàn)。但是這么做很唐，因?yàn)槲覀儾⒉恍枰蟪雒總€(gè) \(S\) 的答案，只需要求出總的答案，滿足條件的 \(S\) 有 \(2^{|U \cap V|}\) 種，直接計(jì)數(shù)就行了。

所以對(duì)于 \((U,V)\) 對(duì)于答案的貢獻(xiàn)是 \(2^{|U \cap V|}(-1)^{|U|+|V|}\prod\limits_{U\subset i,V\nsubseteq i}(a_i+1)\prod\limits_{U\nsubseteq i,V\subset i}(a_i+1)\prod\limits_{U\subset i,V\subset i}(2a_i+1)\)。

為了快速計(jì)算后面的那一坨乘積式，我們?cè)O(shè) \(f_s=\prod\limits_{s\subset i}a_i\)，\(g_s=\prod\limits_{s\subset i}\dfrac{2a_i+1}{(a_i+1)^2}\)。那么 \((U,V)\) 的權(quán)值為 \(f_Uf_Vg_{U\cup V}\)。同時(shí)改寫系數(shù) \(2^{|U\cap V|}=2^{|U|+|V|-|U\cup V|}\)，就可以將下標(biāo)全部轉(zhuǎn)化為 \(U\)，\(V\) 和 \(U\cup V\) 了，這個(gè)時(shí)候使用 or-FWT，就可以把 \(U,V\) 的貢獻(xiàn)放到 \(U\cup V\) 處進(jìn)行統(tǒng)計(jì)了。

但是有一個(gè)問題，就是我們 \(g\) 的分母為 \(a_i+1=0\) 的時(shí)候怎么辦？考慮擴(kuò)域，我們對(duì)于每個(gè)數(shù)字記錄 \((v,k)\) 代表其權(quán)值為 \(v\times 0^k\)。乘法的時(shí)候直接是 \(0\) 的個(gè)數(shù)相加。加法的時(shí)候，顯然只有 \(k\) 小那個(gè)會(huì)產(chǎn)生貢獻(xiàn)，如果相等就都加。減法的時(shí)候，\((v_1,k_1)-(v_2,k_2)\)，一定有 \(k_1\le k_2\)，當(dāng) \(k_1<k_2\) 的時(shí)候無(wú)貢獻(xiàn)，否則就是 \(v_1-v_2\)。

這題就成功解決了，時(shí)間復(fù)雜度 \(O(n2^n)\)。

三進(jìn)制 MEX 卷積

定義三進(jìn)制 \(\operatorname{mex}\) 運(yùn)算，先將兩個(gè)數(shù)字 \(a,b\) 進(jìn)行三進(jìn)制拆分，形如 \(a=\sum a_i3^i\)。\(\operatorname{mex}(a,b)=\sum\limits_{i=0}^{k-1}\operatorname{mex}(a_i,b_i)\)。也就是說(shuō)把每個(gè)數(shù)都拆成三進(jìn)制表示，然后對(duì)于每個(gè)三進(jìn)制位進(jìn)行 \(\operatorname{mex}\)。
定義三進(jìn)制 \(\operatorname{mex}\) 卷積為

\[h_s=\sum\limits_{\operatorname{mex}(L,R)=S}f_L\times g_S \]

給定長(zhǎng)度為 \(3^{n}\) 的 \(f\) 和 \(g\)，求解 \(h\)。\(n\le 10\)。

還是按照 FWT 那套方法，對(duì)于當(dāng)前的最高位的值進(jìn)行分類。

發(fā)現(xiàn)我們需要構(gòu)造四種乘法，

這樣子遞歸是 \(3^n\to 4^n\)，因?yàn)槿?xiàng)變四項(xiàng)。

逆變換，令上述分別為 \(A,B,C,D\)，\((A,B,C,D)\to (A,B-C,D-A-B-C)\)。

可以遞歸計(jì)算，時(shí)間復(fù)雜度是 \(O(n4^n)\)。

QOJ5089. 環(huán)覆蓋

給定一張 \(n\) 個(gè)點(diǎn)，\(m\) 條邊的簡(jiǎn)單無(wú)向圖，對(duì)每個(gè) \(i\in [0,m]\)，計(jì)算它只保留 \(i\) 條邊，使得剩下的圖是一個(gè)可環(huán)覆蓋圖的方案數(shù)。可環(huán)覆蓋的定義是，可以將邊集劃分成若干個(gè)子集，使得每個(gè)子集都形成一個(gè)環(huán)。

UVA13277 XOR Path

我咋想到點(diǎn)分治上面去了。

注意到異或是可以抵消的，而本題恰好是邊權(quán)，所以有 \(w(x,y)=w(1,x)\oplus w(1,y)\)，這樣子就和 \(\rm LCA\) 無(wú)關(guān)了，求出每個(gè)點(diǎn)到根的異或和，然后直接做一個(gè) xor-FWT 統(tǒng)計(jì)答案就做完了。

AGC034F RNG and XOR

FWT 版本的高斯消元。