imtoken2.0官网版|fwt
安全访问中心 - 洛谷
安全访问中心 - 洛谷
即将离开洛谷
你访问的网站可能包含未知的安全风险，如需继续访问，请复制链接访问或点击按钮确认，并注意保护账号和隐私信息。
https://www.luogu.com/article/y0unggsj
继续访问
FWT(快速沃尔什变换)零基础详解qaq（ACM/OI） - 知乎
FWT(快速沃尔什变换)零基础详解qaq（ACM/OI） - 知乎首发于桃酱的算法笔记切换模式写文章登录/注册FWT(快速沃尔什变换)零基础详解qaq（ACM/OI）月下桃子树君がそれでいいなら僕だってそれで構わないさ。1.前言（废话）记得一年半之前做SRM518 Nim的时候还不知道FWT，当时自己用分治完美的水过去了。然后昨天的牛客有一道题，是说nim博弈中有n堆石子，请问最多取出多少堆石子可以让先手必败。当时竟然没思路QAQ？？？想了想使劲往字典树靠边靠不上去QAQ，然后就没想出来！！！想当年自己手推FWT或运算，真的感叹岁月是把杀猪刀！于是怒写这篇博客QAQ把这个算法总结一下QAQ（其实我觉得这变换竟然也有名字真的很神奇QAQ）2.FWT简介沃尔什转换（Walsh Transform）是在频谱分析上作为离散傅立叶变换的替代方案的一种方法。 ——wiki百科其实这个变换在信号处理中应用很广泛，fft是double类型的，但是walsh把信号在不同震荡频率方波下拆解，因此所有的系数都是绝对值大小相同的整数，这使得不需要作浮点数的乘法运算，提高了运算速度。所以，FWT和FFT的核心思想应该是相同的。都是对数组的变换。我们设数组A经过快速沃尔什变换之后记作那么FWT核心思想就是：我们需要一个新序列C，由序列A和序列B经过某运算规则得到，即。我们先正向得到,然后根据（*为点乘），在O(n)求出,然后再逆向运算得到原序列C。 时间复杂度为在算法竞赛中，FWT是用于解决对下标进行位运算卷积问题的方法。公式：其中是任意二元位运算中的某一种，就是普通乘法。3.FWT的运算3.1FWT之与（&）运算和或（|）运算与运算和或运算的本质是差不多的，所以这里讲一下或运算，与运算也是可以自己根据公式yy出来的。3.1.1或运算如果有，那么i的二进制位为1的位置和j的二进制位为1的位置肯定是k的二进制位为1的位置的子集。现在要得到，我们就要构造这个fwt的规则。我们按照定义，显然可以构造,表示j满足二进制中1为i的子集。那么显然会有即那么我们接下来看怎么求。首先肯定不能枚举了，复杂度为n^2。既然不能整体枚举，我们就考虑分治。我们把整个区间二分，其实二分区间之后，下标写成二进制形式是有规律可循的。我们令表示A的前一半，表示区间的后一半，那么A0就是A下标最大值的最高位为0，他的子集就是他本身的子集（因为最高位为0了），但是A1的最高位是1，他满足条件的子集不仅仅是他本身，还包最高位为0的子集，即其中merge表示向字符串拼接一样把他们拼起来。+就是普通加法，表示对应二进制位相加。这样我们就通过二分能在logn完成拼接，每次拼接的时候要完成一次运算，也就是说在的时间复杂度得到了接下来就是反演了，其实反演是很简单的，既然知道了A0的本身的子集是他自己(A0 = FAT[A0])，A1的子集是 FAT[A0] + FAT[A1]（A1' = A0' + A1'）,那就很简单的得出反演的递推式了3.1.2与运算与运算类比或运算可以得到类似结论3.2异或运算最常考的异或运算。异或的卷积是基于如下原理：若我们令i&j中1数量的奇偶性为i与j的奇偶性，那么i与k的奇偶性异或j和k的奇偶性等于i^j和k的奇偶性。对于的运算其实也很好得到。公式如下(C1表示i&j奇偶性为0，C2表示i&j的奇偶性为1)结论3.3 同或运算类比异或运算给出公式：(C1表示i|j奇偶性为0，C2表示i|j的奇偶性为1)QAQ编辑于 2018-08-12 19:35算法竞赛OI（信息学奥林匹克）ACM赞同 32428 条评论分享喜欢收藏申请转载文章被以下专栏收录桃酱的算法笔记ACMer的自我成长笔记。多为算法学习
快速沃尔什变换 - OI Wiki
什变换 - OI Wiki 跳转至 OI Wiki 快速沃尔什变换 正在初始化搜索引擎 OI-wiki/OI-wiki 简介 比赛相关 工具软件 语言基础 算法基础 搜索 动态规划 字符串 数学 数据结构 图论 计算几何 杂项 专题 关于 Hulu OI Wiki OI-wiki/OI-wiki 简介 简介 Getting Started 关于本项目 如何参与 OI Wiki 不是什么 格式手册 数学符号表 F.A.Q. 用 Docker 部署 OI Wiki 镜像站列表 致谢 比赛相关 比赛相关 比赛相关简介 赛事 赛事 OI 赛事与赛制 ICPC/CCPC 赛事与赛制 题型 题型 题型概述 交互题 学习路线 学习资源 技巧 技巧 读入、输出优化 分段打表 常见错误 常见技巧 出题 工具软件 工具软件 工具软件简介 代码编辑工具 代码编辑工具 Vim Emacs VS Code Atom Eclipse Notepad++ Kate Dev-C++ CLion Geany Xcode GUIDE Sublime Text CP Editor 评测工具 评测工具 评测工具简介 Arbiter Cena CCR Plus Lemon 命令行 编译器 WSL (Windows 10) Special Judge Testlib Testlib Testlib 简介 通用 Generator Validator Interactor Checker Polygon OJ 工具 LaTeX 入门 Git 语言基础 语言基础 语言基础简介 C++ 基础 C++ 基础 Hello, World! C++ 语法基础 变量 运算 流程控制语句 流程控制语句 分支 循环 高级数据类型 高级数据类型 数组 结构体 联合体 指针 函数 文件操作 C++ 标准库 C++ 标准库 C++ 标准库简介 STL 容器 STL 容器 STL 容器简介 迭代器 序列式容器 关联式容器 无序关联式容器 容器适配器 STL 算法 bitset string pair C++ 进阶 C++ 进阶 类 命名空间 值类别 重载运算符 引用 常值 新版 C++ 特性 Lambda 表达式 pb_ds pb_ds pb_ds 简介 堆 平衡树 编译优化 C++ 与其他常用语言的区别 Pascal 转 C++ 急救 Python 速成 Java 速成 Java 进阶 算法基础 算法基础 算法基础简介 复杂度 枚举 模拟 递归 & 分治 贪心 排序 排序 排序简介 选择排序 冒泡排序 插入排序 计数排序 基数排序 快速排序 归并排序 堆排序 桶排序 希尔排序 锦标赛排序 tim排序 排序相关 STL 排序应用 前缀和 & 差分 二分 倍增 构造 搜索 搜索 搜索部分简介 DFS（搜索） BFS（搜索） 双向搜索 启发式搜索 A* 迭代加深搜索 IDA* 回溯法 Dancing Links Alpha-Beta 剪枝 优化 动态规划 动态规划 动态规划部分简介 动态规划基础 记忆化搜索 背包 DP 区间 DP DAG 上的 DP 树形 DP 状压 DP 数位 DP 插头 DP 计数 DP 动态 DP 概率 DP DP 优化 DP 优化 单调队列/单调栈优化 斜率优化 四边形不等式优化 状态设计优化 其它 DP 方法 字符串 字符串 字符串部分简介 字符串基础 标准库 字符串匹配 字符串哈希 字典树 (Trie) 前缀函数与 KMP 算法 Boyer–Moore 算法 Z 函数（扩展 KMP） 自动机 AC 自动机 后缀数组 (SA) 后缀数组 (SA) 后缀数组简介 最优原地后缀排序算法 后缀自动机 (SAM) 后缀平衡树 广义后缀自动机 后缀树 Manacher 回文树 序列自动机 最小表示法 Lyndon 分解 Main–Lorentz 算法 数学 数学 数学部分简介 符号 进位制 位运算 二进制集合操作 平衡三进制 高精度计算 快速幂 置换和排列 弧度制与坐标系 复数 数论 数论 数论基础 素数 最大公约数 数论分块 欧拉函数 筛法 Meissel–Lehmer 算法 分解质因数 裴蜀定理 类欧几里德算法 欧拉定理 & 费马小定理 乘法逆元 线性同余方程 中国剩余定理 升幂引理 威尔逊定理 卢卡斯定理 同余方程 二次剩余 原根 离散对数 剩余 莫比乌斯反演 杜教筛 Powerful Number 筛 Min_25 筛 洲阁筛 连分数 Stern–Brocot 树与 Farey 序列 二次域 循环连分数 Pell 方程 多项式与生成函数 多项式与生成函数 多项式与生成函数简介 代数基本定理 快速傅里叶变换 快速数论变换 快速沃尔什变换 快速沃尔什变换 目录 简介 FWT 的运算 FWT 之与（&）运算和或（|）运算 或运算 与运算 异或运算 同或运算 例题 Chirp Z 变换 多项式牛顿迭代 多项式多点求值|快速插值 多项式初等函数 常系数齐次线性递推 多项式平移|连续点值平移 符号化方法 普通生成函数 指数生成函数 狄利克雷生成函数 组合数学 组合数学 排列组合 抽屉原理 容斥原理 康托展开 斐波那契数列 错位排列 卡特兰数 斯特林数 贝尔数 伯努利数 Entringer Number Eulerian Number 分拆数 范德蒙德卷积 图论计数 线性代数 线性代数 线性代数简介 向量 内积和外积 矩阵 初等变换 行列式 线性空间 线性基 线性映射 特征多项式 对角化 Jordan标准型 线性规划 线性规划 线性规划简介 单纯形算法 群论 群论 群论简介 置换群 概率论 概率论 基本概念 条件概率与独立性 随机变量 随机变量的数字特征 概率不等式 博弈论 博弈论 博弈论简介 公平组合游戏 非公平组合游戏 反常游戏 数值算法 数值算法 插值 数值积分 高斯消元 牛顿迭代法 傅里叶-莫茨金消元法 序理论 杨氏矩阵 Schreier–Sims 算法 Berlekamp–Massey 算法 数据结构 数据结构 数据结构部分简介 栈 队列 链表 哈希表 并查集 并查集 并查集 并查集复杂度 堆 堆 堆简介 二叉堆 配对堆 左偏树 块状数据结构 块状数据结构 分块思想 块状数组 块状链表 树分块 Sqrt Tree 单调栈 单调队列 ST 表 树状数组 线段树 李超线段树 区间最值操作 & 区间历史最值 划分树 二叉搜索树 & 平衡树 二叉搜索树 & 平衡树 二叉搜索树 & 平衡树 Treap Splay 树 WBLT Size Balanced Tree AVL 树 B 树 B+ 树 替罪羊树 Leafy Tree 笛卡尔树 红黑树 左偏红黑树 AA 树 2-3 树 2-3-4 树 跳表 可持久化数据结构 可持久化数据结构 可持久化数据结构简介 可持久化线段树 可持久化块状数组 可持久化平衡树 可持久化字典树 可持久化可并堆 树套树 树套树 线段树套线段树 平衡树套线段树 线段树套平衡树 树状数组套权值线段树 分块套树状数组 K-D Tree 动态树 动态树 Link Cut Tree 全局平衡二叉树 Euler Tour Tree Top Tree 析合树 PQ 树 手指树 霍夫曼树 图论 图论 图论部分简介 图论相关概念 图的存储 DFS（图论） BFS（图论） 树上问题 树上问题 树基础 树的直径 最近公共祖先 树的重心 树链剖分 树上启发式合并 虚树 树分治 动态树分治 AHU 算法 树哈希 树上随机游走 矩阵树定理 有向无环图 拓扑排序 最小生成树 斯坦纳树 最小树形图 最小直径生成树 最短路 拆点 差分约束 k 短路 同余最短路 连通性相关 连通性相关 强连通分量 双连通分量 割点和桥 圆方树 点/边连通度 环计数问题 2-SAT 欧拉图 哈密顿图 二分图 最小环 平面图 图的着色 网络流 网络流 网络流简介 最大流 最小割 费用流 上下界网络流 Stoer–Wagner 算法 图的匹配 图的匹配 图匹配 增广路 二分图最大匹配 二分图最大权匹配 一般图最大匹配 一般图最大权匹配 Prüfer 序列 LGV 引理 弦图 最大团搜索算法 支配树 图上随机游走 计算几何 计算几何 计算几何部分简介 二维计算几何基础 三维计算几何基础 距离 Pick 定理 三角剖分 凸包 扫描线 旋转卡壳 半平面交 平面最近点对 随机增量法 反演变换 计算几何杂项 杂项 杂项 杂项简介 离散化 双指针 离线算法 离线算法 离线算法简介 CDQ 分治 整体二分 莫队算法 莫队算法 莫队算法简介 普通莫队算法 带修改莫队 树上莫队 回滚莫队 二维莫队 莫队二次离线 莫队配合 bitset 分数规划 随机化 随机化 随机函数 随机化技巧 爬山算法 模拟退火 悬线法 计算理论基础 字节顺序 约瑟夫问题 格雷码 表达式求值 在一台机器上规划任务 主元素问题 Garsia–Wachs 算法 15-puzzle Kahan 求和 珂朵莉树/颜色段均摊 专题 专题 RMQ 并查集应用 括号序列 线段树与离线询问 关于 Hulu 关于 Hulu 关于 Hulu 目录 简介 FWT 的运算 FWT 之与（&）运算和或（|）运算 或运算 与运算 异或运算 同或运算 例题 快速沃尔什变换（本文转载自 桃酱的算法笔记，原文戳 链接，已获得作者授权）简介沃尔什转换（Walsh Transform）是在频谱分析上作为离散傅立叶变换的替代方案的一种方法。——维基百科其实这个变换在信号处理中应用很广泛，fft 是 double 类型的，但是 walsh 把信号在不同震荡频率方波下拆解，因此所有的系数都是绝对值大小相同的整数，这使得不需要作浮点数的乘法运算，提高了运算速度。所以，FWT 和 FFT 的核心思想应该是相同的，都是对数组的变换。我们记对数组 进行快速沃尔什变换后得到的结果为 。那么 FWT 核心思想就是：我们需要一个新序列 ，由序列 和序列 经过某运算规则得到，即 ；我们先正向得到 ，再根据 在 的时间复杂度内求出 ；然后逆向运算得到原序列 。时间复杂度为 。在算法竞赛中，FWT 是用于解决对下标进行位运算卷积问题的方法。公式：（其中 是二元位运算中的某一种， 是普通乘法）FWT 的运算FWT 之与（&）运算和或（|）运算与运算和或运算的本质是差不多的，所以这里讲一下或运算，与运算也是可以自己根据公式 yy 出来的。或运算如果有 ，那么 的二进制位为 的位置和 的二进制位为 的位置肯定是 的二进制位为 的位置的子集。现在要得到 ，我们就要构造这个 fwt 的规则。我们按照定义，显然可以构造 ，来表示 满足二进制中 为 的子集。那么显然会有 那么我们接下来看 怎么求。首先肯定不能枚举了，复杂度为 。既然不能整体枚举，我们就考虑分治。我们把整个区间二分，其实二分区间之后，下标写成二进制形式是有规律可循的。我们令 表示 的前一半， 表示区间的后一半，那么 就是 A 下标最大值的最高位为 ，他的子集就是他本身的子集（因为最高位为 了），但是 的最高位是 ，他满足条件的子集不仅仅是他本身，还包最高位为 的子集，即其中 merge 表示像字符串拼接一样把它们拼起来， 就是普通加法，表示对应二进制位相加。这样我们就通过二分能在 的时间复杂度内完成拼接，每次拼接的时候要完成一次运算，也就是说在 的时间复杂度得到了 。接下来就是反演了，其实反演是很简单的，既然知道了 的本身的子集是他自己 ()， 的子集是 （），那就很简单的得出反演的递推式了：与运算与运算类比或运算可以得到类似结论异或运算最常考的异或运算。异或的卷积是基于如下原理：若我们令 中 数量的奇偶性为 与 的奇偶性，那么 与 的奇偶性异或 与 的奇偶性等于 与 的奇偶性。对于 的运算其实也很好得到。公式如下：( 表示 奇偶性为 ， 表示 的奇偶性为 )结论：同或运算类比异或运算给出公式：( 表示 奇偶性为 ， 表示 的奇偶性为 )例题【CF103329F】【XXII Opencup, Grand Prix of XiAn】The Struggle 给出一个椭圆 ，其中所有整点的坐标均在 之间。求 的值。 题解 这是一道比较不裸的题，出题人提供了详细的英文题解，具体请见 此链接。本页面最近更新：2023/5/25 17:17:02，更新历史发现错误？想一起完善？ 在 GitHub 上编辑此页！本页面贡献者：Xeonacid, BinDir0, Enter-tainer, Ir1d, lxlonlyn, nocriz, nocrizwang, Tiphereth-A, TrisolarisHD, xyf007本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用Copyright © 2016 - 2024 OI Wiki Team Made with Material for MkDocs 最近更新：7ff011ae, 2024-03-学习：多项式算法----FWT - 七月流 - 博客园
学习：多项式算法----FWT - 七月流 - 博客园
会员
周边
新闻
博问
AI培训
云市场
所有博客
当前博客
我的博客
我的园子
账号设置
简洁模式 ...
退出登录
注册
登录
七月流的小博客
为算法而生
首页
新随笔
联系
管理
学习：多项式算法----FWT
FWT也称快速沃尔什变换，是用来求多项式之间位运算的系数的。FWT的思想与FFT有异曲同工之妙，但较FFT来说，FWT比较简单。
前言
之前学习FFT（快速傅里叶变换）的时候，我们知道FFT是用来快速求两个多项式乘积的，即求序列C：
$$C_k=\sum_{i+j=k}A_iB_j$$
而FWT解决的多项式的位运算，即知道两个序列A与B，求：
$$C_k=\sum_{i\&j=k}A_iB_j\;\;(\& 表示位运算"与")$$
$$C_k=\sum_{i|j=k}A_iB_j\;\;(| 表示位运算"或")$$
$$C_k=\sum_{i\land j=k}A_iB_j\;\;(\land 表示位运算"异或")$$
如图FFT的解决方法，在FWT中，我们需要找到一种线性变换$FWT$，使得原序列$A$变成一个新的序列$FWT(A)$，新序列与由原序列线性相关。
注意，由于FWT变换是一种线性变换，所以一定满足
$$FWT(A)+FWT(B)=FWT(A+B)$$
与FFT一样，我么需要把序列用0补成2的幂次方个，然后分割成序列为2的区间，然后更新数值，再合并，再一段段更新，再合并....直到最后合并成一个序列，然后进行最后一次更新即可得到变换后的序列。
FWT_OR
已知两个序列A，B，求新的序列C，其中
$$C=\left\{\sum_{i|j=0}A_iB_j,\sum_{i|j=1}A_iB_j,\sum_{i|j=2}A_iB_j,...\right\}$$
故
$$C_k=\sum_{i|j=k}A_iB_j$$
假设序列为$A$，前一半元素（前$2^{n-1}$个）元素组成的序列为$A_0$，后一半元素（后$2^{n-1}$个）元素组成的序列为$A_1$，故$A=(A_0,A_1)$
若序列A的长度为$2^n$，更新方法：
$$FWT(A)=\begin{cases}A&n=0\\(FWT(A_0),FWT(A_0)+FWT(A_1))&n>0\end{cases}$$
","表示合并前后两个序列。
此时可以证明$$FWT(C)=FWT(A|B)=FWT(A)*FWT(B)$$
借某位大佬的证明方法：
$FWT(A|B)=FWT((A|B)_0,(A|B)_1)$
$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =FWT(A_0|B_0,A0|B_1+A_1|B0+A_1|B_1)$
$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =(FWT(A_0|B_0),FWT(A_0|B_0+A_0|B_1+A_1|B_0+A_1|B_1))$
$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =(FWT(A_0)×FWT(B_0),$
$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ FWT(A_0)×FWT(B_0)+FWT(A_0)×FWT(B_1)+$
$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ FWT(A_1)×FWT(B_0)+FWT(A_1)×FWT(B_1))$
$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =(FWT(A_0)×FWT(B_0),(FWT(A_0)+FWT(A_1))×$
$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (FWT(B_0)+FWT(B_1)))$
$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =(FWT(A_0),FWT(A_0+A_1))×(FWT(B_0),FWT(B_0+B_1))$
$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =FWT(A)×FWT(B)$
然后对FWT(C)序列进行FWT逆变换（UFWT）即可得到C序列。
逆变换的更新方法可以根据正变换的形式得到，为
$$UFWT(A)=(UFWT(A_0),UFWT(A_1)-UFWT(A_0))$$
FWT或变换代码：
typedef long long ll;
void FWT_or(ll *a,int n){
for(int i=2;i<=n;i<<=1)//i表示分治的区间
for(int p=i>>1,j=0;j for(int k=j;k a[k+p]+=a[k];//更新 return; } UFWT或变换代码： typedef long long ll; void UFWT_or(ll *a,int n){ for(int i=2;i<=n;i<<=1) for(int p=i>>1,j=0;j for(int k=j;k a[k+p]-=a[k]; return; } 合并代码： void FWT_or(ll *a,int n,int opt){ for(int i=2;i<=n;i<<=1) for(int p=i>>1,j=0;j for(int k=j;k a[k+p]+=a[k]*opt; return; } U/FWT_or FWT_AND 已知两个序列A，B，求新的序列C，其中 $$C=\left\{\sum_{i\&j=0}A_iB_j,\sum_{i\&j=1}A_iB_j,\sum_{i\&j=2}A_iB_j,...\right\}$$ 故 $$C_k=\sum_{i\&j=k}A_iB_j$$ 假设序列为$A$，前一半元素（前$2^{n-1}$个）元素组成的序列为$A_0$，后一半元素（后$2^{n-1}$个）元素组成的序列为$A_1$，故$A=(A_0,A_1)$ 若序列A的长度为$2^n$，更新方法： $$FWT(A)=\begin{cases}A&n=0\\(FWT(A_0)+FWT(A_1),FWT(A_1))&n>0\end{cases}$$ ","表示合并前后两个序列。 此时也可以证明$$FWT(C)=FWT(A\&B)=FWT(A)*FWT(B)$$ 证明方法： $FWT(A\&B)=FWT((A\&B)_0,(A\&B)_1)$ $\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =FWT(A_0\&B_0+A_0\&B_1+A_1\&B_0,A_1\&B_1)$ $\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =(FWT(A_0\&B_0+A_0\&B_1+A_1\&B_0+A_1\&B_1),FWT(A_1\&B_1))$ $\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =((FWT(A0)+FWT(A1))×(FWT(B0)+FWT(B1)),FWT(A1)∗FWT(B1))$ $\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =(FWT(A0+A1),FWT(A1))×(FWT(B0+B1),FWT(B1))$ $\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =FWT(A)×FWT(B)$ 然后对FWT(C)序列进行FWT逆变换（UFWT）即可得到C序列。 逆变换的更新方法可以根据正变换的形式得到，为 $$UFWT(A)=(UFWT(A_0)-UFWT(A_1),UFWT(A_1))$$ FWT与变换代码： void FWT_and(ll *a,int n){ for(int i=2;i<=n;i<<=1) for(int p=i>>1,j=0;j for(int k=j;k a[k]+=a[k+p]; return; } UFWT或变换代码： void UFWT_and(ll *a,int n){ for(int i=2;i<=n;i<<=1) for(int p=i>>1,j=0;j for(int k=j;k a[k]-=a[k+p]; return; } 合并代码： void FWT_and(ll *a,int n,int opt){ for(int i=2;i<=n;i<<=1) for(int p=i>>1,j=0;j for(int k=j;k a[k]+=a[k+p]*opt; return; } U/FWT_and FWT_XOR 已知两个序列A，B，求新的序列C，其中 $$C=\left\{\sum_{i\oplus j=0}A_iB_j,\sum_{i\oplus j=1}A_iB_j,\sum_{i\oplus j=2}A_iB_j,...\right\}$$ 故 $$C_k=\sum_{i\oplus j=k}A_iB_j$$ 假设序列为$A$，前一半元素（前$2^{n-1}$个）元素组成的序列为$A_0$，后一半元素（后$2^{n-1}$个）元素组成的序列为$A_1$，故$A=(A_0,A_1)$ 若序列A的长度为$2^n$，更新方法： $$FWT(A)=\begin{cases}A&n=0\\(FWT(A_0)+FWT(A_1),FWT(A_0)-FWT(A_1))&n>0\end{cases}$$ ","表示合并前后两个序列。 此时仍然可以证明$$FWT(C)=FWT(A\oplus B)=FWT(A)*FWT(B)$$ 证明方法： $FWT(A⊕B)=(FWT(A⊕B)_0+FWT(A⊕B)_1,FWT(A⊕B)_0−FWT(A⊕B)_1)$ $\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =(FWT(A_0⊕B_0+A_1⊕B_1+A_1⊕B_0+A_0⊕B_1),$ $\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ FWT(A_0⊕B_0+A_1⊕B_1−A_1⊕B_0−A_0⊕B_1))$ $\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =((FWT(A_0)+FWT(A_1))×(FWT(B_0)+FWT(B_1)),$ $\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (FWT(A_0)−FWT(A_1))×(FWT(B_0)−FWT(B_1))$ $\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =(FWT(A_0+A_1)×(B_0+B_1),FWT(A_0−A_1)×FWT(B_0−B_1))$ $\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =(FWT(A_0+A_1),FWT(A_0−A_1))×(FWT(B_0+B_1),FWT(B_0−B_1))$ $\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =FWT(A)×FWT(B)$ 然后对FWT(C)序列进行FWT逆变换（UFWT）即可得到C序列。 逆变换的更新方法可以根据正变换的形式得到，为 $$UFWT(A)=(\frac {UFWT(A_0)+UFWT(A_1)}2,\frac {UFWT(A_0)-UFWT(A_1)}2)$$ FWT异或变换代码： void FWT_xor(ll *a,int n){ for(int i=2;i<=n;i<<=1) for(int p=i>>1,j=0;j for(int k=j;k ll x=a[k],y=a[k+p]; a[k]=x+y;a[k+p]=x-y; } return 0; } UFWT变换代码： void UFWT_xor(ll *a,int n){ for(int i=2;i<=n;i<<=1) for(int p=i>>1,j=0;j for(int k=j;k ll x=a[k],y=a[k+p]; a[k]=(x+y)/2,a[k+p]=(x-y)/2; } return 0; } 合并代码： void FWT_xor(ll *a,int n,int opt){ for(int i=2;i<=n;i<<=1) for(int p=i>>1,j=0;j for(int k=j;k ll x=a[k],y=a[k+p]; if(opt==1) a[k]=x+y;a[k+p]=x-y; else a[k]=(x+y)/2,a[k+p]=(x-y)/2; } return 0; } U/FWT_xor FWT异或变换的特殊作用 在FWT异或变换中，我们主要解决一个问题 $$h(i)=\sum_{j\oplus k=i}f(j)g(k)$$ 根据某站某大佬的讲解，假设存在三个集合$L,R,S$满足 $$h(S)=\sum_{R\oplus L=i}f(R)g(L)$$ 则为了解决快速多项式异或，我们需要将上面的式子变形。 首先介绍一个等式，假设全集为U，集合内有n个元素，其中$|T|$表示集合T的大小，则 $$\frac 1{2^n}\sum_{T\subseteq U}(-1)^{|W\cap T|}=1$$ 上面的式子仅在$W=\varnothing$时成立 解释一下：由于集合$T$是集合$U$的子集，故集合$T$有$2^n$中可能，一旦$W$不是空集，$(-1)^{|W\cap T|}$就可能等于1，那么$\sum_{T\subseteq U}(-1)^{|W\cap T|}$就会小于$2^n$。所以只有当$W$是空集时，上面式子才等于1 有了上面的等式，就可以变形了，由于$R\oplus L=S$，故$R\oplus L\oplus S=\varnothing$ $$h(S)=\sum_{R\oplus L=i}f(R)g(L)$$ $$=\sum_{R\subseteq U}\sum_{L\subseteq U}[R\oplus L\oplus S=\varnothing]f(L)g(R)$$ $$=\sum_{R\subseteq U}\sum_{L\subseteq U}\frac 1{2^n}\sum_{T\subseteq U}(-1)^{|R\oplus L\oplus S\cap T|}f(L)g(R)$$ 下面证明$|T\cap \oplus^{n}_{i=1}S_i|$与$\sum_{i=1}^n|S_i\cap T|$的奇偶性相同，先证明n=2的情况： 假设$|T\cap S_1|=A,|T\cap S_2|=B$ 1.假设$T\cap S_1$与$T\cap S_2$没有相同位的数相同，那么： $$(-1)^{\sum_{i=1}^2|S_i\cap T|}=(-1)^{|S_1\cap T|+|S_2\cap T|}=(-1)^{A+B}=(-1)^{|T\cap (S_1\oplus S_2)|}$$ 2.假设$T\cap S_1$与$T\cap S_2$有x组相同位的数相同，那么： $$(-1)^{\sum_{i=1}^2|S_i\cap T|}=(-1)^{|S_1\cap T|+|S_2\cap T|}=(-1)^{A+B}$$$$(-1)^{|T\cap (\oplus_{i=1}^2S_i)|}=(-1)^{|T\cap (S_1\oplus S_2)|}=(-1)^{A+B-2x}=(-1)^{A+B}$$ 当然n等于任何数的时候也是像上面一样可以证明的，所以$$(-1)^{|R\oplus L\oplus S\cap T|}=(-1)^{|R\cap T|+|S\cap T|+|L\cap T|}$$ 故上面式子继续变形可得 $$\frac 1{2^n}\sum_{L\subseteq U}\sum_{R\subseteq U}\sum_{T\subseteq U}(-1)^{|L\cap T|}(-1)^{|R\cap T|}(-1)^{|S\cap T|}f(R)g(L)$$ 于是发现了FWT_xor变形的本质，即变形后的序列$f(T)$与变形前序列$f(R)$的关系 $$f(T)=\sum_{R\subseteq U}(-1)^{|R\cap T|}f(R)$$ 通过以上的探究，得到结论：假设原序列为A，变形后的序列为A'，那么 $$A'[x]=\sum_{|x\&i|\bmod {2}=0}A[i]-\sum_{|x\&i|\bmod {2}\neq 0}A[i]$$ 例题 1.2019牛客暑期多校训练营（第一场）----D-Parity of Tuples：https://blog.csdn.net/weixin_43702895/article/details/97114770 posted @ 2019-10-03 20:06 七月流 阅读(2110) 评论(0) 编辑 收藏 举报 会员力量，点亮园子希望 刷新页面返回顶部 公告 Copyright © 2024 七月流 Powered by .NET 8.0 on Kubernetes 算法笔记｜快速沃尔什变换 FWT（或卷积、与卷积、异或卷积） - 知乎切换模式写文章登录/注册算法笔记｜快速沃尔什变换 FWT（或卷积、与卷积、异或卷积）牛客竞赛致力于为中小学生提供NOI/NOIP等比赛信息资讯作者：hydingsy链接：https://ac.nowcoder.com/discuss/175529来源：牛客网快速沃尔什变换用于解决多项式位运算卷积。其计算过程和 \text{FFT} 类似。概述首先我们回忆一下多项式卷积： C_k = \sum_{i + j = k} A_i\times B_j 在「算法笔记」快速傅里叶变换 FFT 中我们将多项式 A(x) 和B(x) 转化为点值表达，然后重新转化为系数表达。接下来考虑如下卷积形式：\begin{align*} C_k &= \sum_{i | j = k} A_i\times B_j \\ C_k &= \sum_{i \& j = k} A_i\times B_j \\ C_k &= \sum_{i \oplus j = k} A_i\times B_j \end{align*} 其中 |, \&, \oplus 分别表示按位或、按位与、按位异或。这样就没法使用 \text{FFT} 解决了，我们需要引进新的方法：快速沃尔什变换。下文会分类介绍这 3 类卷积的解决方法。其中定义部分是一种构造出来的变换方法，证明部分将使用数学归纳法证明一些引理或定理，代码部分为该卷积的实现。符号表示首先我们认为下文提及的多项式的长度均为 2 的非负整数次幂。为了方便表述，我们定义如下如下符号及其含义，下文不再赘述。\begin{array}{} A, B & \text{多项式，其长度为}\ n\text{，次数为}\ n - 1 \\ A_0, A_1 & \text{多项式}\ A\ \text{的前}\ \frac{n}{2}\ \text{位、后}\ \frac{n}{2}\ \text{位} \\ A + B & \text{将多项式}\ A, B\ \text{对应位加（减、乘），} \\ & \text{其系数表达式为}\ (A_0 + B_0, A_1 + B_1, \cdots, A_{n - 1} + B_{n - 1}) \\ A \oplus B & \text{将多项式}\ A, B\ \text{异或（与、或）卷积，} \\ & \text{其系数表达式为}\ (\sum_{i \oplus j = 0} A_i \times B_j, \sum_{i \oplus j = 1} A_i \times B_j, \cdots, \sum_{i \oplus j = n - 1} A_i \times B_j) \\ \text{FWT}(A) & \text{多项式}\ A\ \text{的 FWT 变换} \\ (A, B) & \text{将多项式}\ A, B\ \text{前后拼接起来} \end{array} 其中需要尤其注意：这里定义的多项式异或、与、或均为卷积形式！并不是对应系数位运算！或卷积定义\text{FWT}(A) = \begin{cases} (\text{FWT}(A_0), \text{FWT}(A_0 + A_1)) & n > 1 \\ A & n = 1 \end{cases} 证明1、两个多项式相加后的 \text{FWT} 变换等于分别 \text{FWT} 的和： \text{FWT}(A + B) = \text{FWT}(A) + \text{FWT}(B) 当 n = 1 时 \begin{align*} \text{FWT}(A + B) & = A + B \\ & = \text{FWT}(A) + \text{FWT}(B) \end{align*} 当 n > 1 时 \begin{align*} \text{FWT}(A + B) & = (\text{FWT}(A_0 + B_0), \text{FWT}(A_0 + A_1 + B_0 + B_1)) \\ & = (\text{FWT}(A_0) + \text{FWT}(B_0), \text{FWT}(A_0) + \text{FWT}(A_1) + \text{FWT}(B_0) + \text{FWT}(B_1)) \\ & = (\text{FWT}(A_0) , \text{FWT}(A_0) + \text{FWT}(A_1)) + (\text{FWT}(B_0), \text{FWT}(B_0) + \text{FWT}(B_1)) \\ & = \text{FWT}(A) + \text{FWT}(B) \end{align*} 2、两个多项式或卷积的 \text{FWT} 变换等于分别 \text{FWT} 的积： \text{FWT}(A | B) = \text{FWT}(A)\times FWT(B) 当 n = 1 时 \begin{align*} \text{FWT}(A | B) & = A \times B \\ & = \text{FWT}(A) \times \text{FWT}(B) \end{align*} 当 n > 1 时 \begin{align*} \text{FWT}(A | B) & = \text{FWT}((A | B)_0, (A | B)_1) \\ & = \text{FWT}(A_0 | B_0, A_0 | B_1 + A_1 | B_0 + A_1 | B_1) \\ & = (\text{FWT}(A_0 | B_0), \text{FWT}(A_0 | B_0 + A_0 | B_1 + A_1 | B_0 + A_1 | B_1)) \\ & = (\text{FWT}(A_0) \times \text{FWT}(B_0), \\ & \qquad \text{FWT}(A_0) \times \text{FWT}(B_0) + \text{FWT}(A_0) \times \text{FWT}(B_1) + \text{FWT}(A_1) \times \text{FWT}(B_0) + \text{FWT}(A_1) \times \text{FWT}(B_1)) \\ & = (\text{FWT}(A_0) \times \text{FWT}(B_0), (\text{FWT}(A_0) + \text{FWT}(A_1)) \times (\text{FWT}(B_0) + \text{FWT}(B_1))) \\ & = (\text{FWT}(A_0) \times \text{FWT}(B_0), \text{FWT}(A_0 + A_1) \times \text{FWT}(B_0 + B_1)) \\ & = (\text{FWT}(A_0), \text{FWT}(A_0 + A_1)) \times (\text{FWT}(B_0), \text{FWT}(B_0 + B_1)) \\ & = \text{FWT}(A)\times \text{FWT}(B) \end{align*}逆变换代码void FWTor(std::vector int n = a.size(); for (int l = 2, m = 1; l <= n; l <<= 1, m <<= 1) { for (int j = 0; j < n; j += l) for (int i = 0; i < m; i++) { if (!rev) add(a[i + j + m], a[i + j]); else sub(a[i + j + m], a[i + j]); } } } 与卷积定义\text{FWT}(A) = \begin{cases} (\text{FWT}(A_0 + A_1), \text{FWT}(A_1)) & n > 1 \\ A & n = 1 \end{cases} 证明1、两个多项式相加后的 \text{FWT} 变换等于分别 \text{FWT} 的和： \text{FWT}(A + B) = \text{FWT}(A) + \text{FWT}(B) 当 n=1 时 \begin{align*} \text{FWT}(A + B) & = A + B \\ & = \text{FWT}(A) + \text{FWT}(B) \end{align*} 当 n > 1 时 \begin{align*} \text{FWT}(A + B) & = (\text{FWT}(A_0 + A_1 + B_0 + B_1), \text{FWT}(A_1 + B_1)) \\ & = (\text{FWT}(A_0) + \text{FWT}(A_1) + \text{FWT}(B_0) + \text{FWT}(B_1), \text{FWT}(A_1) + \text{FWT}(B_1)) \\ & = (\text{FWT}(A_0) + \text{FWT}(A_1), \text{FWT}(A_1)) + (\text{FWT}(B_0) + \text{FWT}(B_1), \text{FWT}(B_1)) \\ & = \text{FWT}(A) + \text{FWT}(B) \end{align*} 2、两个多项式与卷积的 \text{FWT} 变换等于分别 \text{FWT} 的积： \text{FWT}(A \& B) = \text{FWT}(A)\times FWT(B) 当 n = 1 时 \begin{align*} \text{FWT}(A \& B) & = A \times B \\ & = \text{FWT}(A) \times \text{FWT}(B) \end{align*} 当 n > 1 时 \begin{align*} \text{FWT}(A \& B) & = \text{FWT}((A \& B)_0, (A \& B)_1) \\ & = \text{FWT}(A_0 \& B_0 + A_1 \& B_0 + A_0 \& B_1, A_1 \& B_1) \\ & = (\text{FWT}(A_0 \& B_0 + A_1 \& B_0 + A_0 \& B_1 + A_1 \& B_1), \text{FWT}(A_1 \& B_1)) \\ & = (\text{FWT}(A_0) \times \text{FWT}(B_0) + \text{FWT}(A_0) \times \text{FWT}(B_1) + \text{FWT}(A_1) \times \text{FWT}(B_0) + \text{FWT}(A_1) \times \text{FWT}(B_1), \\ & \qquad \text{FWT}(A_1) \times \text{FWT}(B_1)) \\ & = ((\text{FWT}(A_0) + \text{FWT}(A_1)) \times (\text{FWT}(B_0) + \text{FWT}(B_1)), \text{FWT}(A_1) \times \text{FWT}(B_1)) \\ & = (\text{FWT}(A_0 + A_1) \times \text{FWT}(B_0 + B_1), \text{FWT}(A_1) \times \text{FWT}(B_1)) \\ & = (\text{FWT}(A_0 + A_1), \text{FWT}(A_1)) \times (\text{FWT}(B_0 + B_1), \text{FWT}(B_1)) \\ & = \text{FWT}(A)\times \text{FWT}(B) \end{align*} 逆变换\text{FWT}(A) = (\text{FWT}(A_0) + \text{FWT}(A_1), \text{FWT}(A_1)) \\ \text{IFWT}(A) = (\text{IFWT}(A_0) - \text{IFWT}(A_1), \text{IFWT}(A_1)) 代码void FWTand(std::vector int n = a.size(); for (int l = 2, m = 1; l <= n; l <<= 1, m <<= 1) { for (int j = 0; j < n; j += l) for (int i = 0; i < m; i++) { if (!rev) add(a[i + j], a[i + j + m]); else sub(a[i + j], a[i + j + m]); } } } 异或卷积定义\text{FWT}(A) = \begin{cases} (\text{FWT}(A_0 + A_1), \text{FWT}(A_0 -A_1)) & n > 1 \\ A & n = 1 \end{cases} 证明1、两个多项式相加后的 \text{FWT} 变换等于分别 \text{FWT} 的和： \text{FWT}(A + B) = \text{FWT}(A) + \text{FWT}(B) 当 n = 1 时 \begin{align*} \text{FWT}(A + B) & = A + B \\ & = \text{FWT}(A) + \text{FWT}(B) \end{align*} 当 n > 1 时 \begin{align*} \text{FWT}(A + B) & = (\text{FWT}(A_0 + A_1 + B_0 + B_1), \text{FWT}(A_0 - A_1 + B_0 - B_1)) \\ & = (\text{FWT}(A_0) + \text{FWT}(A_1) + \text{FWT}(B_0) + \text{FWT}(B_1), \text{FWT}(A_0) - \text{FWT}(A_1) + \text{FWT}(B_0) - \text{FWT}(B_1)) \\ & = (\text{FWT}(A_0) + \text{FWT}(A_1), \text{FWT}(A_0) - \text{FWT}(A_1)) + (\text{FWT}(B_0) + \text{FWT}(B_1), \text{FWT}(B_0) - \text{FWT}(B_1)) \\ & = \text{FWT}(A) + \text{FWT}(B) \end{align*} 2、两个多项式异或卷积的 \text{FWT} 变换等于分别 \text{FWT} 的积： \text{FWT}(A \oplus B) = \text{FWT}(A)\times FWT(B) 当 n = 1 时 \begin{align*} \text{FWT}(A \oplus B) & = A \times B \\ & = \text{FWT}(A) \times \text{FWT}(B) \end{align*} 当 n > 1 时 \begin{align*} \text{FWT}(A \oplus B) & = \text{FWT}((A \oplus B)_0, (A \oplus B)_1) \\ & = \text{FWT}(A_0 \oplus B_0 + A_1 \oplus B_1, A_0 \oplus B_1 + A_1 \oplus B_0) \\ & = (\text{FWT}(A_0 \oplus B_0 + A_1 \oplus B_1 + A_0 \oplus B_1 + A_1 \oplus B_0), \text{FWT}(A_0 \oplus B_0 + A_1 \oplus B_1 - A_0 \oplus B_1 - A_1 \oplus B_0)) \\ & = (\text{FWT}(A_0) \times \text{FWT}(B_0) + \text{FWT}(A_1) \times \text{FWT}(B_1) + \text{FWT}(A_0) \times \text{FWT}(B_1) + \text{FWT}(A_1) \times \text{FWT}(B_0), \\ & \qquad \text{FWT}(A_0) \times \text{FWT}(B_0) + \text{FWT}(A_1) \times \text{FWT}(B_1) - \text{FWT}(A_0) \times \text{FWT}(B_1) - \text{FWT}(A_1) \times \text{FWT}(B_0)) \\ & = ((\text{FWT}(A_0) + \text{FWT}(A_1)) \times (\text{FWT}(B_0) + \text{FWT}(B_1)), (\text{FWT}(A_0) - \text{FWT}(A_1)) \times (\text{FWT}(B_0) - \text{FWT}(B_1))) \\ & = (\text{FWT}(A_0 + A_1) \times \text{FWT}(B_0 + B_1), \text{FWT}(A_0 - A_1) \times \text{FWT}(B_0 - B_1)) \\ & = (\text{FWT}(A_0 + A_1), \text{FWT}(A_0 - A_1)) \times (\text{FWT}(B_0 + B_1), \text{FWT}(B_0 - B_1)) \\ & = \text{FWT}(A)\times \text{FWT}(B) \end{align*} 逆变换\text{FWT}(A) = (\text{FWT}(A_0) + \text{FWT}(A_1), \text{FWT}(A_0) - \text{FWT}(A_1)) \\ \text{IFWT}(A) = \left(\frac{\text{IFWT}(A_0) + \text{IFWT}(A_1)}{2}, \frac{\text{IFWT}(A_0) - \text{IFWT}(A_1)}{2}\right) 代码void FWTxor(std::vector int n = a.size(), inv2 = (P + 1) >> 1; for (int l = 2, m = 1; l <= n; l <<= 1, m <<= 1) { for (int j = 0; j < n; j += l) for (int i = 0; i < m; i++) { int x = a[i + j], y = a[i + j + m]; if (!rev) { a[i + j] = (x + y) % P; a[i + j + m] = (x - y + P) % P; } else { a[i + j] = 1LL * (x + y) * inv2 % P; a[i + j + m] = 1LL * (x - y + P) * inv2 % P; } } } } 完整代码#include #include #include const int P = 998244353; void add(int &x, int y) { (x += y) >= P && (x -= P); } void sub(int &x, int y) { (x -= y) < 0 && (x += P); } struct FWT { int extend(int n) { int N = 1; for (; N < n; N <<= 1); return N; } void FWTor(std::vector int n = a.size(); for (int l = 2, m = 1; l <= n; l <<= 1, m <<= 1) { for (int j = 0; j < n; j += l) for (int i = 0; i < m; i++) { if (!rev) add(a[i + j + m], a[i + j]); else sub(a[i + j + m], a[i + j]); } } } void FWTand(std::vector int n = a.size(); for (int l = 2, m = 1; l <= n; l <<= 1, m <<= 1) { for (int j = 0; j < n; j += l) for (int i = 0; i < m; i++) { if (!rev) add(a[i + j], a[i + j + m]); else sub(a[i + j], a[i + j + m]); } } } void FWTxor(std::vector int n = a.size(), inv2 = (P + 1) >> 1; for (int l = 2, m = 1; l <= n; l <<= 1, m <<= 1) { for (int j = 0; j < n; j += l) for (int i = 0; i < m; i++) { int x = a[i + j], y = a[i + j + m]; if (!rev) { a[i + j] = (x + y) % P; a[i + j + m] = (x - y + P) % P; } else { a[i + j] = 1LL * (x + y) * inv2 % P; a[i + j + m] = 1LL * (x - y + P) * inv2 % P; } } } } std::vector int n = std::max(a1.size(), a2.size()), N = extend(n); a1.resize(N), FWTor(a1, false); a2.resize(N), FWTor(a2, false); std::vector for (int i = 0; i < N; i++) A[i] = 1LL * a1[i] * a2[i] % P; FWTor(A, true); return A; } std::vector int n = std::max(a1.size(), a2.size()), N = extend(n); a1.resize(N), FWTand(a1, false); a2.resize(N), FWTand(a2, false); std::vector for (int i = 0; i < N; i++) A[i] = 1LL * a1[i] * a2[i] % P; FWTand(A, true); return A; } std::vector int n = std::max(a1.size(), a2.size()), N = extend(n); a1.resize(N), FWTxor(a1, false); a2.resize(N), FWTxor(a2, false); std::vector for (int i = 0; i < N; i++) A[i] = 1LL * a1[i] * a2[i] % P; FWTxor(A, true); return A; } } fwt; int main() { int n; scanf("%d", &n); std::vector for (int i = 0; i < n; i++) scanf("%d", &a1[i]); for (int i = 0; i < n; i++) scanf("%d", &a2[i]); std::vector A = fwt.Or(a1, a2); for (int i = 0; i < n; i++) { printf("%d%c", A[i], " \n"[i == n - 1]); } A = fwt.And(a1, a2); for (int i = 0; i < n; i++) { printf("%d%c", A[i], " \n"[i == n - 1]); } A = fwt.Xor(a1, a2); for (int i = 0; i < n; i++) { printf("%d%c", A[i], " \n"[i == n - 1]); } return 0; } 习题「Luogu 4717」【模板】快速沃尔什变换「BZOJ 4589」Hard Nim「hihoCoder 1230」The Celebration of Rabbits「HDU 5909」Tree Cutting与作者交流：https://ac.nowcoder.com/discuss/175529更多算法和题解：https://ac.nowcoder.com/acm/contest/discuss发布于 2019-05-16 16:26算法卷积赞同 27添加评论分享喜欢收藏申请 FWT快速沃尔什变换学习笔记 - 小蒟蒻yyb - 博客园 会员 周边 新闻 博问 AI培训 云市场 所有博客 当前博客 我的博客 我的园子 账号设置 简洁模式 ... 退出登录 注册 登录 小蒟蒻yyb的博客 AFO 博客园 首页 新随笔 联系 订阅 管理 FWT快速沃尔什变换学习笔记 FWT快速沃尔什变换学习笔记 1、FWT用来干啥啊 回忆一下多项式的卷积\(C_k=\sum_{i+j=k}A_i*B_j\) 我们可以用\(FFT\)来做。 甚至在一些特殊情况下，我们\(C_k=\sum_{i*j=k}A_i*B_j\)也能做（SDOI2015 序列统计）。 但是，如果我们把操作符换一下呢？ 比如这样？ \(C_k=\sum_{i|j=k}A_i*B_j\) \(C_k=\sum_{i\&j=k}A_i*B_j\) \(C_k=\sum_{i\wedge j=k}A_i*B_j\) 似乎这就不能用\(FFT\)来做了。 这样子就有了\(FWT\)——用来解决多项式的位运算卷积 2、FWT大概要怎么搞啊 我们想一想\(FFT\)在干啥？ 先对于一个多项式求出他在若干个单位根的点值表示法 再将多项式乘起来，最后再复原。 那么，我们可不可以用一个类似的思路呢？ 先将多项式求出另外一个多项式\(FWT(A)\)，再将对应的位置乘起来，最后再复原？ 也就是\(FWT(C)=FWT(A)*FWT(B)\)（这个不是卷积，是对应位置相乘）? 废话，显然可以，要不然我还写什么\(FWT\)呢？ 我们先来一点奇奇怪怪的记号吧。 因为多项式可以看成一个\(n\)维向量 所以，我们定义以下东西： \(A+B=(A_0+B_0,A_1+B_1,......)\) \(A-B=(A_0-B_0,A_1-B_1,......)\) \(A\oplus B=(\sum_{i\oplus j=0}A_i*B_j,\sum_{i\oplus j=1}A_i*B_j,......)\) 3、或(or)卷积 或卷积长成这个样子：\(C_k=\sum_{i|j=k}A_i*B_j\) 写成向量的形式也就是这样子：\(A|B=(\sum_{i|j=0}A_i*B_j,\sum_{i|j=1}A_i*B_j,......)\) 很显然的一点：这个东西满足交换律，也就是\(A|B=B|A\) 再来仔细的看看，这个东西也满足结合律。 简单的证明一下\((A+B)|C=(\sum_{i|j=0}(A_i+B_i)*C_j,......)\) 很明显可以把括号拆开，然后分成两个\(\sum\)，也就是\(A|C+B|C\) 我们这样子定义一下： 对于一个多项式\(A\)(最高次项是\(2^n\)), 我们把它分成两部分\(A_0,A_1\)，分别表示前\(2^{n-1}\)次项和后面的\(2^{n-1}\)次项 也就是最高位为\(0\)与\(1\)的两部分。 对于或卷积，我们有： \[FWT(A)=\begin{cases}(FWT(A_0),FWT(A_0+A_1)) & n\gt0 \\ A & n=0\end{cases} \]对于\(n=0\)的时候，这个是非常显然的（常数还不显然了。。。） 啥？你问打个括号，然后中间一个逗号是啥意思？ 不是说了这个结果是一个\(2^n\)维向量？ 也就表示前\(2^{n-1}\)项是逗号前面的东西，后面那几项是逗号后面的东西 完全可以理解为将两个多项式强行前后拼接成一个新的多项式。 好的，我们来伪证（感性理解）一下\(n>0\)的时候的式子 对于\(A_0\)中的任意一项，如果在做\(or\)卷积的时候，和任意一个\(A_1\)中的项\(or\)了一下 那么它的首位一定是\(1\),必定不会对于\(FWT(A_0)\)产生任何贡献， 所以\(FWT(A)\)的前\(2^{n-1}\)项一定等于\(FWT(A_0)\)。 后面这个东西看起来就很不好证明了，所以我们先考虑证明点别的东西。 \(FWT(A+B)=FWT(A)+FWT(B)\) 证明（伪）： 对于一个多项式\(A\)的\(FWT(A)\)，它一定只是若干个原多项式中的若干项的若干倍的和。 即\(FWT(A)\)一定不包含原多项式的某几项的乘积。 如果包含了原多项式的乘积，那么在求出卷积之后， 我们发现此时的结果与某个多项式自身的某两项的乘积有关 但是我们在或卷积的结果式中发现一定只与某个多项式的某一项与另一个多项式的某一项有关。 因此，我们知道\(FWT(A)\)的任意一项只与\(A\)的某几项的和有关 因此，我们这个式子可以这样拆开。 此时，这个伪证成立。（这话怎么这么别扭） 但是怎么说，总是感觉证明后面都要贴上一个伪字， 如果我们能够知道\(FWT(A)\)是个啥东西，我们就可以把这个字给扔掉了 先给出结论： 对于\(or\)卷积而言,\(FWT(A)[i]=\sum_{j|i=i}A[j]\) 它基于的原理呢？ 如果\(i|k=k,j|k=k\)，那么就有\((i|j)|k=k\) 这样说很不清楚，我们现在来证明后半部分为啥是\(FWT(A_0+A_1)\) 因为\(A_0\)中取一项和\(A_1\)中取一项做\(or\)卷积，显然贡献会产生到\(A_1\)中去 首先，对于\(A_1\)中的任意两项的贡献，一定在\(A_1\)中，即使去掉了最高位，此时也会产生这部分的贡献 但是现在在合并\(A_0\)和\(A_1\)的贡献的时候，还需要考虑\(A_0\)的贡献 相当于只丢掉了最高位，因此，在\(A_0\)与\(A_1\)对应项的\(FWT\)的和就是我们现在合并之后的结果 所以也就是\(FWT(A_0+A_1)=FWT(A_0)+FWT(A_1)\) 这样子，我们来考虑或卷积，也就是\(FWT(A|B)\) 我们要证明它等于\(FWT(A)\times FWT(B)\)，这样子我们就可以放心的使用\(or\)卷积了 证明： \[\begin{aligned} FWT(A|B)=&FWT((A|B)_0,(A|B)_1)\\ =&FWT(A_0|B_0,A_0|B_1+A_1|B_0+A_1|B_1)\\ =&(FWT(A_0|B_0),FWT(A_0|B_0+A_0|B_1+A_1|B_0+A_1|B_1))\\ =&(FWT(A_0)\times FWT(B_0)\\&,FWT(A_0)\times FWT(B_0)+FWT(A_0)\times FWT(B_1)+FWT(A_1)\times FWT(B_0)+FWT(A_1)\times FWT(B_1))\\ =&(FWT(A_0)\times FWT(B_0),(FWT(A_0)+FWT(A_1))\times (FWT(B_0)+FWT(B_1)))\\ =&(FWT(A_0),FWT(A_0+A_1))\times (FWT(B_0),FWT(B_0+B_1))\\ =&FWT(A)\times FWT(B) \end{aligned} \]这是一个数学归纳法的证明，请仔细看一看QwQ 当只有一项的时候这个是显然的。 好啦，这样就证明出了\(or\)卷积的正确性了 4、和(and)卷积 \(and\)卷积是这样的：\(C_k=\sum_{i\&j=k}A_i*B_j\) 写成向量的形式：\(A\&B=(\sum_{i\&j=0}A_i*B_j,\sum_{i\&j=1}A_i*B_j,......)\) 交换律？\(A\&B=B\&A\)显然成立 结合律？和前面一样是满足的。 好的，先把变换的式子写出来。 \[FWT(A)=\begin{cases}(FWT(A_0+A_1),FWT(A_1)) & n\gt0 \\ A & n=0\end{cases} \]从某种意义上来说，\(and\)和\(or\)和很类似的。 我们这样看： \(0|0=0,0|1=1,1|0=1,1|1=1\) \(0\&0=0,0\&1=0,1\&0=0,1\&1=1\) 都是\(3\)个\(0/1\)，然后剩下的那个只有一个 既然如此，其实我们也可以用\(or\)卷积类似的东西很容易的证明\(and\)卷积 \(FWT(A+B)=FWT(A)+FWT(B)\) 大致的伪证就是\(FWT(A)\)是关于\(A\)中元素的一个线性组合，显然满足分配率 接着只要再证明 \(FWT(A)\times FWT(B)=FWT(A\&B)\)就行了 方法仍然是数学归纳法。 证明： \[\begin{aligned} FWT(A\&B)=&FWT((A\&B)_0,(A\&B)_1)\\ =&FWT(A_0\&B_0+A_0\&B_1+A_1\&B_0,A_1\&B_1)\\ =&(FWT(A_0\&B_0+A_0\&B_1+A_1\&B_0+A_1\&B_1),FWT(A_1\&B_1))\\ =&((FWT(A_0)+FWT(A_1))\times (FWT(B_0)+FWT(B_1)),FWT(A_1)*FWT(B_1))\\ =&(FWT(A_0+A_1),FWT(A_1))\times (FWT(B_0+B_1),FWT(B_1))\\ =&FWT(A)\times FWT(B) \end{aligned} \]好啦，这样子\(and\)卷积就证明完啦。 5、异或(xor)卷积 为了方便打，我就把异或操作用\(\oplus\)来表示吧(而且这样似乎也是一种常用的表达方式) 主要原因是\(\wedge\)太难打了 表达式：\(C_k=\sum_{i\oplus j=k}A_i*B_j\) 向量式按照上面写就行了 先写一下\(FWT(A)\)吧 \[FWT(A)=\begin{cases}(FWT(A_0)+FWT(A_1),FWT(A_0)-FWT(A_1)) & n>0\\A & n=0\end{cases} \] \(FWT(A+B)=FWT(A)+FWT(B)\) 这个显然还是成立的，理由和上面是一样的。 接下来还是证明相同的东西 \(FWT(A)\times FWT(B)=FWT(A\oplus B)\) 证明： \[\begin{aligned} FWT(A\oplus B)=&(FWT(A\oplus B)_0+FWT(A\oplus B)_1,FWT(A\oplus B)_0-FWT(A\oplus B)_1)\\ =&(FWT(A_0\oplus B_0+A_1\oplus B_1+A_1\oplus B_0+A_0\oplus B_1)\\&,FWT(A_0\oplus B_0+A_1\oplus B_1-A_1\oplus B_0-A_0\oplus B_1))\\ =&((FWT(A_0)+FWT(A_1))\times(FWT(B_0)+FWT(B_1))\\ &,(FWT(A_0)-FWT(A_1))\times(FWT(B_0)-FWT(B_1))\\ =&(FWT(A_0+A_1)\times(B_0+B_1),FWT(A_0-A_1)\times FWT(B_0-B_1))\\ =&(FWT(A_0+A_1),FWT(A_0-A_1))\times(FWT(B_0+B_1),FWT(B_0-B_1))\\ =&FWT(A)\times FWT(B) \end{aligned} \]好啦好啦 这样子\(xor\)卷积也证明完啦。 于是我们可以开心的来写\(FWT\)啦 6、IFWT 我们现在可以在\(O(nlogn)\)的时间复杂度里面得到\(FWT(A\oplus B)\)，其中\(\oplus\)表示一个位运算。 得到了\(FWT\)之后我们需要还原这个数组，也就是\(IFWT\)（叫\(UFWT\)也没啥问题？？） 怎么求？ 正向的过程我们知道了，逆向的反着做啊。 所以： \(or\)卷积：$$IFWT(A)=(IFWT(A_0),IFWT(A_1)-IFWT(A_0))$$ \(and\)卷积：$$IFWT(A)=(IFWT(A_0)-IFWT(A_1),IFWT(A_1))$$ \(xor\)卷积：$$IFWT(A)=(\frac{IFWT(A_0)+IFWT(A_1)}{2},\frac{IFWT(A_0)-IFWT(A_1)}{2})$$ 7、代码实现 \(or\)卷积的代码 void FWT(ll *P,int opt) { for(int i=2;i<=N;i<<=1) for(int p=i>>1,j=0;j for(int k=j;k P[k+p]+=P[k]*opt; } \(and\)卷积只需要在\(or\)卷积的基础上修改一点点就好了 void FWT(ll *P,int opt) { for(int i=2;i<=N;i<<=1) for(int p=i>>1,j=0;j for(int k=j;k P[k]+=P[k+p]*opt; } \(xor\)卷积其实也差不多(这个是在模意义下的\(FWT\)) 如果不是在模意义下的话，开一个\(long\ long\)，然后把逆元变成直接除二就好了。 void FWT(int *P,int opt) { for(int i=2;i<=N;i<<=1) for(int p=i>>1,j=0;j for(int k=j;k { int x=P[k],y=P[k+p]; P[k]=(x+y)%MOD;P[k+p]=(x-y+MOD)%MOD; if(opt==-1)P[k]=1ll*P[k]*inv2%MOD,P[k+p]=1ll*P[k+p]*inv2%MOD; } } Upd: 写了个好看点的板子，这样就和\(FFT\)长得很像了。 void FWT_or(int *a,int opt) { for(int i=1;i for(int p=i<<1,j=0;j for(int k=0;k if(opt==1)a[i+j+k]=(a[j+k]+a[i+j+k])%MOD; else a[i+j+k]=(a[i+j+k]+MOD-a[j+k])%MOD; } void FWT_and(int *a,int opt) { for(int i=1;i for(int p=i<<1,j=0;j for(int k=0;k if(opt==1)a[j+k]=(a[j+k]+a[i+j+k])%MOD; else a[j+k]=(a[j+k]+MOD-a[i+j+k])%MOD; } void FWT_xor(int *a,int opt) { for(int i=1;i for(int p=i<<1,j=0;j for(int k=0;k { int X=a[j+k],Y=a[i+j+k]; a[j+k]=(X+Y)%MOD;a[i+j+k]=(X+MOD-Y)%MOD; if(opt==-1)a[j+k]=1ll*a[j+k]*inv2%MOD,a[i+j+k]=1ll*a[i+j+k]*inv2%MOD; } } posted @ 2018-05-21 08:53 小蒟蒻yyb 阅读(23359) 评论(44) 编辑 收藏 举报 会员力量，点亮园子希望 刷新页面返回顶部 公告 Copyright © 2024 小蒟蒻yyb Powered by .NET 8.0 on Kubernetes 野雪界的天花板——FWT自由式滑雪世界巡回赛 - 知乎切换模式写文章登录/注册野雪界的天花板——FWT自由式滑雪世界巡回赛滑雪族Rock'n' Snow自由式滑雪，只能在挤压平整的雪面上，比谁跳着身板直，比谁转圈多吗？野雪，只能在野雪公园刷粉雪，和小伙伴一起滑着爽而已吗？此处注意！敲黑板！！有一个被大家长期忽视的赛事，野雪+自由式+比赛，三者结合，它就是FWT（Freeride World Tour）世界野雪巡回赛。（也有一种叫法是自由式滑雪世界巡回赛~）FWT比赛现场这是滑野雪的顶级赛事，赛道比冬奥会更野性，更凶险，更充满未知数。参赛选手的视角FWT最高级的巡回赛在每年初的1月到3月左右举行，在全世界举办5站。比赛分为四个项目，双板组和单板组的男女比赛。今年因为疫情原因取消了原定前两站日本和加拿大的比赛，只保留了在欧洲的三站比赛。2021年的比赛分别在安道尔2月20号-26号、奥地利3月6号-12号、瑞士3月20号-28号。原定日本白马举办的巡回赛变成了4星级的资格赛，刚刚在上周五（1月15号）举办完成！日本白马站的比赛海报 Freeride Hakuba 2021FWT是什么样的？我们常见的自由式滑雪（freestyle）场地上是人工建设的障碍，例如跳台、轨道、半管；高山滑雪则是在规整的雪道上进行，以速度竞赛为主。平整、规则的雪面、人工设置障碍而FWT赛道是纯天然的。选手要绕开岩石、树木等障碍物，还要从悬崖上飞跃而下。这里没有一套奥运会那样的路线和规则，比拼创意先行、挑战极限，在高山野雪中自由发挥。FWT比赛现场FWT高山自由滑雪场地是随机的自然地形，往往在雪道外、村野的非滑雪场地，甚至会在野外、纯天然的高山野雪等极限地区挑战滑雪。FWT比赛场地Freeride World Tour是很多观众心中滑雪比赛该有的样子——选手们发挥自由式的动作技巧，腾空跳跃，雪花飞扬。回归滑雪本来的面貌，场地景色壮观雄阔，观赏性极强。一面山坡，自由发挥。空翻360意味着跳崖，free是唯一的标准。没有压过的坡面，没有人造的起飞平台，回归原始，只滑自然纯真粉雪。一旦起步，完全用天然地形做动作。野雪往往也就意味着危险。松软的野雪，既代表着原始自由，也代表着未知的风险。为了应对雪崩风险，FWT参赛选手必须佩戴雪崩救援定位系统、雪崩气囊背包、信号收发器等。配齐全部设备后，选手才能参加比赛。FWT比赛上选手摔倒裁判将通过5个因素评判给选手们打分。包括：路线选择、动作流畅性、控制力、滞空和姿态、滑行技巧。飞起来的线路，这个新西兰小哥获得了第二名FWT在全球每年举办一百多场不同级别的野雪比赛。从难到易有不同的等级，最难的、金字塔的最顶端比赛是The Freeride World Tour (FWT)。最高级：世界野雪巡回赛（自由式滑雪世界巡回赛）The Freeride World Tour (FWT)顶级选手的比赛殿堂，全球5站比赛，50多个选手参加，代表了野雪自由式的最高水平。FWT比赛现场第二级：世界野雪资格赛（自由式滑雪资格赛、预选赛）The Freeride World Qualifier (FWQ)野雪选手在世界各地举办的60多次赛事（包括40项欧洲赛事）累积积分，有不同的星级排名（1-4星级），星级越高，含金量越大。第三级：青少年自由式滑雪巡回赛和青少年自由式滑雪世界锦标赛The Freeride Junior Tour (FJT) and Freeride Junior World Championships (FJWC)18岁以下的年轻滑手可以参加，让选手学习伤害预防、安全和了解山区环境，培养未来的顶尖选手。中国有FWT赛事吗？这项世界顶级滑雪赛事在中国似乎不太出名。FWT一年有5次顶级巡回赛，但是20多年以来都在欧美国家举办，直到前几年的才首次来到亚洲日本白马，参赛选手里几乎见不到中国人的身影。既是凶险，也是优美，既是极限，也是惊呼。有着阿勒泰的顶级粉雪，冬奥会的人气加持，FWT巡回赛会不会落地中国？期望中国选手有朝一日也能登上FWT比赛的领奖台！发布于 2021-01-20 14:41滑雪场地滑雪滑雪技术赞同 61 条评论分享喜欢收藏申请 安全访问中心 - 洛谷 即将离开洛谷 你访问的网站可能包含未知的安全风险，如需继续访问，请复制链接访问或点击按钮确认，并注意保护账号和隐私信息。 https://www.luogu.com/article/x3pywq3m 继续访问 安全访问中心 - 洛谷 即将离开洛谷 你访问的网站可能包含未知的安全风险，如需继续访问，请复制链接访问或点击按钮确认，并注意保护账号和隐私信息。 https://www.luogu.com/article/rtcwubuc 继续访问 IOC江原道2024巴黎2024米兰科尔蒂纳2026洛杉矶2028布里斯班2032博物馆商店Olympic Refuge Foundation中文奥运会运动员运动项目新闻Olympic Channel动就一起高山自由滑雪 | 世界巡回赛17 二月 - 2 四月 2023全部重播2023年高山自由滑雪世界巡回赛即将开赛，参加各个项目的运动员将在大批观众的见证下展现高超的技术和惊人的勇气。精彩不要错过！关联Freeride World Tour回放观看全部 集锦01:41:34高山自由滑雪世界巡回赛 | 菲伯尔布伦集锦01:42:20高山自由滑雪世界巡回赛 | 踢马山集锦01:43:37高山自由滑雪世界巡回赛 | 奥尔迪诺阿卡里斯滑雪场专题单板滑雪原创05:19Exclusive马克·麦克莫里斯：在伟大团队的包围之下 | From the Start拥抱奥运。 尽享奥运激情。免费观看体育赛事直播。 尽情观赏系列片。独家奥运新闻和精彩集锦在此注册奥运会巴黎2024结果和奖牌回看和集锦全部奥运会Olympic Channel电视频道直播赛事原创系列企业新闻播客话题探索运动员运动项目Cookie条款Cookie设置隐私条款服务条款著作权 2023 年。保留所
算法笔记｜快速沃尔什变换 FWT（或卷积、与卷积、异或卷积） - 知乎
FWT快速沃尔什变换学习笔记 - 小蒟蒻yyb - 博客园
野雪界的天花板——FWT自由式滑雪世界巡回赛 - 知乎
安全访问中心 - 洛谷
安全访问中心 - 洛谷
2023年FWT高山自由滑雪世界巡回赛
年FWT高山自由滑雪世界巡回赛
版权声明：本文由imtoken2.0官网版发布，如需转载请注明出处。
本文链接：https://www.siyuewuyu.com/article/98.html
