首页 > 其他分享 >FWT 的另一种理解

FWT 的另一种理解

时间:2023-11-16 11:12:28浏览次数:30  
标签:xor mathscr sum 一种 理解 text FWT oplus 复杂度

思路

若要 \(\oplus\) 卷积 \(a\) 和 \(b\)(此处 \(\oplus\) 可以是任意运算),我们希望存在一个线性变换 \(\mathscr F\),满足:

\[c_k = \sum_{i\oplus j = k} a_ib_j \Longleftrightarrow \mathscr F(a) \cdot \mathscr F(b) = \mathscr F(c) \]

若求 \(\mathscr F(x)\) 和 \(\mathscr F^{-1}(x)\) 的时间复杂度为 \(\mathcal O(T)\),则卷积可以以 \(\mathcal O(n + T)\) 的时间复杂度完成。

设 \(\mathscr F\) 的系数矩阵为 \(F\),分析一下这个式子:

\[\begin{aligned} \mathscr F(a) \cdot \mathscr F(b) = \mathscr F(c) &\Longleftrightarrow \forall x, \mathscr F(a)_x \times \mathscr F(b)_x = \mathscr F(c)_x \\ &\Longleftrightarrow \forall x, (\sum_{i=0}^{n-1} F(i, x)a_i) (\sum_{i=0}^{n-1} F(i, x)b_i) = \sum_{i=0}^{n-1} F(i, x)c_i\\ &\Longleftrightarrow \forall x, \sum_{i=0}^{n-1}\sum_{j=0}^{n-1}F(i, x)F(j, x)a_ib_j = \sum_{i=0}^{n - 1}F(i, x)c_i\\ &\Longleftrightarrow \forall x, \sum_{i=0}^{n-1}\sum_{j=0}^{n-1}F(i, x)F(j, x)a_ib_j = \sum_{i=0}^{n - 1}\sum_{j=0}^{n-1} F(i\oplus j, x)a_ib_j\\ \end{aligned} \]

所以,若上式对任意 \(a, b\) 及 \(c = a * b\) 都成立,则其等价于 \(F(i, x)F(j, x) = F(i \oplus j, x)\)。

\(\oplus = \&\)

令 \(F(i, j) = [i \text{ or } j = i]\),显然有 \(F(i, x) F(j, x) = F(i\& j, x)\)。

此时 \(\mathscr F(x)\) 即为 \(x\) 的高维后缀和,从而 \(\mathscr F^{-1}(x)\) 就是高维后缀差分。

时间复杂度 \(\mathcal O(n 2^n)\)。

\(\oplus = \text{or}\)

令 \(F(i, j) = [i \text{ or }j = j]\),显然有 \(F(i, x) F(j, x) = F(i\text{ or }j,x)\)。

此时 \(\mathscr F(x)\) 即为 \(x\) 的高维前缀和,从而 \(\mathscr F^{-1}(x)\) 就是高维前缀差分。

时间复杂度 \(\mathcal O(n 2^n)\)。

\(\oplus = \text{xor}\)

下面记 \(|x| = \text{popcount}(x)\)。

注意到有 \(|i| + |j| \equiv |i \text{ xor } j|\pmod 2\),从而有 \((-1)^{|i|}(-1)^{|j|} = (-1)^{|i \text{ xor } j|}\)。

又因为 \((a \text{ xor } b) \& c = (a \& c)\text{ xor } (b\& c)\),于是令 \(F(i, j) = (-1)^{|i \& j|}\),显然 \(F(i, x)F(j, x) = F(i \text{ xor } j, x)\) 成立。

现在的问题在于如何快速求出 \(\mathscr F(x)\) 和 \(\mathscr F^{-1}(x)\)。

考虑分治求 \(x' = \mathscr F(x)\),若要求 \(x'_0 \sim x'_{2^n - 1}\),则对于 \(0 \leq k < 2^{n - 1}\),有:

\[x'_k = \sum_{i=0}^{2^n - 1} x_i (-1)^{|i \& k|} = \sum_{i=0}^{2^{n -1 } - 1} x_i(-1)^{|i\&k|} + \sum_{i=0}^{2^{n -1 } - 1} x_{i + 2^{n -1 }}(-1)^{|i\&k|} = x0'_k + x1'_k \]

\[x'_{k + 2^{n - 1}} = \sum_{i=0}^{2^n - 1} x_i (-1)^{|i \& (k + 2^{n - 1})|} = \sum_{i=0}^{2^{n -1 } - 1} x_i(-1)^{|i\&k|} + \sum_{i=0}^{2^{n -1 } - 1} x_{i + 2^{n -1 }}(-1)^{|i\&k|+1} = x0'_k - x1'_k \]

其中 \(x0\) 表示分治求出的前一半的答案,\(x1\) 表示分治求出的后一半的答案。

类似 FFT,可以把这个过程变成非递归的,减小常数还好写。

至于求 \(\mathscr F^{-1}(x)\),幸运地,我们有 \(F^{-1} = \dfrac 1n F\),因此求出 \(\mathscr F(x)\) 再除以 \(2^n\) 就好了。

时间复杂度 \(\mathcal O(n 2^n)\)。

标签:xor,mathscr,sum,一种,理解,text,FWT,oplus,复杂度
From: https://www.cnblogs.com/reliauk/p/fwt.html

相关文章

  • 理解技术和业务的共同目标
    昨天更新了一篇关于稳定性保障的文章,我在文末写了这样一句:遇上降本增效,或者换一个重业务轻技术的领导上台,技术团队就是第一个被砍的。毕竟在国内这种环境,哪儿来的技术导向和工程师文化,不都是营销为王和短期利润为重。有同学提了一个疑问,技术和业务,到底哪个重要?毕竟绝大多数公......
  • 简单例子理解 Qt 中 QObject: Cannot create children for a parent that is in a dif
    c++guiprogrammingwithqt中关于QThread的用法的限制下面这句话的翻译不清QObjectisreentrant,buttherearethreeconstraintstokeepinmind:ChildQObjectsmustbecreatedintheirparent'sthread.Inparticular,thismeansthattheobjectscreatedina......
  • 算法~base64算法理解
    base64Base64是一种用于将二进制数据编码成ASCII字符的编码方式。它主要用于在文字环境中传输或存储二进制数据,如在电子邮件、XML文件、URL参数等。Base64编码不是一种加密算法,而是一种编码方式,其主要作用是将二进制数据转换为文本数据,以便更容易在文本协议中处理。Base64......
  • DyHGCN:一种学习用户动态偏好的动态异构图卷积网络,用于信息扩散预测
    DyHGCN:ADynamicHeterogeneousGraphConvolutionalNetworktoLearnUsers’DynamicPreferencesforInformationDiffusionPredictionECML-PKDD2020欧洲机器学习与数据挖掘顶级会议Abstract​ 信息扩散预测是了解信息传播过程的一项基本任务。它在错误信息传播预测......
  • 2023全球智能汽车AI挑战赛——赛道二:智能驾驶汽车虚拟仿真视频数据理解赛道
    赛题:智能驾驶汽车虚拟仿真视频数据理解赛道任务:输入:元宇宙仿真平台生成的前视摄像头虚拟视频数据(8-10秒左右);输出:对视频中的信息进行综合理解,以指定的json文件格式,按照数据说明中的关键词(key)填充描述型的文本信息(value,中文/英文均可以)初赛提交格式:{"author":"abc","time":"YY......
  • 理解与使用Javascript中的回调函数
     js里的解释:Acallbackisafunctionthatispassedasanargumenttoanotherfunctionandisexecutedafteritsparentfunctionhascompleted.    从字面上理解下来就是,回调就是一个函数的调用过程。假如函数a有一个参数,这个参数是个函数b,当函数a执行完......
  • 对前端工程师这个职位的理解
    a. 前端是最贴近用户的程序员,前端的能力就是能让产品从90分进化到100分,甚至更好b. 参与项目,快速高质量完成实现效果图,精确到1px;c.与团队成员,UI设计,产品经理的沟通;d. 做好的页面结构,页面重构和用户体验;e. 处理hack,兼容、写出优美的代码格式;f. 针对服务器的优化、拥抱最新前......
  • 相机靶面和图像传感器的理解与应用
    一、相机靶面(SensorSize)的基本概念相机靶面,即相机内部的图像传感器尺寸,是衡量相机性能的重要指标。靶面尺寸越大,通常意味着相机能够捕获更多的光线和细节,具有更好的低光表现和更浅的景深效果。靶面尺寸的大小直接影响着相机的图像质量和使用场景。二、特定靶面尺寸的理解:以2/3......
  • 11月智能汽车AI挑战赛——智能驾驶汽车虚拟仿真视频数据理解
    赛题理解:赛题任务:输入:元宇宙仿真平台生成的前视摄像头虚拟视频数据(8-10秒左右);输出:对视频中的信息进行综合理解,以指定的json文件格式,按照数据说明中的关键词(key)填充描述型的文本信息(value,中文/英文均可以);赛题只提供了测试集,所以我们要通过预训练模型预测,或者直接使用外部数据训练后......
  • 深入理解JMeter中的JSON Extractor
    ApacheJMeter是一款出色的开源性能和功能测试工具,这款工具提供了丰富的功能和强大的扩展性,可以应对各种复杂的测试需求。当我们在进行接口测试时,经常会遇到需要从接口响应中提取信息并在后续请求中使用的情况。这时候,JMeter中的JSONExtractor就派上了用场。JSONExtractor是JMe......