0%

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$使得(也有人喜欢右乘,问题不大)

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

另一个等价形式:

$or$可以换成$and$.

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

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

对于$k$进制,则有

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
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$使得

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

妙在$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就是乘上

最后除以$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