FWT

解决的问题 \(\rm FWT\) 是用来解决位运算卷积的。 啥是位运算卷积呢？ 常见的多项式乘法可以认为是一种加法卷积，即 \(A_{i+j}=\sum B_i \times C_j\)。 位运算卷积就是 \(A_{i \ \text{Or/And/Xor} \ j}=\sum B_i \time ......

思路 若要 \(\oplus\) 卷积 \(a\) 和 \(b\)（此处 \(\oplus\) 可以是任意运算），我们希望存在一个线性变换 \(\mathscr F\)，满足： \[c_k = \sum_{i\oplus j = k} a_ib_j \Longleftrightarrow \math ......

FWT 快速沃尔什变换，用来解决位运算相关的卷积。常见的有与、或、异或三种。 P4717 【模板】快速莫比乌斯/沃尔什变换 (FMT/FWT) 给定长度为 \(2^n\) 两个序列 \(A,B\)，设 \[C_i=\sum_{j\oplus k = i}A_j \times B_k \]分别当 \( ......

\(Fast Fourier Transform(FFT)\) 在 oi 中的主要作用是用来求“卷积”（多项式乘法）。 可将时间复杂度降为 \(O(n \log_2n)\) 3步快速求出多项式乘积： 由系数表示法转换成点值表示法。 求两个多项式的乘积。 将点值表示法转换成系数表示法。 假设A的点值表 ......

仅供学习。 给定长度为 \(2^n\) 两个序列 \(A,B\)，设 \[C_i=\sum_{j\oplus k = i}A_j \times B_k \]分别当 \(\oplus\) 是 or,and,xor 时求出 \(C\) or \[c_{i}=\sum_{j|k\in i} a_{j} b ......

卷积 通用定义： \[\text{令 } F = G\times H \text{ 。} \\ \text{则有 } f_i=\sum\limits_{x=0}^{n-1}\sum\limits_{y=0}^{n-1}g_x h_y [x\oplus y=i] \]若 \(\oplus\) 为 \( ......

cnblogs 你终于不 503 了。充 VIP 能保证不间歇性爆炸吗！ 它们两个的全名叫 快速沃尔什变换(FWT) 和 快速莫比乌斯变换(FMT)，用来在 $O(n\log n)$ 时间复杂度内求位运算卷积。 因为 FMT 能解决的问题是 FWT 的子集，所以这里不讲 FMT，把它拎出来是想说它们 ......

设 $\omega$ 为 $n$ 次单位根。有如下性质： $$ \frac 1n\sum_{k = 0} ^ {n - 1} \omega ^ {vk} = [v \bmod n = 0] $$ 套路大概是看到 $[n | v]$ 这类式子直接化成单位根的形式。 考虑如何计算两个序列的循环卷积： $ ......

title: FWT 做题记录 mathjax: true date: 2022-06-05 16:01:45 tags: - 多项式 feature: false categories: 做题记录 cover: https://pic.imgdb.cn/item/629c9533094754312 ......

title: 关于 FWT 的一些扩展 mathjax: true date: 2022-05-28 18:54:21 tags: - 多项式 feature: false categories: Math cover: https://pic.imgdb.cn/item/6292b34e09475 ......

看见网上题解都是“二维生成函数”，就来传一下这个做法（ 问题可以转化为：$n$ 枚硬币，每次随机翻一枚，求最后正面朝上硬币个数的期望。 把这个过程看作 XOR 卷积，并且需要卷积的两个数组有特性：在 popcount 相同的位置值相同。 这样只要对这种特殊的数组能做 fwt 就做完了。 于是现在要解 ......

其实是一类要按位变换的问题。 不妨假设是二进制的，别的进制类似。 ```cpp void F(int *a){ for (int w=1;(w<<1)<=(1<<k);w<<=1) for (int s=0;s<(1<<k);s+=(w<<1)) for (int t=0;t<w;++t) a[s+ ......

一道挺有意思的题，并且感觉有点诈骗的成分在内（ 首先考虑分析三种字符的性质： 显然任意两点 $i,j$ 之间要么 $i$ 可以到达 $j$，要么 $j$ 可以到达 $i$，否则 A O X 三个一个都不能满足。 如果两点间的状态是 A，那么这两点必须在同一强连通分量内。 如果两点间的状态是 X，那么 ......

打个广告QwQ 对应的FFT洛谷blog链接 对应的csdn博客链接 ~~个人觉得洛谷的观感最好。~~ 不忘历史 八百年前学了 $\text{FFT}$，因vicky过于垃圾，遂放弃。 七百年前重拾 $\text{FFT}$，勉强搞懂了它的递归写法，因vicky再一次懒癌附体，遂连板题都没写就弃疗了 ......

#2023.4.7【模板】快速沃尔什变换FWT 题目概述 给定长度为 $2^n$ 两个序列 $A,B$，设 $C_i=\sum_{j\oplus k = i}A_j \times B_k$ 分别当 $\oplus$ 是 or,and,xor 时求出 $C$ 我们通常将这个操作，叫做“位运算卷积”，因 ......

CF449D Jzzhu and Numbers 简要题意 给定序列 ${a_n}$，求有多少个子序列满足所有元素的按位与为 $0$。 题解 F1 考虑 FWT 的与卷积形式，构造序列 ${A_n}$，使 $A_i=\displaystyle\sum_{j&i=i}a_i$，记 $B_i=\disp ......

FWT 背景 类似与$FFT$,$FWT$是在下标位运算为背景的变换 $FFT$是利用单位根插值作为变换,而$FWT$同样要构造$FWT(A),IFWT(A)$ 当然$FWT(A\times B)=FWT(A)\ op \ FWT(B)$ 或 定义$C=A\times B=\sum\limits_{ ......

来学点好玩的。 引入 我们也许学过，$FFT$ 可以解决一类卷积： $$C_i=\sum^{k+j=i} A_iB_j$$ 现在我们稍微变一下式子： $$C_i=\sum^{i=k \And j} A_kB_j$$ $$C_i=\sum^{i =k\mid j} A_kB_j$$ $$C_i=\su ......