当前位置: 首页 > news >正文

位运算快速卷积 快速沃尔什变换 FWT

用于解决一类位运算快速卷积问题:
\(C_{k}=\sum_{i\oplus j}A_i\times B_j\),其中 \(\oplus\) 为某种位运算,可以取按位或、按位与或按位异或。

P4717 【模板】快速莫比乌斯/沃尔什变换 (FMT/FWT)

概论

模仿(笔记)多项式基础 FFT 快速傅里叶变换 NTT 快速数论变换,我们尝试把需要操作的值都放在一个多项式的系数上,然后用一些快速的方法把它们变成点值的形式(其中我们会需要每个 \(x^k\),这是我们需要构造的),\(\Theta(n)\) 相乘,然后再用逆变换把这个东西变回系数的形式。

FWT

根据概论,我们不妨令点值 \(\text{FWT}(A)[i]=\sum_{j=0}^{n-1} A_j\times c(i,j)\),其中 \(c(i,j)\)\(A_j\)\(\text{FWT}(A)[i]\) 的贡献系数,类比 FFT 可以理解为幂级数中的 \(x^i\)。这个东西和 \(x^i\) 同时又有本质不同,我们不需要依赖 \(n\) 个本质不同的单位根分别带入求到点值再求逆变换,而是在位运算过程中可以分治处理。

根据点值性质,\(\text{FWT}(A)[i]\cdot\text{FWT}(B)[i]=\text{FWT}(C)[i]\),拆开可以得到:

\[\begin{aligned} \sum_{j=0}^{n-1}A_j\times c(i,j)\sum_{k=0}^{n-1}B_k\times c(i,k)&=\sum_{p=0}^{n-1}C_p\times c(i,p)\\ \sum_{j=0}^{n-1}\sum_{k=0}^{n-1}c(i,j)c(i,k)A_jB_k&=\sum_{p=0}^{n-1}C_p\times c(i,p)\\ \end{aligned} \]

根据 \(C_{k}=\sum_{i\oplus j}A_i\times B_j\)

\[\sum_{j\oplus k=p}c(i,j)\times c(i,k)=c(i,p)\\ c(i,j)\times c(i,k)=c(i,j\oplus k) \]

性质 1,这是一条关键性质。

同时,由于位运算每位的独立性,\(c\) 还具有性质 2\(c(i,j)=c(i_0,j_0)c(i_1,j_1)c(i_2,j_2)\dots\)。为什么是累乘是因为我们选用了乘法作为卷积的内置运算符号,这和上面那条性质是相符的。

接下来我们考虑求出一些合法的 \(c\) 后如何快速计算 \(\text{FWT}\)

暴力是 \(O(n^2)\) 的,我们预期达到 \(O(n\log n)\),那直接从低到高按位考虑合并答案。由于位运算每一位的独立性,我们不需要像 FFT 那样奇偶拆半(单位根加速的需要),而是可以直接利用最高位为 \(0/1\) 左右拆半。这样考虑的好处是去掉了蝴蝶变换这一优化,且可以利用二进制位直接处理。

由于性质 2,让 \(i',j'\) 分别表示 \(i,j\) 去掉最高位后的数,我们可以如此按位拆开每个分治过程:

\[\text{FWT}(A)[i]=\sum_{j=0}^{n/2-1}c(i_0,0)c(i',j')A_j+\sum_{j=n/2}^{n-1}c(i_0,1)c(i',j')A_j\\ \text{FWT}(A)[i]=c(i_0,0)\sum_{j=0}^{n/2-1}c(i',j')A_j+c(i_0,1)\sum_{j=n/2}^{n-1}c(i',j')A_j \]

于是每次计算出 \(\sum_{j=0}^{n/2-1}c(i',j')A_j\) 这样的子问题即可。

转移矩阵构造

根据性质 2,我们只需要构造出 \(c([0,1],[0,1])\) 就相当于构造出了所有 \(c\)。我们还要解决的是 FWT 如何求逆?有如下公式:

\[\text{FWT}(A)[i]=\sum_{j=0}^{n-1}c(i,j)A_j\\ A_j=\sum_{i=0}^{n-1}c^{-1}(i,j)\text{FWT}(A)[i] \]

类似莫比乌斯反演和二项式反演,我没法给出很严谨的推导过程,但是不妨代入下式到上式理解一下。此外,一个矩阵 \(A\) 的逆定义为 \(A\times B=B\times A=E\) 的矩阵 \(B\),这也代表了 \(A\) 不能存在某一行或某一列全为 \(0\),否则没有逆。

下文 \(\oplus\) 统一表示按位异或,\(\cup\) 表示按位或,\(\cap\) 表示按位与。

可以记一下结论,构造过程参考位运算卷积(FWT) & 集合幂级数。

或矩阵

我们构造矩阵需要满足 \(c(i,j)c(i,k)=c(i,j\cup k)\)

\[\begin{bmatrix} 1 & 0\\ 1 & 1 \end{bmatrix} \]

比较自然地,我们发现这个东西实际上就是高位为 \(0\) 只取 \(0\) 的贡献,高位为 \(1\)\(0\)\(1\) 的贡献,也就是这个东西实际上是在做子集卷积((笔记)Sum over Subsets SOS 子集 DP 高维前缀和)。

主包没学过矩阵相关,只能从定义入手推一下逆:

\[\begin{bmatrix} 1 & 0\\ 1 & 1 \end{bmatrix} \times \begin{bmatrix} a_{0,0} & a_{0,1}\\ a_{1,0} & a_{1,1} \end{bmatrix} = \begin{bmatrix} a_{0,0} & a_{0,1}\\ a_{1,0} & a_{1,1} \end{bmatrix} \times \begin{bmatrix} 1 & 0\\ 1 & 1 \end{bmatrix} = \begin{bmatrix} 1 & 0\\ 0 & 1 \end{bmatrix} \]

大致可以列几个式子:

\[\begin{cases} a_{0,0}+a_{0,1}=1\\ a_{0,0}=1\\ a_{1,1}=1\\ a_{0,0}+a_{1,0}=0 \end{cases} \]

因此:

\[\begin{cases} a_{0,0}=1\\ a_{0,1}=0\\ a_{1,0}=-1\\ a_{1,1}=1 \end{cases} \]

即逆矩阵:

\[\begin{bmatrix} 1 & 0\\ -1 & 1 \end{bmatrix} \]

感性理解构造其实可以拆开分治过程:

\[\text{FWT}(A)[i]=\text{FWT}(A_0)[i]\\ \text{FWT}(A)[i+n/2]=\text{FWT}(A_0)[i]+\text{FWT}(A_1)[i]\\ \text{IFWT}(A)[i]=\text{IFWT}(A_0)[i]\\ \text{IFWT}(A)[i+n/2]=\text{IFWT}(A_1)[i]-\text{IFWT}(A_0)[i]\\ \]

有点像前缀和和差分的关系。

与矩阵

构造:

\[\begin{bmatrix} 1 & 1\\ 0 & 1 \end{bmatrix} \]

逆:

\[\begin{bmatrix} 1 & -1\\ 0 & 1 \end{bmatrix} \]

异或矩阵

\[\begin{bmatrix} 1 & 1\\ 1 & -1 \end{bmatrix} \]

逆:

\[\begin{bmatrix} 0.5 & 0.5\\ 0.5 & -0.5 \end{bmatrix} \]

Code

点击查看代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL MOD=998244353,inv2=(MOD+1)/2;
const int N=17;
const LL cOR[2][2]={{1,0},{1,1}},cAND[2][2]={{1,1},{0,1}},cXOR[2][2]={{1,1},{1,MOD-1}},cnOR[2][2]={{1,0},{MOD-1,1}},cnAND[2][2]={{1,MOD-1},{0,1}},cnXOR[2][2]={{inv2,inv2},{inv2,MOD-inv2}};
int n;
LL A[1<<N],B[1<<N],FWTA[1<<N],FWTB[1<<N];
LL C[1<<N],FWTC[1<<N];
void FWT(LL *R,LL *FWTR,const LL c[2][2],int len){if(len==1){FWTR[0]=R[0];return ;}int half=len>>1;FWT(R,FWTR,c,half);FWT(R+half,FWTR+half,c,half);for(int i=0;i<half;i++){LL pre=FWTR[i],suf=FWTR[i+half];FWTR[i]=(c[0][0]*pre%MOD+c[0][1]*suf%MOD)%MOD;FWTR[i+half]=(c[1][0]*pre%MOD+c[1][1]*suf%MOD)%MOD;}
}
void solve(const LL c[2][2],const LL cn[2][2]){FWT(A,FWTA,c,n);FWT(B,FWTB,c,n);for(int i=0;i<n;i++)FWTC[i]=FWTA[i]*FWTB[i]%MOD;FWT(FWTC,C,cn,n);
}
int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n;n=1<<n;for(int i=0;i<n;i++)cin>>A[i];for(int i=0;i<n;i++)cin>>B[i];solve(cOR,cnOR);for(int i=0;i<n;i++)cout<<C[i]<<' ';cout<<'\n';solve(cAND,cnAND);for(int i=0;i<n;i++)cout<<C[i]<<' ';cout<<'\n';solve(cXOR,cnXOR);for(int i=0;i<n;i++)cout<<C[i]<<' ';return 0;
}

Q&A

  1. 性质 2 成立的必要性?

它出现的必要性是我们需要保证 \(c(i_t,j_t)c(i_t,k_t)=c(i_t,j_t\oplus k_t)\iff c(i,j)c(i,k)=c(i,j\oplus k)\)

  1. 异或卷积是否依赖模数?

是,否则将使用 double。同时与或卷积可以不带取模,但是需要数据足够小。

http://www.hskmm.com/?act=detail&tid=36001

相关文章:

  • 嵌合抗体:破解二抗选择难题,赋能多重分子检测的核心工具
  • 原来用聊天记录就可以创造数字分身!WeClone项目在Lab4AI平台上的复现
  • 自监督提示优化SPO
  • Java中的注释
  • 实测!不同场景下,哪款 AI IDE 能真正帮你少加班?
  • CSP-S模拟36 2025.10.21
  • 2025 年 AI 编程工具生成效果全景比拼:从技术实力到综合评分
  • 打造AI IDE标杆产品,腾讯CodeBuddy深度全方位解析
  • C语言项目开发常用目录结构 - Invinc
  • 2025年不锈钢水箱厂家权威推荐榜:方形/圆形/消防/生活/保温/承压/装配式/焊接水箱及水塔水罐全解析
  • day03-Coze记忆-对话体验
  • 2025年流量计厂家权威推荐榜单:电磁流量计、超声波流量计、涡街流量计、质量流量计专业制造商深度解析
  • RNDIS让Air8000的USB上网更智能、更快速!
  • 如果k8s有三个calico节点A,B,C 使用bgp模式的话是如何进行BGP对等会话的
  • 10.21
  • home-assistant-Onboarding Home Assistant(入职家庭助理)
  • Day1标签语法
  • home-assistant-Concepts and terminology概念和术语
  • 2025年印染水洗机厂家权威推荐榜:高效水洗设备与环保节能技术深度解析,专业水洗机厂家精选
  • 高级语言程序设计第二次作业
  • 有关K8s calico IPIP模式的一些疑惑和思考
  • 1.正手握拍
  • 2025年角接触轴承厂家推荐排行榜,高精度/高承载/高精密/机床主轴/汽车/定制/可替代进口/高转速/高刚性角接触球轴承公司推荐
  • 7-Zip最新版 7-Zip25.01
  • 2025年精密球轴承厂家权威推荐榜:半导体设备轴承,机床主轴轴承,真空泵轴承,国产高端精密球轴承,晶圆搬运机械手臂不锈钢轴承
  • 结对项目-实现四则运算题目的命令行程序
  • 从易路iBuilder平台看企业人力资源的AI转型升级与变革
  • 从零开始,搭建自己的AI平台写小说
  • UMDF驱动开发入门:创建虚拟设备,从安装到I/O交互全解析
  • 2025年AI优化公司电话推荐:十家可验证服务商沟通备忘