【預備知識】

子集反演公式：

如果用 \(g\) 直接暴力算 \(f\)，復雜度是 \(O(3^n)\) 的；使用 SOSDP 則可以把復雜度優化至 \(O(n\cdot 2^n)\)，具體不再贅述。

（\(f\) 子集反演算 \(g\) 也可以 SOSDP，同樣 \(O(n\cdot 2^n)\) 求）

【FMT】

FMT，快速莫比烏斯變換。它解決這么一個問題：

給定兩個序列 \(a_0\sim a_{2^n-1}\) 和 \(b_0\sim b_{2^n-1}\)，求序列 \(c_0\sim c_{2^n-1}\)，滿足：將下標 \(I\) 看作 \(n\) 大小的子集，\(c_I=\sum_{J\cup K=I}a_J\cdot b_K\)。

這種問題叫或卷積。

記 \(N=2^n\)，首先容易發現有一個 \(O(N^2)\) 的解法，即枚舉 \(J,K\) 累加答案。

FMT 可以用來解決這類問題，復雜度為 \(O(N\log N)=O(2^n\cdot n)\)，和 SOSDP 一樣。

下面介紹一下 FMT。

在開始之前，我們先回顧一下 FFT 是怎么做普通卷積的。

1. 對 \(a,b\) 分別做 DFT。

2. 求出 \(c\) 的 DFT。

3. 做 iDFT 求出 \(c\)。

這個做法的關鍵在于：存在一個變換 DFT，使得 DFT 和 iDFT 做起來都很快，而且 \(\mathrm{DFT}(a*b)=\mathrm{DFT}(a)\cdot \mathrm{DFT}(b)\)。

然后回到原問題。我們記 \(a\oplus b\) 為 \(a,b\) 的或卷積。

為了解決問題，我們希望找到變換 t 滿足：t 和 it 都很快，且 \(\mathrm{t}(a\oplus b)=\mathrm{t}(a)\cdot \mathrm{t}(b)\)。

一個很牛的事實是，這種變換確實存在，它們叫做 DMT 和 iDMT。即莫比烏斯變換和逆莫比烏斯變換。

介紹一下，\(\mathrm{DMT}(a)=(\overline{a_0},\dots,\overline{a_N})\)，其中 \(\overline{a_I}=\sum_{J\subseteq I}a_J\)。即把 \(a\) 變換為它的前綴和。顯然做這個變換和逆變換可用 SOSDP 在 \(O(n\cdot 2^n)\) 做，問題只剩下一個性質。

引理：\(c=a\oplus b\)，則 \(\overline{c}=\overline{a}\cdot\overline{b}\)。

證明：

因此可以 \(O(n\cdot 2^n)\) 求 \(a,b\) 的高維前綴和，乘起來之后再用子集反演 \(O(n\cdot 2^n)\) 求出 \(c\)。

另外，FMT 還可以做與卷積：把 \(\overline{a_I}=\sum_{J\subseteq I}a_J\) 換做 \(\overline{a_I}=\sum_{I\subseteq J}a_J\) 即可。證明過程也類似，方向換一下即可。

【FWT】

FWT，快速沃爾什變換，用于解決異或卷積問題。問題定義類似。

同樣地，我們要找一個變換 t，同樣滿足上面的性質。

而一樣很牛的事實是，這樣的變換也存在，叫做 DWT 和 iDWT。

\(\mathrm{DWT}(a)=\hat{a_0},\dots,\hat{a_N}\)，其中 \(\hat{a}_I\) 的定義不再是前后綴和：\(\hat{a}_I=\sum_{J}(-1)^{|I\cap J|}a_J\)。

看起來相當奇怪。

先說明 DWT 和 iDWT 都可以 \(O(n\cdot 2^n)\) 計算。

引理：\(\mathrm{iDWT}(a)=\mathrm{DWT}(a)/2^n\)。

引理證明：

轉證 \(\mathrm{DWT}(\mathrm{DWT}(a))=a\cdot 2^n\)，這和引理是等價的。

為什么呢？

令 \(b=\mathrm{DWT}(a)\)，由原本引理有 \(\mathrm{DWT}(b)=a\cdot 2^n\iff\mathrm{DWT}(b)/2^n=a\iff \mathrm{DWT}(b/2^n)=a\iff b/2^n=\mathrm{iDWT}(a)\)，能這么做的原因是 DWT 其實是線性變換，所以 \(\mathrm{DWT}(x)/C=\mathrm{DWT}(x/C)\)。

接下來證明轉化命題。不妨設 \(b=\mathrm{DWT}(a),c=\mathrm{DWT}(b)\)，求證 \(c_I=a_I\cdot 2^n\)。

觀察上式，\((I\oplus K)\cap J\) 有什么規律？當 \(I\oplus K=\empty\) 時，\(J\) 無論怎么取，系數都是 \(1\)，因此 \(\sum_J(-1)^{\cdots}=2^n\)；而 \(I\oplus K\neq \empty\) 時，系數會正負抵消，總共的貢獻為 \(0\)。

因此，\(\sum_{J}(-1)^{|(I\oplus K)\cap J|}=2^n\)，得證。

算法：只考慮怎么 DWT。

設 \(f\) 為 \(a\) 的前 \(2^{n-1}\) 項的 \(2^{n-2}\sim 2^0\) 位的結果，\(g\) 為后 \(2^{n-1}\) 項的 \(2^{n-2}\sim 2^0\) 位的結果。注意是只考慮更低位。

有結論：\(\mathrm{DWT}(a)=(\mathrm{DWT}(f)+\mathrm{DWT}(g),\mathrm{DWT}(f)-\mathrm{DWT}(g))\)，即前一半項是求和，后一半項是做差。

如果有這個結論，很顯然就可以分治 \(O(N\log N)=O(n\cdot 2^n)\) 來做。其實這和 FFT 非常相似，區別只在于 DFT 是按照奇偶分治下去，DWT 直接按下標分治。

問題只在于結論證明。

求證：\(\forall 0\le I< 2^{n-1}\)，\(\hat{a_I}=\hat{f_I}+\hat{g_I}\)，\(\hat{a}_{I+2^{n-1}}=\hat{f}_I-\hat{g}_I\)。

證明：

證畢。

然后說明 \(\mathrm{DWT}(a\oplus b)=\mathrm{DWT}(a)\cdot \mathrm{DWT}(b)\)。

證明：

引理：\((-1)^{|I\oplus J|}=(-1)^{|I|}\cdot (-1)^{|J|}\)。

比較顯然，因為異或后受到影響的只有同時在 \(I,J\) 中的元素，左邊會讓它們的影響變成 \(1\)，而右邊在 \(I,J\) 中各算一個 \(-1\)，乘起來還是 \(1\)。

證明：

【深入理解】

可能會覺得 DMT, DWT 的式子比較生硬，于是我們深入理解一下這兩個東西到底在干嘛。

DFT 是在做點值，DMT 和 DWT 其實也是在做另一種意義上的點值。

具體來說，我們需要用到集合冪級數。

對于一個序列 \(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 上。簡記 \(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}\) 為 \(A(x)=\sum_{I}a_Ix^I\)。

看看 DMT 是在干嘛。令 \(J=(j_1,\dots,j_n)\in \{0,1\}^n\)，即一個集合。

注意到當 \(I\not\subseteq J\)，存在 \(i_t=1,j_t=0\)，此時有 \(j_t^{i_t}=0\)，所以 \(j_1^{i_1}\cdots j_n^{i_n}=0\)。

而 \(I\subseteq J\) 時，\((i_t,j_t)=(0,0)/(0,1)/(1,1)\)，\(j_t^{i_t}=1\)，所以 \(j_1^{i_1}\cdots j_n^{i_n}=1\)。

因此，\(A(J)=\sum_{I\subseteq J}a_I=\overline{a}_J\)。

所以 DMT 計算 \(\overline{a}\) 實際上是求出了 \(A\) 在 \(\{0,1\}^n\) 這 \(2^n\) 個點處的值。

再看看 DWT 是在干嘛。令 \(J=(j_1,\dots,j_n)\in \{0,1\}^n\)，即一個集合。

那么 \(P=((-1)^{j_1},(-1)^{j_2},\dots,(-1)^{j_n})\in \{-1,1\}^n\)。

注：向量 \(a,b\) 的點乘 \(a\cdot b=\sum a_ib_i\)。上面 \(i\cdot j\) 實際上是把 \(i,j\) 兩個集合看作了向量（或者說 01 串）進行運算。

而 \(i\cdot j\) 在某一位上取 \(1\)，當且僅當這一位上 \(i,j\) 都是 \(1\)，所以：

所以 DWT 實際上是求出了 \(A\) 在 \(\{-1,1\}^n\) 這 \(2^n\) 個點處的值。

總之，FFT, FMT, FWT 都是在先點值后插值。

例題

經驗：什么涉及位運算，什么就作為集合冪級數的指數。

例如要求一些東西的與等于 \(p\)，放到集合冪級數的指數上，定位乘法為與卷積后，答案就是 \(x^p\) 的系數。

Nim (Topcoder 11469)

問有多少序列 \((i_1\sim i_m)\) 滿足：

1. \(i_1\oplus\cdots\oplus i_m=0\)。

2. \(1\le i_j\le k\)。

3. \(i_j\) 為質數。

\(m\le 10^9,k\le 50000\)。

構造一個序列 \(a_0\sim a_{65536}\)，使 \(a_I=1\iff 1\le I\le K,I\in Prime\)。

構造一個集合冪級數 \(A(x)=\sum a_Ix^I\)。

在乘法定義為異或卷積（\(a_Ix^I\cdot b_Jx^J=a_Ib_Jx^{I\oplus J}\)）時，\(A^m(x)\) 中 \(x^0\) 的系數就是答案。

那 \(A^m(x)\) 怎么算？

因此只要做一次 \(\mathrm{DMT}\)，然后讓所得序列的每一項變成 \(m\) 次方，再做一次 \(\mathrm{iDMT}\) 即可。注意這里是點乘 \(m\) 次不是卷積 \(m\) 次。

這題可以類比多項式快速冪：\(f^m(x)=\exp \ln f^m(x)=\exp m\ln f(x)\)。

CF449D

給定 \(a_1\sim a_n\)，計數 \((1\le i_1<\cdots<i_k\le n)\)，使 \(a_{i_1}\,\mathrm{and}\,a_{i_2}\,\mathrm{and}\cdots\mathrm{and}\,a_{i_k}=0\)。

\(n,a_i\le 10^6\)。

考慮取 \(u=2^{20}-1\)。定義集合冪級數 \(F(x)=\prod(x^{a_i}+x^u)\)。這里 \(x^{a_i}\) 和 \(x^u\) 都是集合冪級數，\(u\) 相當于全集。也就是說，令 \(A(x)=\sum_{I}[I=a_i]x^I,U(x)=\sum_{U}[I=U]x^I\)，則 \(x^{a_i}+x^u=A(x)+U(x)\)。

令乘法為與卷積，答案就是 \(F(x)\) 中 \(x^0\) 的系數。這也說明為什么取 \(u=2^{20}-1\)，因為全集是與運算的單位元。

問題轉化為求 \([x^0]F(x)\)。令 \(\mathrm{DMT'}\) 為與卷積的點值。

\(F(x)=\mathrm{iDMT'}(\mathrm{DMT'}(x^{a_1}+x^u)\cdots \mathrm{DMT'}(x^{a_n}+x^u))\)。注意在做了 \(\mathrm{DMT'}\) 后的乘法是點乘。

注意到 \(x^{a_i}+x^u\) 每一項的系數只有在 \(a_i,u\) 處才取 \(1\)，其余為 \(0\)。

所以做 \(\mathrm{DMT'}\) 后，每一項系數為 \(1/2\)。當 \(I\subseteq a_i\) 時為 \(2\)，其余為 \(1\)。（\(\check{a}_I=\sum_{I\subseteq J}a_J\)）

這有什么用呢？記 \(\check{S}_I=(\prod (x^{a_i}+x^u))_I\)，有 \(\check{S}_I=2^{t_I}\)，其中 \(t_I\) 表示 \(a_1\sim a_n\) 中包含 \(I\) 的個數。

那么問題轉化為求 \(t_0\sim t_{2^n-1}\)，即給定一些集合，求每個集合被多少個包含。這也是 SOSDP 能做的。如果要類比 \(\mathrm{DMT'}\)，令 \(cnt(J)\) 為 \(a_1\sim a_n\) 中 \(J\) 的個數。則 \(t_I=\sum_{I\subseteq J}cnt(J)\)，也是后綴和。

那么這一題就做完了，復雜度 \(O(20\cdot 2^{20})\) 求 \(t_0\sim t_{2^n-1}\)，然后 \(O(20\cdot 2^{20})\) 做一次 \(\mathrm{iDMT'}\) 得到 \(F(x)\)，答案取 \(x^0\) 系數。