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

To_Heart—总结——FWT(快速沃尔什变换)

目录

    • 闲话
    • 拿来求什么
      • 异或

闲话

这个比FFT简单了很多呢,,大概是我可以学懂的水平!

好像是叫 快速沃尔什变换 ?

拿来求什么

以 FFT 来类比。我们 FFT 可以在 O(nlogn)\mathrm{O(nlogn)}O(nlogn) 的复杂度下实现求解:

Ck=∑i+j=kAi×BjC_k=\sum_{i + j=k} A_i \times B_j Ck=i+j=kAi×Bj

那么 FWT 的作用就是再 O(nlogn)\mathrm{O(nlogn)}O(nlogn) 的时间复杂度下面求解:

Ck=∑i⊕j=kAi×BjC_k=\sum_{i \oplus j=k} A_i \times B_j Ck=ij=kAi×Bj

其中的 ⊕\oplus 是位运算异或的意思。 FWT 应该是支持 ⊕\oplus∣|&\&& 三种位运算的。

然后就准备开始讲这三种位运算分别对应的算法。

我们定义 FWT(A)i=∑j∣i=iAj\mathrm{FWT(A)_i}=\sum_{j|i=i} A_jFWT(A)i=ji=iAj。根据定义可以知道 FWT(A)\mathrm{FWT(A)}FWT(A) 是一个由 AAA 构造出来的多项式。先不管如何构造,我们考虑 FWT(A)\mathrm{FWT(A)}FWT(A) 有什么用。我们发现:

FWT(A)×FWT(B)\mathrm{FWT(A)} \times \mathrm{FWT(B)}FWT(A)×FWT(B)
=∑i=0FWT(A)i×FWT(B)i=\sum_{i=0} \mathrm{FWT(A)_i} \times \mathrm{FWT(B)_i}=i=0FWT(A)i×FWT(B)i
=∑i=0(∑j∣i=iAj×∑k∣i=iBk)=\sum_{i=0} ( \sum_{j|i=i} A_j \times \sum_{k|i=i} B_ k)=i=0(ji=iAj×ki=iBk)

=∑i=0∑(j∣k)∣i=iAj×Bk=\sum_{i=0} \sum_{(j|k)|i=i} A_j \times B_ k=i=0(jk)i=iAj×Bk

=∑i=0∑(j∣k)∣i=iCi=\sum_{i=0} \sum_{(j|k)|i=i} C_i=i=0(jk)i=iCi
=FWT(C)=\mathrm{FWT(C)}=FWT(C)

所以我们发现可以在 O(n)\mathrm{O(n)}O(n) 的时间复杂度下实现由 A,BA,BA,BCCC 的转换。所以现在的问题就是如何在 O(nlogn)\mathrm{O(nlogn)}O(nlogn) 及以下的时间复杂度中求出 FWT(A)\mathrm{FWT(A)}FWT(A)

考虑分治。假设 AAA2n2^n2n 项,那么 A0A_0A0 表示 AAA 的前 2n−12^{n-1}2n1A1A_1A1 表示 AAA 的后 2n−12^{n-1}2n1 项。

然后就可以得到一个崭新的转移:

FWT(A)={FWT(A0),FWT(A1)+FWT(A0)n≥1An=0\mathrm{FWT(A)}=\begin{cases}{\mathrm{FWT(A_0)},\mathrm{FWT(A_1)}+\mathrm{FWT(A_0)}}&{n\geq 1}\\{A}&{n=0}\end{cases}FWT(A)={FWT(A0),FWT(A1)+FWT(A0)An1n=0

这个 ,可以理解成把两个多项式拼起来。

如何理解这个式子呢?n=0n=0n=0 的边界很好理解,问题在上面一个式子。

你考虑 A0A_0A0A1A_1A1 的区别:在 AAA 中且在 A0A_0A0中 的项的下标的最高位一定是 0 ;在 AAA 中且在 A1A_1A1中 的项的下标的最高位一定是 1 ;

所以你发现从 A0A_0A0A1A_1A1AAA 中只有可能是 A0A_0A0 所在的项给 A1A_1A1 所在的项做贡献。

所以就可以做到 O(nlogn)\mathrm{O(nlogn)}O(nlogn) 的时间复杂度实现从 AAAFWT(A)\mathrm{FWT(A)}FWT(A) 的转换了。

但是还需要实现从 FWT(A)\mathrm{FWT(A)}FWT(A)AAA 的转换,也就是逆转换。

你感性理解一下,大概就是 A_0 会影响的两个位置,其中一个只有 A_0 ,另一个是 A_0+A_1 ,所以设 x_0 为改变的第一个位置, x_1 为改变的第二个位置,那么有 x=A0x=A_0x=A0y=A0+A1y=A_0+A_1y=A0+A1 。现在是知道了 x 和 y ,所以 A0=xA_0=xA0=xA1=y−A0=y−xA_1=y-A_0=y-xA1=yA0=yx

那么关于 或运算 的 FWT 就可以实现了:

void OR(ll *a,int n,int op){ //op=1是顺转换,op=-1是逆转换for(int mid=1;mid<n;mid<<=1) for(int len=mid<<1,j=0;j<n;j+=len) for(int i=j;i<j+mid;i++)a[i+mid]=(a[i+mid]+a[i]*op+Mod)%Mod;
}

这个和 或 差不多,但是注意到只有 A1A_1A1 可以向 A0A_0A0 贡献,所以反过来。

void AND(ll *a,int n,int op){for(int mid=1;mid<n;mid<<=1) for(int len=mid<<1,j=0;j<n;j+=len) for(int i=j;i<j+mid;i++)a[i]=(a[i]+a[i+mid]*op+Mod)%Mod;
}

异或

这个可能要麻烦一点。

异或本身并不好统一的下标之间的关联。什么意思呢?对于 或 ,我们可以很清楚的发现对于所有情况都是 A0A_0A0A1A_1A1 做贡献;对于 与,所有情况都是 A1A_1A1A0A_0A0 做贡献。但是异或并不满足这样的性质。所以需要考虑一种构造 FWT\mathrm{FWT}FWT 的方式使得 A0A_0A0A1A_1A1 的做贡献方式是一成不变的。

那么考虑怎么找到构造方式。

相关文章:

To_Heart—总结——FWT(快速沃尔什变换)

目录闲话拿来求什么或与异或闲话 这个比FFT简单了很多呢&#xff0c;&#xff0c;大概是我可以学懂的水平&#xff01; 好像是叫 快速沃尔什变换 &#xff1f; 拿来求什么 以 FFT 来类比。我们 FFT 可以在 O(nlogn)\mathrm{O(nlogn)}O(nlogn) 的复杂度下实现求解&#xff1…...

Google巨大漏洞让Win10、11翻车,小姐姐马赛克白打了

早年间电脑截图这项技能未被大多数人掌握时&#xff0c;许多人应该都使用过手机拍屏幕这个原始的方式。 但由于较低的画面质量极其影响其他用户的观感&#xff0c;常常受到大家的调侃。 但到了 Win10、11 &#xff0c;预装的截图工具让门槛大幅降低。 WinShiftS 就能快速打开…...

腾讯云服务器部署内网穿透(让其他人在不同ip可以访问我们localhost端口的主机项目)(nps开源项目)

首先打开shell连接我们的云服务器 然后我们再opt目录下面创建一个文件夹用来存放我们的压缩包和文件 mkdir /opt/nps 这个是它官方的安装图解.所以我们按照这个docker安装过程来: 然后我们用docker安装镜像.这样的话比较简单一点 docker pull ffdfgdfg/nps 然后我们查看docker…...

IDS、恶意软件、免杀技术、反病毒技术、APT、对称加密、非对称加密以及SSL的工作过程的技术介绍

IDS的简单介绍IDS是&#xff1a;入侵检测系统&#xff08;intrusion detection system&#xff0c;简称“IDS”&#xff09;是一种对网络传输进行即时监视&#xff0c;在发现可疑传输时发出警报或者采取主动反应措施的网络安全设备。它与其他网络安全设备的不同之处便在于&…...

怎么把pdf转换成高清图片

怎么把pdf转换成高清图片&#xff1f;可以使用以下两种方法&#xff1a; 方法一&#xff1a;使用Adobe Acrobat Pro DC 1、打开需要转换的PDF文件&#xff0c;点击“文件”菜单中的“导出为”&#xff0c;在弹出的菜单中选择“图像”&#xff0c;然后选择“JPEG”。 2、在“…...

MATLAB 系统辨识 + PID 自动调参

系统辨识 PID 自动调参 文章目录系统辨识 PID 自动调参1. 导入数据1.1 从 Excel 中导入数据2. 系统辨识3. PID 自动调参1. 导入数据 1.1 从 Excel 中导入数据 如果不是从Excel中导入可以跳过该步骤 导入函数&#xff1a; [num,txt,raw]xlsread(xxx\xxx.xlsx);num返回的是…...

【vue3】组合式API之setup()介绍与reactive()函数的使用·上

>&#x1f609;博主&#xff1a;初映CY的前说(前端领域) ,&#x1f4d2;本文核心&#xff1a;setup()概念、 reactive()的使用 【前言】vue3作为vue2的升级版&#xff0c;有着很多的新特性&#xff0c;其中就包括了组合式API&#xff0c;也就是是 Composition API。学习组合…...

爬虫Day3 csv和bs4

爬虫Day3 csv和bs4 一、CSV的读和写 1. 什么是csv文件 csv文件叫做&#xff1a;逗号分隔值文件&#xff0c;像Excel文件一样以行列的形式保存数据&#xff0c;保存数据的时候同一行的多列数据用逗号隔开。 2. csv文件的读写操作 1) csv文件读操作 from csv import reader…...

nnAudio的简单介绍

官方实现 https://github.com/KinWaiCheuk/nnAudio&#xff1b; 论文实现&#xff1a; nnAudio: An on-the-Fly GPU Audio to Spectrogram Conversion Toolbox Using 1D Convolutional Neural Networks&#xff1b; 以下先对文章解读&#xff1a; abstract 在本文中&#x…...

【id:134】【20分】B. 求最大值最小值(引用)

题目描述 编写函数void find(int *num,int n,int &minIndex,int &maxIndex)&#xff0c;求数组num(元素为num[0]&#xff0c;num[1]&#xff0c;...&#xff0c;num[n-1]&#xff09;中取最小值、最大值的元素下标minIndex,maxIndex&#xff08;若有相同最值&#xff0…...

Java 面向对象

一、Java 8 增强的包装类 Java是面向对象的编程语言&#xff0c;但它也包含了8种基本数据类型&#xff0c;这8种基本数据类型不支持面向对象的编程机制&#xff0c;基本数据类型的数据也不具备对象的特性。&#xff08;没有成员变量、方法可以被调用&#xff09;。Java之所以提…...

五、传输层

&#xff08;一&#xff09;TCP传输控制协议 可靠的、面向连接的字节流服务&#xff0c;全双工&#xff0c;有端口寻址功能 1、TCP的三种机制 1.使用序号对分段的数据进行标记&#xff0c;便于调整数据包 2.TCP使用确认、校验和和定时器系统提供可靠性 3.TCP使用可变大小的…...

Thinkphp 6.0一对一关联查询

本节课我们来了解关联模型中&#xff0c;一对一关联查询的使用方法。 一&#xff0e;hasOne 模式 1. hasOne 模式&#xff0c;适合主表关联附表&#xff0c;具体设置方式如下: hasOne(关联模型,[外键,主键]); return $this->hasOne(Profile::class,user_id, id); 关联模型&…...

基于51单片机的自动打铃打鸣作息报时系统AT89C51数码管三极管时钟电路

wx供重浩&#xff1a;创享日记 对话框发送&#xff1a;单片机打铃 获取完整无水印论文报告说明&#xff08;含源码程序、电路原理图和仿真图&#xff09; 本次设计中的LED数码管电子时钟电路采用24小时制记时方式,本次设计采用AT89C51单片机的扩展芯片和6个PNP三极管做驱动&…...

算法详解-双指针算法的魅力-一种简单而高效的编程思想

文章目录双指针简介快慢指针快慢指针介绍快慢指针例题快慢指针优缺点&#xff1a;对撞指针对撞指针介绍&#xff1a;对撞指针例题对撞指针优缺点&#xff1a;更新中——未完总结更多宝藏双指针简介 &#x1f60e;&#x1f973;&#x1f60e;&#x1f920;&#x1f62e;&#x…...

网页审查元素

在讲解爬虫内容之前&#xff0c;我们需要先学习一项写爬虫的必备技能&#xff1a;审查元素&#xff08;如果已掌握&#xff0c;可跳过此部分内容&#xff09;。1、审查元素在浏览器的地址栏输入URL地址&#xff0c;在网页处右键单击&#xff0c;找到检查。(不同浏览器的叫法不同…...

gpt2 adapter finetune

1. 安装依赖&#xff1a; pip install -U adapter-transformers pip install datasets 2.训练代码&#xff1a; from datasets import load_dataset from transformers import AutoModelForCausalLM from transformers import GPT2Tokenizer from transformers import Adap…...

Day14_文件操作

一、数据存储 1.1 计算机数据存储 计算机内存分为运行内存和硬盘两种&#xff1a;保存在运行内存中的数据在程序运行结束后会自动释放&#xff0c;保存在硬盘中的数据会一直存在(除非手动删除或者硬盘损坏) 1&#xff09;打开文件 open(文件路径, 文件打开方式‘r’, encod…...

leetcode 轮转数组 189

题目 给定一个整数数组 nums&#xff0c;将数组中的元素向右轮转 k 个位置&#xff0c;其中 k 是非负数。 示例 1: 输入: nums [1,2,3,4,5,6,7], k 3 输出: [5,6,7,1,2,3,4] 解释: 向右轮转 1 步: [7,1,2,3,4,5,6] 向右轮转 2 步: [6,7,1,2,3,4,5] 向右轮转 3 步: [5,6,7,1,2…...

Leetcode.1849 将字符串拆分为递减的连续值

题目链接 Leetcode.1849 将字符串拆分为递减的连续值 Rating &#xff1a; 1747 题目描述 给你一个仅由数字组成的字符串 s。 请你判断能否将 s拆分成 两个或者多个 非空子字符串 &#xff0c;使子字符串的 数值 按 降序 排列&#xff0c;且每两个 相邻子字符串 的数值之 差 …...

Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)

概述 在 Swift 开发语言中&#xff0c;各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过&#xff0c;在涉及到多个子类派生于基类进行多态模拟的场景下&#xff0c;…...

AtCoder 第409​场初级竞赛 A~E题解

A Conflict 【题目链接】 原题链接&#xff1a;A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串&#xff0c;只有在同时为 o 时输出 Yes 并结束程序&#xff0c;否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...

Leetcode 3577. Count the Number of Computer Unlocking Permutations

Leetcode 3577. Count the Number of Computer Unlocking Permutations 1. 解题思路2. 代码实现 题目链接&#xff1a;3577. Count the Number of Computer Unlocking Permutations 1. 解题思路 这一题其实就是一个脑筋急转弯&#xff0c;要想要能够将所有的电脑解锁&#x…...

《通信之道——从微积分到 5G》读书总结

第1章 绪 论 1.1 这是一本什么样的书 通信技术&#xff0c;说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号&#xff08;调制&#xff09; 把信息从信号中抽取出来&am…...

苍穹外卖--缓存菜品

1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得&#xff0c;如果用户端访问量比较大&#xff0c;数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据&#xff0c;减少数据库查询操作。 缓存逻辑分析&#xff1a; ①每个分类下的菜品保持一份缓存数据…...

BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践

6月5日&#xff0c;2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席&#xff0c;并作《智能体在安全领域的应用实践》主题演讲&#xff0c;分享了在智能体在安全领域的突破性实践。他指出&#xff0c;百度通过将安全能力…...

【开发技术】.Net使用FFmpeg视频特定帧上绘制内容

目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法&#xff0c;当前调用一个医疗行业的AI识别算法后返回…...

laravel8+vue3.0+element-plus搭建方法

创建 laravel8 项目 composer create-project --prefer-dist laravel/laravel laravel8 8.* 安装 laravel/ui composer require laravel/ui 修改 package.json 文件 "devDependencies": {"vue/compiler-sfc": "^3.0.7","axios": …...

Xen Server服务器释放磁盘空间

disk.sh #!/bin/bashcd /run/sr-mount/e54f0646-ae11-0457-b64f-eba4673b824c # 全部虚拟机物理磁盘文件存储 a$(ls -l | awk {print $NF} | cut -d. -f1) # 使用中的虚拟机物理磁盘文件 b$(xe vm-disk-list --multiple | grep uuid | awk {print $NF})printf "%s\n"…...

回溯算法学习

一、电话号码的字母组合 import java.util.ArrayList; import java.util.List;import javax.management.loading.PrivateClassLoader;public class letterCombinations {private static final String[] KEYPAD {"", //0"", //1"abc", //2"…...