题解 P4717 【【模板】快速莫比乌斯/沃尔什变换 (FMT/FWT)】
以下是一个偏向于初学者的题解。
卷积的定义
对于一个序列，将其中元素一一映射到一个多项式函数的系数上，
这个多项式函数便叫做该序列的生成函数。
形式化地讲，对于序列
卷积即为生成函数的乘积在对应序列的变换上的的抽象，
“卷”即为其作用效果，“积”即为其本质。
对于序列
FFT计算的是循环卷积，也即
卷积的基本性质
-
f\otimes g=g\otimes f 显而易见的交换律，用定义
(f\otimes g)_k=\displaystyle\sum_{i+j=k}f_i\times g_j ，
乘法交换律a\times b=b\times a 即可证明。 -
证明： $[f\otimes(g\otimes h)]_n=\displaystyle\sum_{a+b=n}f_a\times(g\otimes h)_b =\sum_{a+b=n}f_a\sum_{i+j=b}g_ih_j=\sum_{a+(i+j)=n}f_ag_ih_j=\sum_{(a+i)+j=n}f_ag_ih_j 反向推导即可得证。
-
其中 $(f\oplus g)_k=af_k+bg_k$，$a,b$ 为常数 证明：$[(f\oplus g)\otimes h]_k=\displaystyle\sum_{i=0}^k(f\oplus g)_ih_{k-i}=\sum_{i=0}^k (af_i+bg_i)h_{k-i} =a(f\otimes h)_k+b(g\otimes h)_k=[(f\otimes h)\oplus(g\otimes h)]_k
位运算卷积定义及其性质
一般的卷积满足
类似的，对于序列
可以定义位运算卷积
还有
-
由于 $a\operatorname{xor}b=b\operatorname{xor}a$，根据定义显然成立。 $\operatorname{and},\operatorname{or}$ 同样满足此性质，原因同上。 -
证明： $[f\otimes_\text{xor}(g\otimes_\text{xor} h)]_n=\displaystyle\sum_{a\operatorname{xor}b=n}f_a\times(g\otimes_\text{xor} h)_b =\sum_{a\operatorname{xor}b=n}f_a\sum_{i\operatorname{xor}j=b}g_ih_j=\sum_{a\operatorname{xor}(i\operatorname{xor}j)=n}f_ag_ih_j=\sum_{(a\operatorname{xor}i)\operatorname{xor}j=n}f_ag_ih_j 反向推导即可得证。
\operatorname{and},\operatorname{or} 同理。 -
证明同加法卷积，$\operatorname{and},\operatorname{or}$ 同理。
FFT 的性质
在 FFT 的实现过程中，我们得到了两个很重要的处理方法：
奇偶分段和蝴蝶变换。
现在让我们仔细审视一下 FFT 的变换过程。
分治证明式：
实际变换过程：
注意到单次卷积 DFT
（ DFT 时向下递归，点乘时到达底部，IDFT 时向上回溯）
那么 IDFT 就是：
设
其中
已知
其中
考虑蝴蝶变换，发现
其中
显然，逆变换时只要对如上两式加减消元即可。
于是可得
向下递归，计算出卷积
回溯时，逆变换为
注意到系数
类似的，可以得到
自此，我们已经可以
FWT 的性质
为了方便使用，我们希望 FWT 满足与 FFT 类似的性质。
-
F_\text{xor}^{-1}(F_\text{xor}(f))=f 证明：在序列长度为
2^0=1 时，F_\text{xor}(f)=F^{-1}_\text{xor}(f)=f ，性质显然成立
序列长度>1 时，考虑不做卷积，只有蝴蝶变换，得到\begin{matrix} & f_0 & f_1 \\ F_\text{xor}: & \Downarrow & \Downarrow \\ & f_0+f_1 & f_0-f_1 \\ \text{递归:} & \Downarrow & \Downarrow \\ & g_0=F^{-1}_\text{xor}(F_\text{xor}(f_0+f_1)) & g_1=F^{-1}_\text{xor}(F_\text{xor}(f_0-f_1)) \\ F^{-1}_\text{xor}: & \Downarrow & \Downarrow \\ & \dfrac{1}{2}(g_0+g_1) & \dfrac{1}{2}(g_0-g_1) \end{matrix} 显然
\dfrac{1}{2}[(f_0+f_1)+(f_0-f_1)]=\frac{1}{2}(2f_0)=f_0 \dfrac{1}{2}[(f_0+f_1)-(f_0-f_1)]=\frac{1}{2}(2f_1)=f_1 便可递归证明。
$$ \begin{matrix} F_\text{and}: & (a_0+a_1)-a_1=a_0 & a_1=a_1 \\ F_\text{or}: & a_0=a_0 & (a_1+a_0)-a_0=a_1 \end{matrix} $$ -
F_\text{xor}(F^{-1}_\text{xor}(f))=f,F_\text{xor}(f\oplus g)=F_\text{xor}(f)\oplus F_\text{xor}(g) 同上，此处不再赘述。
-
F_\text{xor}(f\otimes_\text{xor} g)_k=F_\text{xor}(f)_k\times F_\text{xor}(g)_k 证明：已知
f\otimes_\text{xor}g=F^{-1}_\text{xor}(F_\text{xor}(f)\bullet F_\text{xor}(g)) ，则F_\text{xor}(f\otimes_\text{xor}g)=F_\text{xor}(F^{-1}_\text{xor}(F_\text{xor}(f)\bullet F_\text{xor}(g)))=F_\text{xor}(f)\bullet F_\text{xor}(g)
总结与代码
经过严谨的推导，我们得出了 FWT 的实现，
并发现其具有与 FFT 类似的性质，这为我们解题带来了极大的方便。
#include<stdio.h>
#include<string.h>
typedef unsigned char byte;
typedef unsigned long long ull;
typedef long long ll;
typedef unsigned int word;
struct READ{
char c;
inline READ(){c=getchar();}
template<typename type>
inline READ& operator>>(register type& num){
while('0'>c||c>'9') c=getchar();
for(num=0;'0'<=c&&c<='9';c=getchar())
num=num*10+(c-'0');
return *this;
}
};//快读快写
#define mx 17
#define mx_ 16
word root[1<<mx],inv[1<<mx],realid[1<<mx];
const word mod=998244353;
inline ull pow(register ull a,register word b){
register ull ans=1;
for(;b;b>>=1){
if(b&1) (ans*=a)%=mod;
(a*=a)%=mod;
}
return ans;
}//快速幂
#define loading() \
register ull num1=pow(3,(mod-1)>>mx); \
register ull num2=pow(num1,mod-2); \
register word head,i; \
register byte floor; \
register ull ni2=pow(2,mod-2); \
root[0]=inv[0]=1; \
for(i=1;head=i,i<(1<<mx);++i){ \
root[i]=num1*root[i-1]%mod; \
inv[i]=num2*inv[i-1]%mod; \
for(floor=0;floor<mx;++floor,head>>=1) \
realid[i]=realid[i]<<1|(head&1); \
}
//单位根及下标翻转初始化
#define load() \
register ull num1,num2;\
register word head,i; \
register byte floor
//floor 变换区间大小
//head 变换区间头指针
//i 变换位置
#define nttfor(size) \
for(floor=0;floor<(size);++floor) \
for(head=0;head<(1u<<(size));head+=1u<<(floor+1)) \
for(i=0;i<(1u<<(floor));++i)
//FFT/FWT循环
#define ntt(num,root)( \
num1=(num)[head+i], \
num2=(num)[head+i+(1<<floor)], \
(num)[head+i]=(num1+((num2*=root[i<<(mx_-floor)])%=mod))%mod, \
(num)[head+i+(1u<<floor)]=(num1+mod-num2)%mod)
//FFT蝴蝶变换
#define _and(num)( \
num1=(num)[head+i], \
(num)[head+i]=(num1+(num)[head+i+(1u<<floor)])%mod)
//FWT and 蝴蝶变换
#define and_(num)( \
num1=(num)[head+i], \
(num)[head+i]=(num1+mod-(num)[head+i+(1u<<floor)])%mod)
//逆FWT and 蝴蝶变换
#define _or(num)( \
num2=(num)[head+i+(1<<floor)], \
(num)[head+i+(1u<<floor)]=(num2+(num)[head+i])%mod)
//FWT or 蝴蝶变换
#define or_(num)( \
num2=(num)[head+i+(1<<floor)], \
(num)[head+i+(1u<<floor)]=(num2+mod-(num)[head+i])%mod)
//逆FWT and 蝴蝶变换
#define _xor(num)( \
num1=(num)[head+i], \
num2=(num)[head+i+(1<<floor)], \
(num)[head+i]=(num1+mod-num2)%mod, \
(num)[head+i+(1<<floor)]=(num1+num2)%mod)
//FWT xor 蝴蝶变换
#define id(size,i) (realid[i]>>(mx-(size)))
//下标二进制翻转的编号
#define FOR(size) for(i=0;i<1u<<(size);i++)
word eax[1<<mx],ebx[1<<mx],ecx[1<<mx],edx[1<<mx],eex[1<<mx],efx[1<<mx];
int main(){
byte size;
register READ cin;
cin>>size;
loading();
FOR(size) cin>>eax[id(size,i)];
FOR(size) cin>>ebx[id(size,i)];
memcpy(ecx,eax,4u<<size);
memcpy(edx,ebx,4u<<size);
memcpy(eex,eax,4u<<size);
memcpy(efx,ebx,4u<<size);
nttfor(size){
_or(eax),_or(ebx);
_and(ecx),_and(edx);
}
FOR(size){
head=id(size,i);
root[head]=(ull)(eax[i])*ebx[i]%mod;
inv[head]=(ull)(ecx[i])*edx[i]%mod;
}
nttfor(size) or_(root),and_(inv);
FOR(size) printf("%u ",root[i]);
putchar('\n');
FOR(size) printf("%u ",inv[i]);
putchar('\n');
nttfor(size) _xor(eex),_xor(efx);
FOR(size) root[id(size,i)]=(ull)(eex[i])*efx[i]%mod;
nttfor(size) _xor(root);
num1=pow(ni2,size);
FOR(size) printf("%u ",num1*root[i]%mod);
// $F_\text{xor}^{-1}(f)_k=2^{-n}F_\text{xor}(F)_k$
return 0;
}