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

引入 我们已经知道了多项式版的二进制 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，考虑矩阵长什么样。 我们可以得到如