群
群 = 一个集合 + 一个"合并运算" ⊕,满足四条规矩。 你可以把它理解成"一种可以反悔(有逆元)的合并方式"。
设集合 G,运算 ⊕,要求:
① 封闭性:a ⊕ b 还得在 G 里。
整数 + 整数 = 整数 ✓
② 结合律:(a⊕b)⊕c = a⊕(b⊕c)。
(1+2)+3 = 1+(2+3)✓
③ 单位元:存在一个 e,使 e ⊕ a = a ⊕ e = a 对所有 a 成立。
加法的单位元是
0:0 + a = a✓
④ 逆元:每个 a 都有一个 a⁻¹,使 a ⊕ a⁻¹ = e。
加法下
a的逆元是−a:a + (−a) = 0✓
四条全满足 → 整数配上加法,是一个群,记 (ℤ, +)。
卷积
f, g : G → R 是 G 上的函数(系数取实数/复数/整数都行)。卷积 f * g 定义为:
任何有限交换群上的卷积,都能被该群的"傅里叶变换"对角化(即卷积 ↔ 变换域逐点乘)
有限:元素个数有限
交换:a opt b = b opt a 对所有 a, b 成立。
ℕ | 自然数 | 0, 1, 2, ... |
| ℤ | 整数 | ..., −2, −1, 0, 1, 2, ... |
| ℚ | 有理数 | 分数 |
| ℝ | 实数 | 所有实数(含小数、无理数) |
| ℂ | 复数 | a + bi
对角化 变成对角矩阵
换基(向量换基/矩阵换基)
FWT 本质 = 通过换基(H),把 XOR 卷积矩阵对角化,使其作用从"混合 O(N²)“变成"逐点 O(N)";于是单次卷积变快,而堆叠同一卷积 m 次更是塌缩成"一次变换 + 逐点 m 次方 + 一次逆变换”
“群 → 卷积 → 对角化定理 → 换基 → 蝴蝶快速算 → 幂运算塌缩”,
原来是标准基 对角线全1
要换的基是哈达玛基矩阵
fft
fwt
fwt能解决什么问题
fwt的流程
f_i^f_j 这个卷积可以通过H(f)加速
也就是f_i^f_j =H(f opt f)= H(f) * H(f)
以leetcode 3514为例
题意,给定一个数组num,求num[i] ^ num[j] ^ num[k] 的 值的种类数(不同的异或结果的个数)
1 <= nums.length <= 1500 1 <= nums[i] <= 1500
定义f[x]=1 存在异或结果为x,为0则不存在
只要求出f[],统计f[]中值为1的个数即可
一开始,f[i]表示num中是否存在i
- 把n round up 为 2的幂次(为什么在后面讲)
N=2048
- 对f[]进行fwt变换
对相距len的元素进行变换,len=1,2,4,..2^i (i<=log2(N))
把num分成长度为2*len的若干段,每段对相距len的元素进行变换 $f_i,f_{i+len}=(f_i+f_{i+len},f_i-f_{i+len})$
for (len = 1; len < N; len <<= 1) // len = 1, 2, 4, ...
for (i = 0; i < N; i += len << 1) // 每块大小 2*len
for (j = i; j < i + len; j++) // 块内前半段每个 j
配对 ( f[j], f[j+len] ) → ( f[j]+f[j+len], f[j]-f[j+len] )
3.逐点平方3次
f[i]=f[i]^3(为什么是3次方下面解释)
4.再重复一次步骤2,然后每个元素/N
≥ 所有可能的 XOR 输出值(这一条你说对了——保证结果不越界); 必须是 2 的幂(这一条漏了,而且更硬)。
fwt的原理
延伸一下:如果某题的值域是 10⁹ 这种,但值只有几个,你还会傻乎乎开 N = 2³⁰ 吗?——那是另一个经典处理方式(离散化 + 别的思路),FWT 在值域大但值稀疏时反而不如直接 O(n²)。想想为什么,这能帮你判断"什么时候该上 FWT,什么时候不该"