位运算卷积学习笔记位运算卷积，即快速沃尔什变换\(\text{FWT}\)和快速莫比乌斯变换\(\text{FMT}\)，但事实上最常用的是\(\text{FWT}\)，因为\(\text{FMT}\)所求解的内容是\(\text{FWT}\)的子集。位运算卷积首先要知道位运算卷积指的是\[c_i=\sum_{j\odotk=i}a_jb_k\]形

异或卷积，把一个三元组\(\{a_i,b_i,c_i\}\)转化为\(F_i[a_i]=x\)，\(F_i[b_i]=y\)，\(F_i[c_i]=z\)的幂级数，将\(\prod\limits_{i=1}^n\text{FWT}(F_i)\)执行\(\text{IFWT}\)即可考虑从每个幂级数只有\(3\)个非零值入手优化，设\(c(i,j)\)表示异或卷积的变换系数，即\(\text{

集合幂级数从\(2^U\rightarrowR\)​的映射加法乘法\(h=f\cdotg=\sum\limits_{L\in2^U}\sum\limits_{R\in2^U}f_Lg_Rx^{L\oplusR}\)类比乘法，其中\(\oplus\)​需要满足交换律，结合律高维前缀和的dp解释设\(f_{S,i}\)表示考虑\(S\)的子集的后\(i\)位，前\(|S|-i

还是记一下这个trick吧，虽然很简单但是我认为十分有趣！本质上是MaximizetheDifference做法的扩展。（似乎有人称作RainFestivalTree？？？）这个题经过一些简单转化可以转化为这样一个问题：给定有二进制数序列\(A,B\)，求\(\max_{r-l\gem}|A_l\oplusB_r|\)（\(|x|\)即二进制位下一的

CF662C首先有一个\(\mathcalO(2^nm)\)的做法。枚举每一行是否反转的状态\(s\)，记\(g_i=\min(\operatorname{popcount}(i),n-\operatorname{popcount}(i))\)，\(t_i\)表示第\(i\)列的状态。则答案为\(\min_s{\sum_{i=1}^mg_{s\operatorname{xor}t_i}}\)。发现这个东西

集合幂级数集合到整数设\(n\)元集\(A=a_1,a_2,\cdots,a_n\)，定义\(A\)的幂集\(2^{A}=\{S\midS\subseteqA\}\)到整数集\(\mathbb{Z}\)的映射\(\text{id}\)为：若\(S=\{a_{i_1},a_{i_2},\cdots,a_{i_k}\}\)，则\(\text{id}(S)=\sum_{j=1}^{k}2^

下文下标一般从\(0\)开始。卷积：记的数组\(a,b\)在运算\(\circ\)下的卷积\(a\circb=c\)，其中\(c_k=\sum\limits_{i\circj=k}a_ib_j\)。直接暴力计算卷积复杂度为\(O(n^2)\)，其中\(n\)为数组长度。DFT-IDFT一般快速计算特殊卷积的方法为构造DFT变换：欲构造可逆的

博客园我的博客快速沃尔什变换解决的卷积问题快速沃尔什变换（FWT）是解决这样一类卷积问题：\[c_i=\sum_{i=j\odotk}a_jb_k\]其中，\(\odot\)是位运算的一种。举个例子，给定数列\(a,b\)，求：\[c_i=\sum_{j\oplusk=i}a_jb_k\]FWT的思想看到FWT的名字，我们可以联想到之前学过

其实就是高维前缀和。FMT和FWT几乎一样，一个是分治一个是DP。FMT：有\(C_i=\sum\limits_{j\oplusk=i}A_jB_k\)，其中\(\oplus\)为与、或。构造\(FMT[S]_i=\sum\limits_{j\oplusi=i}S_j\)，有\(\begin{align*}&FMT[A]_x\timesFMT[B]_x\\&=\sum\limits_{i\oplusx=x}A

日记2024.4.7：子集卷积记号\(F(x)=\sum_{S\subseteq[n]}f_Sx^{S}\)是一个集合幂级数，其中\([n]=\{1,2,\cdots,n\}\)，\(f_S\)是一个数组，然后写成像生成函数（其实是“形式幂级数”）的形式，\(x^S\)的这个指数是没意义的。FWT/FMT即两个集合幂级数的并、交、异或卷积运算。h

上文：FWT快速沃尔什变换概念\(k\)进制的DWT本质上是二进制操作的一个扩展操作。原来的位运算也推广到了\(k\)进制上。\(\text{or}\)卷积定义两个数\(x_{1...k},y_{1...k}\)的\(k\)进制或运算定义为：\(z_i=\max(x_i,y_i)\)。换言之，在每个维度上取\(\max\)。分析

位运算卷积快速求序列\(C\)：\[C_i=\sum_{j\oplusk=i}A_jB_k\]其中\(\oplus=or,and,xor\)。类似FFT的思路，对于序列\(a\)构造新序列\(fmt(a)\)，使得满足\(fmt(a*b)_i=fmt(a)_i\timesfmt(b)_i\)在位运算情况下，\(fmt(a)_i\)均可以表达成关于序列\(a\)的可逆线性变换，即

FWT/快速沃尔什变换前言FWT是处理一类问题形如（\(\oplus\)指or,and,xor二元运算符）\[c_{i}=\sum_{i=j\oplusk}a_{j}b_{k}\]考虑像FFT一样，用\(O(n\logn)\)的复杂度构造出\(fwt\)，在\(O(n)\)计算出\(fwt_a\timesfwt_b\)，最后在\(O(n\logn)\)将\(fwt\)转化回去正题OR考虑构

遗憾的是math里面一直没有很好的讲这个东西……所以这次细致说说。FWT的本质类似于多项式卷积中，利用ntt变换使得卷积\(\to\)点乘，fwt也是类似的应用。定义某种位运算\(\oplus\)，那么fwt处理的位运算卷积形如：\[H=F*G\impliesH_k=\sum_{i\oplusj=k}F_iG_

FWTFWT即位运算卷积，用来快速计算形如\(\sum\limits_{i\oplusj=k}f_ig_j\)，其中\(\oplus\)表示某种位运算。设FWT(A)是幂级数A经过\(\rmFWT\)变换之后得到的幂级数。我们需要令其满足:\(A*B=C\LongleftrightarrowFWT(A)·FWT(B)=FWT(C)\)(点积)。\(\rmFFT\)是

FWT入门题，很适合我这样的蒟蒻。首先我们可以轻松的根据转移条件写出来一个优美的函数\(T(i)=1+\sum_{j\oplusk=i}a_kT(j)\)，边界为\(T(0)=0\)。这个方程属于转移带环的DP，处理方法一般是高斯消元，在这道题里会T飞。但是我们又注意到后边是一个美丽的异或卷积，因此可以考虑用

题目链接题目本质就是对一个多项式\(F\)进行等比数列求和得到\(G\)（\(F_i\)表示\(i\)在序列\(A\)中的出现次数），求\(G\)所有下标\(>0\)的位置的权值和。显然，\(M\)固定就可以直接做了。但\(M\)不固定，所以我们只能暴力枚举\(M\)并进行\(N\)次FWT卷积。复杂度显

洛谷传送门CF传送门UNR#2黎明前的巧克力。枚举两个人选的卡的并集\(S\)，那么当\(\bigoplus\limits_{i\inS}a_i=0\)时\(S\)有贡献\(2^{|S|}\)。考虑将\(2^{|S|}\)分摊到每个元素上，也就是每个元素有\(2\)的贡献，然后把这些贡献乘起来。所以题目其实是想让我们算

解决的问题\(\rmFWT\)是用来解决位运算卷积的。啥是位运算卷积呢？常见的多项式乘法可以认为是一种加法卷积，即\(A_{i+j}=\sumB_i\timesC_j\)。位运算卷积就是\(A_{i\\text{Or/And/Xor}\j}=\sumB_i\timesC_j\)。主要思想现在以异或卷积为例，默认\(n=2^k\)。回忆

首先，任何一个卡树剖的出题人都很没有素质前言2023年8月22日，XDFnoip模拟赛场上，神犇liuhangxin自己发明了矩阵乘法维护FWT，可是出成绩的时候发现本题挂了30分。2023年9月22日，菜鸡cool_milo看到了liuhangxin的题解，但是由于太菜，并没有看懂。2023年10月22日，菜

0.前情提要别想翻盘了，赶紧搞你那whk去吧。学点期望概率以后用。1.一些需要知道的有关概率约定\(P(A)\)为\(A\)事件发生的概率。条件概率\(P(A|B)\)表示，在\(B\)已经发生的情况下，\(A\)事件发生的概率。由条件概率的定义，可以得到算式：\[P(A|B)=\frac{P(A\capB)

前置知识：FWT的另一种理解FWT的另一种理解，文中使用的系数矩阵\(F\)似乎不太标准，本文中认为\(\mathscr{F}(\bma)=F\times\bma\)。摘要：FWT使用的线性变换的系数矩阵\(F\)需要满足\(F(i,x\oplusy)=F(i,x)\timesF(i,y)\)。同或卷积因为同或运算在每一位上是独立的，所以

思路若要\(\oplus\)卷积\(a\)和\(b\)（此处\(\oplus\)可以是任意运算），我们希望存在一个线性变换\(\mathscrF\)，满足：\[c_k=\sum_{i\oplusj=k}a_ib_j\Longleftrightarrow\mathscrF(a)\cdot\mathscrF(b)=\mathscrF(c)\]若求\(\mathscrF(x)\)和\(\maths

这说明你那破子集卷积不是万能的。显然题目要求的图\(G'\)是弱联通的，考虑给出的图\(G\)中两个点\(i,j\)之间\(G_{i,j}\)的条件转化为：\(G_{i,j}=\mathttA\)，说明\(i\)能到\(j\)且\(j\)能到\(i\)，则\(i,j\)在\(G'\)的同一个强连通分量中。\(G_{i,j}=\mathttO

仅供学习。给定长度为\(2^n\)两个序列\(A,B\)，设\[C_i=\sum_{j\oplusk=i}A_j\timesB_k\]分别当\(\oplus\)是or,and,xor时求出\(C\)or\[c_{i}=\sum_{j|k\ini}a_{j}b_{k}\]定义\(fwt[a]_i=\sum_{j\ini}a_j\)显然$$\begin{aligned}fwt[a]\timesf