快速沃尔什变换模板题给定长度为\(2^n\)两个序列\(A,B\)，设\[C_i=\sum_{j\oplusk=i}A_j\timesB_k\]分别当\(\oplus\)是or,and,xor时求出\(C\)。FWT，中文名称：快速沃尔什变换。因为已经有FFT和NTT基础，所以直接考虑构造FWT的变换。不失一般性，先考虑\(n=

SS241106C.此时此刻的光辉题意给你\(n\)个点，每个点需要被染成\(0/1/2\)三种颜色之一，有\(m\)种限制，每个限制形如【\(u\)不是颜色\(x\)or\(v\)不是颜色\(y\)】，问你满足限制的涂色方案数。思路拜谢dxw。题解提到了FWT是什么东西，好吓人啊。这里是题解的做法一

快速沃尔什变换（FWT）前言本文为个人学习笔记，大量参考了oi-wiki以及其他博客的内容。问题给定\(a,b\)序列，求：\[c_i=\sum_{i=j\oplusk}a_jb_k\]其中，\(\oplus=\operatorname{or}/\operatorname{and}/\operatorname{xor}\)。做法核心思想对于某种特定的\(\o

2024.11做题笔记其实是CSP后到NOIP前的部分10.28怎么KTSC这么困难啊……B.P11237「KTSC2024R1」警察与小偷把警察、小偷所在路径拎出来，此时警察一定往小偷所在方向走，而小偷可以在警察到路径上的某点之前从这点走向路径外，想选尽量长的路径，让警察走的尽量多但可能

RT，主要内容涉及有高维前缀和（子集DP），高维后缀和，高维差分，快速沃尔什变换，子集卷积。参考资料：link1link2知识点合集高维前缀和用于求解\(f(S)=\sum_{T\subseteqS}g(T)\)。for(inti=0;i<(1<<n);i++)f[i]=g[i];for(intj=0;j<n;j++){for(inti=0;i<(1<<n)

\(3^n\)枚举子集状压DP中相当重要的技巧（虽然后位有FWT，FMT替代，但不是都能代）for(inti=x;i;i=(i-1)&x){//i就是x的子集}题目P6622[省选联考2020A/B卷]信号传递看数据范围，\(m\le23\)，且不同分数段增长很慢，表明会有\(O(2^m)\)的做法，考虑状压或搜索剪枝

B维护长度为二的次幂的数组，支持单点修改，区间和，全局执行以下三种操作之一：for(inti=0;i<n;i++)b[i]=0;for(inti=0;i<n;i++)b[i()x]+=a[i];for(inti=0;i<n;i++)a[i]=b[i];（）里为或，且，异或中的一种。\(n\le2^{19}\)。考虑线段树维护。注意到如果为或/且，那么相当于对

Xor-FWT的另一种理解方式学习\(\text{Fennec'sAlgorithm}\)的额外收获，顺手记录一下。假设我们要求两个长度为\(n\)的数组的异或卷积，为方便起见令\(n=2^m\)，也就是类似下面的形式\[C_k=\sum\limits_{i\oplusj}A_i\timesB_j\]考虑构造\(\mathbb{Z}_2^n\)中的向

概览将对数列的讨论带到了二进制上，用于解决跟操作二进制位的符号有关的题目如\[\sum_{i|j=k}a[i]·b[j]\]FFT的大概流程是将多项式化为点值表达式，然后通过点值表达式\(O(n)\)复杂度的合并降低复杂度上限，最后将点值表达式化回多项式第一步和第三步的复杂度是\(O(n\logn)\)的，

DescriptionSK酱送给你了一份生日礼物。礼物是\(n\)个三元组\((a_i,b_i,c_i)\)和四个正整数\(x,y,z,k\)。你利用这\(n\)个三元组填充了\(n\)个数组，其中第\(i\)个数组中有\(x\)个\(a_i\)，\(y\)个\(b_i\)，\(z\)个\(c_i\)（所以第\(i\)个数组长度为\((x+y+z)\)。

282.CF2001D贪心做不明白了。按照字典序贪心。比如说奇数位，让颜色最大。有一种说法是选择一个最大的颜色填入，使得填入后剩余颜色都可填入。形式些表述，我们已经构造了\(b_1,b_2,\cdots,b_j\)，其中\(b_j=a_i\)，设\(l_x\)是颜色\(x\)出现在\(a[i+1,n]\)的最后一个位置，那

MyBlogs[ABC367G]Sumof(XOR^Kor0)考虑求出\(ans_i\)表示选了\(m\)的倍数个数，异或和是\(i\)的方案数再统计答案。先考虑\(m=1\)怎么做。相当于是\(ans_i=[x^i]\prod_j(x^0+x^{a_j})\)，这里的乘法是异或卷积。如果直接xor-FWT复杂度不如暴力。令\(F_i(x)\)表

关于fwt的直接计算式：or：\(fwt(a)_i=\sum_{j\subseteqi}a_j\)and：\(fwt(a)_i=\sum_{i\subseteqj}a_j\)xor：\(fwt(a)_i=\sum_{j}(-1)^{|i\capj|}a_j\)关于ifwt的直接计算式：or和xor就是子集反演（容斥）xor发现就是每次都会多乘一个\(\frac{1}{2}\)：\(ifwt(a)_i=\frac{

快速莫比乌斯/沃尔什变换(FMT/FWT)这个东西是用来求二进制位运算的卷积的，\(or\)卷积、\(and\)卷积、\(xor\)卷积。引入我们要求的是：\[C[i]=\sum_{i=j\oplusk}A[j]*B[k]\]考虑像FFT一样，先将一个式子计算出它的正变换后的式子，再相乘，最后做一次逆变换。于是我们先定义一个

ABC367G神奇题目场上想到了引入多元生成函数之后就嗝屁了。定义两个多项式的运算\(A(z)*B(z)=\sum_{i}\sum_{j}z^{i\oplusj}a_ib_j\)，也就是异或卷积。定义两个二元生成函数\(A(x,y)*B(x,y)=\sum_{i,p}\sum_{j,q}x^{i\oplusj}y^{p+q}a_{i,p}b_{j,q}\)我们仍然选用\(\prod

QOJ8047DFSOrder4先考虑如何判断一个一个\(p\)的合法性。如果\(p_{i-1}<p_i\)，把\(p_i\)挂到\(p_{i-1}\)下方；否则在\(p_{i-1}\)的祖先集合中取一个点\(u\)满足\(u<p_i\)且\(u\)最深，把\(p_i\)挂到\(u\)父亲下面。现在连出来的树，不仅儿子递增，而且对于第\(i

位运算卷积学习笔记位运算卷积，即快速沃尔什变换\(\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