目录 前言符号约定或运算FWT 变换逆变换代码实现 与运算FWT变换和逆变换代码实现 异或运算FWT变换逆变换 另一个角度的 FWT异或运算代码实现 同或运算FWT变换和逆变换 FWT 是线性变换例题[例题1：洛谷P4717 【模板】快速莫比乌斯/沃尔什变换 (FMT/FWT)](https://www.luogu.com.cn/problem/P4717)例题2：BZOJ4589 Hard

参考博客 https://www.cnblogs.com/Mychael/p/9255572.html https://www.cnblogs.com/cjyyb/p/9065611.html 题意：给定一棵无根树，统计所有子树的异或和的个数。 dp[u][i],表示u为根的数，xor值得到i的方案数 显然，每次合并就是两个dp    dp值做xor   xor卷积 利用FWT优化异或

题意 题解 从大到小枚举\(l\), 把一个序列从\(2^{l+1}\)分成两个独立的\(2^l\)，去除两半的影响。 设去除前的序列为\(b\), 去除后序列为\(b'\) 则有\(b_{2^{l+1}-1}-b_{2^l-1}=\sum^{2^{l+1}-1}_{i=2^l}b_i\) 考虑左边的一个位置\(d\)与右边的位置\(d+2^l\)相对应 考虑一个序列\(s_0\)的第\(i

题目链接 https://atcoder.jp/contests/agc034/tasks/agc034_f 题解 无论多水的题我都不会啊.jpg 首先考虑一个图上随机游走的经典问题，无向图求从\(0\)号点出发随机游走到每个点的期望时间。做法是显然答案等于从每个点走到\(0\)号点的期望时间，然后列方程高斯消元。 设答案向量为\(\textbf{x}\), 则有\(x_i=\sum_{j\ \

题目链接：http://codeforces.com/contest/662/problem/C 首先将矩阵按列压成二进制，G[i]表示某一列为状态i时最小的1的数目，cnt[i]表示状态i时1的个数，按行枚举翻转状态j，则在状态i下，1的最小的数目为sigma(cnt[i]*G[i^j])，因为i^(i^j)=j，所以可以看作一个异或卷积的形式，采用fwt进行加速即可。 代码：

https://vj.imken.moe/contest/597216#problem/F 考虑两个人的集合分别为 i , j i,j i,j，那么我们令 f ( i ⊗ j ) + + f(i\otimes j)++ f(i⊗j)++，其中 f ( s ) f(s) f(s) 表示两个人不同集合恰好为 s s s，显然 f ( s ) f(s) f(s) 可以FWT求。 假设 g

Description 传送门 题解 看懂题需要一会… 朴素的dp就可以列出一个方程 f [ m a s k ] = 1 r [ i ] p ∑ j ∣ k = m a s k f [ j ] ∗ r [ k ] p f[mask]=\frac{1}{r[i]^p}\sum_{j|k=mask} f[j]*r[k]^p f[mask]=r[i]p1​j∣k=mask∑​f[j]∗r

引入 我们已经知道了多项式版的二进制 FWT，但是我们似乎不是很好将其扩展到 k k k 进制下，于是我们来考虑另一种方式的 FWT。 原理 二进制 规定三个多项式的长度为 2 n 2^n 2n，如果不够则往后面补 0 0 0。 还是先考虑二进制，我们假设存在矩阵使得 T A ∗ T B = T C TA * TB = TC TA∗TB=TC，考虑矩阵长什么样。 我们可以得到如