Fast Transform Algorithms

这里放所有变换,FFT,NTT,FWT,FMT,的知识,etc.

Flu发现好像关于这些的算法开三倍空间一般就够用了.

FFT

FFT解决的问题是在O(nlogn)时间内求解多项式相乘,长这样:

$$C_k=\sum_{i+j=k}A_iB_j$$

这是板子.

FFT的精度

N = 1000000 X = 6000
N = 100000 X = 40000
N = 10000 X = 300000
N = 1000 X = 1000000
N = 100 X = 6000000
N = 10 X = 20000000
（精度值在1000000下为6000，对拍程序为NTT）

例题

1. 给两个序列 $a,b$ 你可以对序列进行旋转操作(如 $1,2,3,4,5$ 可以变成 $2,3,4,5,1$ )你也可以对任意序列进行全部加 $x(x>0)$ 的操作,定义差异值是下面的式子,求两个数列最小差异值.

   $$s=\sum_{i=1}^n(a_i-b_i)^2$$

   首先,对于一个数列加x和另一个数列-x效果相当,于是式子先转成

   $$s=\sum_{i=1}^n(a_i+x-b_i)^2,-m\le x\le m$$

   展开式子得

   $$s=\sum_{i=1}^na_i^2+\sum_{i=1}^nb_i^2+nx^2+2x(\sum_{i=1}^na_i-\sum_{i=1}^nb_i)-2\sum_{i=1}^na_ib_i$$

   然后发现只有最后的部分和旋转有关,是不确定的,其他都可以快速找出来,现在要求 $\sum_{i=1}^na_ib_i$ 的最大值.

   我们先把a反过来,式子变成 $\sum_{i=1}^na'_{n-i+1}b_i$ 发现这是一个卷积形式,然后 倍长a 和b进行卷积,答案里面的 n+1~2n 项就是最大值(妙啊).

NTT

会炸精度…实际有效的精度大概就是两位.

例题:P2000拯救世界,计算 $(a+1)(a+2)(a+3)(a+4)/24$ ,使用NTT先计算出 $(a+1)*(a+2)$ 然后要 处理进位 ,然后再乘上后半部分.

原根表

转载,其中质数满足 $prime=r\cdot2^k+1$ ,ord是原根.

$r\cdot2^k+1$	r	k	$ord$
3	1	1	2
5	1	2	2
17	1	4	3
97	3	5	5
193	3	6	5
257	1	8	3
7681	15	9	17
12289	3	12	11
40961	5	13	3
65537	1	16	3
786433	3	18	10
5767169	11	19	3
7340033	7	20	3
23068673	11	21	3
104857601	25	22	3
167772161	5	25	3
469762049	7	26	3
998244353	119	23	3
1004535809	479	21	3
2013265921	15	27	31
2281701377	17	27	3
3221225473	3	30	5
75161927681	35	31	3
77309411329	9	33	7
206158430209	3	36	22
2061584302081	15	37	7
2748779069441	5	39	3
6597069766657	3	41	5
39582418599937	9	42	5
79164837199873	9	43	5
263882790666241	15	44	7
1231453023109121	35	45	3
1337006139375617	19	46	3
3799912185593857	27	47	5
4222124650659841	15	48	19
7881299347898369	7	50	6
31525197391593473	7	52	3
180143985094819841	5	55	6
1945555039024054273	27	56	5
4179340454199820289	29	57	3

为什么是这些数?

只有这样才能找到所需的原根,且 $P=2^a*X+1$ 适用的最大多项式长度为 $2^a$ .

FWT 快速沃尔什变换

用于求解 $C_i=\sum_{k\oplus j=i}A_iB_j$ 的问题,其中 $\oplus$ 代表& | & 三种运算符,还可以解决子集卷积问题.

FMT 快速莫比乌斯变换

莫比乌斯反演在集合上的结论:

$$g(S)=∑_{T⊆S}(−1)^{|S|−|T|}f(T)$$

有人说FMT是高阶的容斥原理.

例题

1. 给出n个数,计算每个数的 $E_i$ ,有

   $$E_i=\frac{F_i}{q_i}$$ $$F_j=\sum_{i=1}^{j-1}\frac{q_i\times q_j}{(i-j)^2}-\sum_{i=j+1}^n\frac{q_i\times q_j}{(i-j)^2}$$

   先推式子:

   $$E_j=\sum_{i=1}^{j-1}\frac{q_i}{(i-j)^2}-\sum_{i=j+1}^n\frac{q_i}{(i-j)^2}$$

   令 $g(i)=1/i^2$ ,g(0)=0 有

   $$E_j=\sum_{i=0}^{j}q_ig(i-j)-\sum_{i=j}^nq_ig(i-j)$$

   发现前半部分是卷积形式,直接FFT即可.看后半部分,把初始j带进去得到

   $$E_j=\sum_{i=0}^{j}q_ig(i-j)-\sum_{i=0}^nq_{i+j}g(i)$$

   引入 $q’(i)=q(n-i)$ ,原式得

   $$E_j=\sum_{i=0}^{j}q_ig(i-j)-\sum_{i=0}^{n-j}q'_{n-i-j}g(i)$$

   至此,两个式子都变成了卷积形式,直接FFT计算即可.但是后面半个部分是上界 $n-j$ 的,注意最后减掉的时候别减错了.

2. 子集卷积 :计算

   $$C_k​=\sum_{i\&j=0}^{i|j=k}A_i​B_j$$

   记|S|表示集合S的元素个数,∗表示子集并卷积运算,即

   $$h_i=\sum_{j \cup k=i}f_j\times g_k$​$$

   第一个限制 $i∪j=k$ 容易处理,直接FWT计算子集并卷积即可.
   第二个限制 $i∩j=∅$ ,等价于 $|i|+|j|=|i∪j|$ .我们再开一维记录集合中的元素个数即可.

   具体地，令 $f_{i,j}=\begin{cases}a_j(|j|=i)\\0\end{cases}$ , $g_{i,j}=\begin{cases}b_j(|j|=i)\\0\end{cases}$ ,有 $h_i=\sum_{k=0}^if_k*g_{i-k}$ .最后我们所求的答案 $c_i=h_{|i|,i}$ ,复杂度 $O(n^22^n)$ .

   代码实现:先读入,用popcount计算有多少个1,存进去,然后对 f[i],g[i] 每一个二进制多少个进行 FWT_or ,然后h直接乘,取模,然后对h进行 IFWT_or ,最后输出,瓶颈在于卷积的计算.

3. (bzoj4589)从m个质数中选出n个数(可以重),让他们的抑或和是0,有多少种情况? ($1\le n\le10^9,m\le50000$)

   从生成函数的角度考虑:设数组f表示当前抑或和是i时的情况数,初始状况就是每个质数的位置填1,然后答案就是f使用FWT抑或卷积,卷积n次,最后取0的位置即可,套一个快速幂.复杂度 $O(m\log n)$ .

   代码实现:发现FWT_xor卷积具有结合性,也就是说,假设 $f’$ 表示 $fwt(f)$ ,有 $f*f*g=f'f'g'$ 不需要进行FWT的多余还原操作,复杂度并不是 $O(m\log m\log n)$ .

ref

1