FWT的本质与 k进制FWT/高维DFT的探究

FWT的本质与 $k$ 进制FWT/高维DFT的探究

我以前在学啥啊。。。

位与/位或FWT

这两个比较简单。（或许该叫FMT…但在此统一叫FWT吧）

对于$k$进制，定义$x\text{ or } y=\sum_i\max(x_i,y_i)k^i,x_i,y_i$ 为$k$进制下第$i$位，$\text{and}$ 定义为$x\text{ and } y=\sum_i\min(x_i,y_i)k^i$.

FWT的本质是将当前的集合幂级数看成向量（记为$\textbf{F},\textbf{G}$ ），左乘上矩阵$A$使得（也有人喜欢右乘，问题不大）

$(A\textbf{F})\cdot (A\textbf{G})=A(\vec{FG})$

其中左边的 $ \cdot $ 指按位相乘，$\vec{FG}$ 指$F$和$G$两个幂级数做位与/位或卷积后得到的幂级数看成向量。

另一个等价形式：

$(\sum_ja_{i,j}f_j)(\sum_ja_{i,j}g_j)=\sum_ja_{i,j}\sum_{x\text{ or }y=j} f_xg_y$

$or$可以换成$and$.

所以通常的FWT,即每一维长度为2，

$A(\text{or})=\begin{bmatrix} 1& 0\\ 1& 1\\ \end{bmatrix},A(\text{and})=\begin{bmatrix} 1& 1\\ 0& 1 \end{bmatrix}$

因此我们的代码里就是“右加左”，“左加右”了.

对于$k$进制，则有

$A(\text{or})=\begin{bmatrix} 1& 0& 0&\cdots &0\\ 1& 1& 0&\cdots &0\\ 1& 1& 1&\cdots &0\\ \vdots&\vdots&\vdots&\vdots&\vdots\\ 1&1&1&\cdots&1 \end{bmatrix},A(\text{and})=\begin{bmatrix} 1& 1& 1&\cdots &1\\ 0& 1& 1&\cdots &1\\ 0& 0& 1&\cdots &1\\ \vdots&\vdots&\vdots&\vdots&\vdots\\ 0&0&0&\cdots&1 \end{bmatrix}$

宏观上就是高维前缀和和高维后缀和. $A^{-1}$就是差分，就不列出了。

实现可以枚举间隔，然后每次拿出$k$个元素，看成向量去左乘$A$.

$k$进制，$n$维的位与/位或FWT ，直接做矩阵乘法是$O(k^nnk)$，记下前缀和/后缀和能做到$O(k^nn).$

const int MAXN = 100011;
ull a[MAXN];
void FWT(int K,int N)//OR
{
	int len=1;
	for(int i=1;i<=N;++i)len*=K;
	for(int cur=1;cur<len;cur*=K)
		for(int j=0;j<len;j+=cur*K)
			for(int k=0;k<cur;++k)
				for(int x=1;x<K;++x)
					a[j+cur*x+k]+=a[j+cur*(x-1)+k];
}

~~据说还可以每一维长度不一样~~

异或FWT/高维DFT(1)

~~注意有个(1)~~

对于$k$进制，定义$x\text{ xor } y=\sum_i(x_i+y_i(\text{ mod }k))k^i,x_i,y_i$ 为$k$进制下第$i$位.（即$k$进制不进位加法）

同样要找一个矩阵$A$使得

$(A\textbf{F})\cdot (A\textbf{G})=A(\vec{FG})$

冷静分析一下发现直接把DFT的范德蒙矩阵拉过来就行，即

$\begin{bmatrix} 1&1& 1&\cdots&1\\ 1&\omega_k^1&\omega_k^2&\cdots&\omega_k^{k-1}\\ 1&\omega_k^2&\omega_k^4&\cdots&\omega_k^{2(k-1)}\\ \vdots&\vdots&\vdots&\vdots&\vdots\\ 1&\omega_k^{k-1}&\omega_k^{(k-1)2}&\cdots&\omega_k^{(k-1)(k-1)}\\ \end{bmatrix}$

妙在$x\text{ xor } y=j\Leftrightarrow \omega_k^x\omega_k^y=\omega_k^j$ （这里$x,y$是指当前考虑的这一维上$x,y$的值）

所以也发现$k$进制FWT和高维DFT本质相同。

这里似乎只能暴力矩乘了，复杂度$O(k^nnk)$

IDFT就是乘上

$\begin{bmatrix} 1&1& 1&\cdots&1\\ 1&\omega_k^{-1}&\omega_k^{-2}&\cdots&\omega_k^{-(k-1)}\\ 1&\omega_k^{-2}&\omega_k^{-4}&\cdots&\omega_k^{-2(k-1)}\\ \vdots&\vdots&\vdots&\vdots&\vdots\\ 1&\omega_k^{-(k-1)}&\omega_k^{-(k-1)2}&\cdots&\omega_k^{-(k-1)(k-1)}\\ \end{bmatrix}$

最后除以$k^n$ 。

异或FWT/高维DFT(2)

如果模数没有$k$次单位根？

我们看个例题。

CF1103 E Radix sum

给一个长度为$n$的序列$A$,对所有$0\le i<n$求出选出$k$个（可以重复）元素使得10进制异或和为$i$的方案数模$2^{58}$

$n\le 10^5,a_i<10^5$

只需高维DFT然后点值上快速幂最后IDFT回去。

模数比较阴间，没有$\omega_{10}$也没有$10^5$的逆元。

$10^5$的逆元稍微好些，考虑$\frac{2^{64}}{2^{58}}=2^6>2^5$所以在模$2^{64}$意义下计算然后直接除$2^5$。然后$5^5$是有逆元的。

$\omega_{10}$真的没有，考虑扩域。将所有数表示为$\sum_{i=0}a_ix^i$的形式幂级数，加法定义为形式幂级数加法，乘法定义为形式幂级数卷积。

这里我们将所有数看为$a_0+a_1\omega_5+a_2\omega_5^2+a_3\omega_5^3+a_4\omega_5^4$的形式。下面证明这样做所得域是足够的。

考虑$\omega_5^5=1\Rightarrow \omega_5^5-1=0$ 。所以所有运算可以在模$\omega_5^5-1$ 意义下做，也就是幂级数模$\omega_5^5$做循环卷积。（模0不会有问题是相当于考虑$F=VG+R$,$G=\omega_5^5-1$ ）然后$\omega_{10}=\omega_{10}^6/(-1)=-\omega_5^3$，所以是足够的。

所有加法/乘法操作都对$a_0+a_1\omega_5+a_2\omega_5^2+a_3\omega_5^3+a_4\omega_5^4$这样的形式做就能实现高维DFT了。

最后还剩一个问题，如何从这个形式推出答案。

我们希望只有常数项非零，否则难以求答案。但模$\omega_5^5-1$不能保证。

考虑为什么不能保证，发现$x^5-1$在$\mathbf Q$上的因式分解为$(x-1)(1+x+x^2+x^3+x^4)$，可能有零因子。而五次分圆多项式$\Phi_5=1+x+x^2+x^3+x^4$ 在$\mathbf Q$上不可约因此可推得在$\text{mod }\Phi_5$意义下计算只有常数项非零。所以在$\text{mod }\Phi_5$意义下计算就好。

但是这样不太好算，但$\Phi_5|(x^5-1)$所以可以先$\text{mod }x^{5}-1$循环卷积最后摸一次$\Phi_5$.

复杂度$O(k^nnk^3)$,也可以做到$O(k^nnk^2)$.

My code