集合冪級數

在 FMT 和 FWT 里有提到過。

對于一個序列 \(a_0\sim a_N\)，定義一個多元多項式 \(A(x_1\sim x_n)=\sum_{0\le I<2^{n}}a_I\cdot x_1^{i_1}x_2^{i_2}\cdots x_n^{i_n}\)，其中 \(i_1\sim i_n\) 是 \(I\) 這個集合的二進制表示。

這個多項式有 \(2^n\) 項，每一項的系數就是 \(a\)。這個 \(A\) 叫做集合冪級數。可以類比序列對應到 OGF 上，集合就會對應集合冪級數。

相較于 FMT 和 FWT 處，我們進一步定義集合冪級數的乘法。這是一個比較有用的概念。

簡記集合冪級數為 \(A(x)=\sum a_Ix^I\)，給定 \(A(x)=\sum_{I}a_Ix^I,B(x)=\sum_{J}a_Jx^J\)，怎么定義 \(A(x)\cdot B(x)\)？

關鍵在于怎么定義單項式的相乘，也就是 \(x^I\cdot x^J\) 怎么定義。在普通單項式乘法里，\(x^I\cdot x^J=x^{I+J}\)。但是對于集合冪級數，我們有多種定義。

1. \(x^I\cdot x^J=x^{I\cup J}\)。

2. \(x^I\cdot x^J=x^{I\cap J}\)。

3. \(x^I\cdot x^J=x^{I\oplus J}\)。

無論對于哪種定義，都滿足交換律和結合律。同時，我們發現這三種定義和與、或、異或卷積都有關系。下面我們來看看。

引理：在 \(x^I\cdot x^J=x^{I\cup J}\) 時，\(A(x)\cdot B(x)\) 所得的系數剛好是 \(a,b\) 的或卷積。

證明：

同理，把或卷積替換為與卷積、異或卷積，證明都是類似的。

這個引理表明在做集合冪級數乘法時，仍然可以使用卷積快速求得結果。類比多項式乘法用 FFT 快速計算。

子集卷積

假設我們有兩個長為 \(2^n\) 的序列 \(a,b\)，定義其子集卷積 \(c=a*b\)，滿足：

就是或卷積額外要求其交集為空。也就是要求 \(J,K\) 是 \(I\) 的劃分。

這個問題可以 \(O(n^2\cdot 2^n)\) 求，而且有兩種解法。

法一

來個新定義。

這可以理解為一個拆分，把序列按下標的集合大小分為不同類。

觀察到 \(c_I=\sum_{t=0}^{|I|}\sum_{J\cup K=I}a^{(t)}_Jb^{(|I|-t)}_K\)。因為 \(J\cup K=I\) 且 \(J\cap K=\empty\)，所以 \(|J|+|K|=|I|\)。于是就可以枚舉 \(|J|=t\)，則有 \(|K|=|I|-t\)。

然后怎么求 \(c\)？

將 \(a^{(t)}\) 與 \(b^{(t')}\) 的或卷積記作 \(c^{(t,t')}\)。那么 \(c_I=\sum_{t+t'=|I|}c^{(t,t')}_I\)。

容易給出一個算法：

1. 預處理 \(c^{(t,t')}\)。

2. 枚舉 \(|I|=i\)。

3. 枚舉 \((t,t')\) 滿足 \(t+t'=i\)。

4. 將 \(c^{(t,t')}\) 中大小為 \(i\) 的項加入 \(c_I\)。

分析一下復雜度。

第一步預處理，\(O(n^2\cdot n\cdot 2^n)\)。之后統計答案，

還是太慢了，我們再來一個優化：

定義 \(c^{(i)}_I=\sum_{t+t'=i}c^{(t,t')}_I\)。目標轉化為求 \(c_I^{(0\sim n)}\)。

那 \(c^{(i)}\) 怎么求？

注：這里的點乘就是向量點乘。

注 2：這里能把 \(\mathrm{DMT}\) 拿進括號里，是因為它是線性變換。

先預處理 \(a^{(x)},b^{(x)}\) 的 \(\mathrm{DMT}\) 序列，是 \(O(2n\cdot n\cdot 2^n)=O(n^22^n)\) 的。

然后 \((\sum_{t+t'=i}\mathrm{DMT}(a^{(t)})\cdot \mathrm{DMT}(b^{(t')}))\) 這一部分的點乘是單次 \(O(2^n)\)，總共 \(O(n2^n)\) 的。

最后對每個 \(c^{(i)}\) 各做一次 \(\mathrm{iDMT}\)，單次 \(O(n2^n)\)，總共 \(O(n^22^n)\)。

總復雜度為 \(O(n^22^n)\)。

法二

需要用到占位集合冪級數。這個東西也很有用，對集合冪級數的 exp 和 ln 都有用。

下面給出它的定義。

設有一個長度 \(2^n\) 的序列 \(a_I\)。定義一個占位集合冪級數 \(A[z](x_1\cdots x_n)=\sum_{I}a_Ix^Iz^{|I|}\)，普通集合冪級數就是 \(A[1](x_1\cdots x_n)\)。注意 \(z\) 對應的是數字而不是集合。

占位集合冪級數也可以定義乘法：\(x^Iz^u\cdot x^Jz^v=x^{I\cup J}z^{u+v}\)。對與卷積和異或卷積也是類似的。不過這里要用來解決子集卷積就攜程或卷積的形式。

我們定義 \(x^Iz^u\) 是合法項，當且僅當 \(|I|=u\)。容易發現 \(I,J\) 不相交 \(\iff x^Iz^{|I|}\cdot x^Jz^{|J|}\) 為合法項。

簡寫 \(A[z](x_1\cdots x_n)\) 為 \(A[z]\)。

引理：設 \(c=a*b\)（子集卷積），\(a\rightarrow A[z],b\rightarrow B[z],c\rightarrow C[z]\)。有：\(A[z]B[z]\) 保留合法項后恰為 \(C[z]\)。

證明比較顯然。不合法項在子集卷積中是不會出現的。

保留合法項是很容易的，只要 \(O(2^n)\) 遍歷每一項判斷即可。那么問題變成求 \(A[z]B[z]\)。

法 1

令 \(A^{(i)}\) 為 \(a^{(i)}\) 的集合冪級數。這個 \(a^{(i)}\) 就是在法一中按集合大小分組的 \(a^{(t)}\)。\(B^{(i)}\) 類似定義。

枚舉 \(i\)，對于 \(A[z]\cdot B[z]\) 的 \(z^i\) 項，包含它的項為 \(\sum_{t+t'=i}A^{(t)}z^t\cdot B^{(t')}z^{t'}=\sum_{t+t'=i}(A^{(t)}B^{(t')})z^i\)。

而對于 \(A^{(t)}B^{(t')}\) 的處理，我們和上面一樣進行 \(\mathrm{iDMT},\mathrm{DMT}\)，利用 \(\mathrm{DMT}\) 的線性變換性質把集合冪級數的相乘轉化為向量的點乘，從而優化復雜度。

具體細節略去。這種方法本質和上面是相同的。不過是引入了 \(z\) 作為主元。

法 2

此種方法不同，它并非按 \(z\) 分類，而是把 \(z\) 看作參數。

把 \(A[z],B[z]\) 當作普通的集合冪級數，但是每一項的系數不是一個數，而是一個關于 \(z\) 的多項式。

具體而言，\(A[z]=\sum_{I}(a_Iz^{|I|})x^I\)，\(B[z]=\sum_{I}(b_Iz^{|I|})x^I\)。這里 \((a_Iz^{|I|})\) 和 \((b_Iz^{|I|})\) 看作系數。

計算 \(A[z]B[z]=\mathrm{iDMT}(\mathrm{DMT}(A[z])\cdot \mathrm{DMT}(B[z]))\)，現在的問題是對于系數是多項式的時候 \(\mathrm{DMT}\) 是怎么定義的。

其實沒有區別，\(\overline{a}_I=\sum_{J\subseteq I}a_I\)，不過前綴和變成了多項式的和。子集反演后也是一樣。

復雜度呢？

普通數組做 \(\mathrm{DMT}\) 是 \(O(n2^n)\) 的，但是現在系數是一個長度為 \(n\) 的多項式，所以復雜度是 \(O(n^22^n)\) 的。

對 \(A[z],B[z]\) 各自求 \(\mathrm{DMT}\)，復雜度 \(O(n^22^n)\)；讓兩個結果點乘，復雜度 \(O(2^n)\)；對點乘的結果再做 \(\mathrm{iDMT}\)，復雜度 \(O(n^22^n)\)。注意這里 \(\mathrm{iDMT}\) 的復雜度也是平方，因為 \(\mathrm{iDMT}\) 也要對多項式運算。