关于此视频的一些练习题:(网页链接)

先说核心公式,一切推导都从这一行开始:
对 次本原单位根 ,指示函数有展开:
[n∣k]=1n∑j=0n−1ωjk[n∣k]=n1j=0∑n−1ωjk
是 的倍数时右边等于 1,否则等于 0。这就是"条件函数的傅里叶展开",整个 root of unity filter 全是它的应用。
右边是一个几何级数,公比是 :
∑j=0n−1(ωk)j={n,ωk=11−ωkn1−ωk=0,ωk≠1j=0∑n−1(ωk)j=⎩⎨⎧n,1−ωk1−ωkn=0,ωk=1ωk=1
分两种情况看:
证完,就这么短。本质是"把所有 次单位根的幂平均一下,只有周期对得上的时候才不被抵消"。
上面看着像技巧,其实它就是 上的离散傅里叶变换(DFT),跟信号处理里那套是同一个东西。
取函数 。 个特征(character) 构成一组正交基,正交性就是刚才那个等比求和:
1n∑k=0n−1ωjk⋅ωj′k‾=[j=j′]n1k=0∑n−1ωjk⋅ωj′k=[j=j′]
任何函数都能展开成"傅里叶级数":
f(k)=∑j=0n−1f^(j) ωjk,f^(j)=1n∑k=0n−1f(k) ω−jkf(k)=j=0∑n−1f^(j)ωjk,f^(j)=n1k=0∑n−1f(k)ω−jk
而" 的指示函数"就是 (只在 0 处取 1 的函数)。代入算系数:,对所有 都一样。所以
δ0(k)=1n∑j=0n−1ωjkδ0(k)=n1j=0∑n−1ωjk
和第一节完全吻合。单位根滤波 = 循环群上的傅里叶反演,没有新东西,只是换了个说法。
组合计数里最常见的困境:求"满足 的方案数",直接枚举是指数级的。滤波的做法是把条件函数塞进生成函数的求值里。
通用套路: 设 是普通生成函数, 里编码了"和为 "的方案数。那么
1n∑j=0n−1F(ωj)=1n∑j∑kck ωjk=∑kck [n∣k]n1j=0∑n−1F(ωj)=n1j∑k∑ckωjk=k∑ck[n∣k]
中间那步就是交换求和顺序然后用第一节的核心恒等式。一次滤波 = 对生成函数在所有 nn 次单位根处取值再平均,剩下的恰好是下标被 nn 整除的那些系数之和。
求 。
生成函数是 ,但这次要选余数 不是 0,得加权转一下:
∑k≡r(Nk)=1n∑j=0n−1ω−jr(1+ωj)Nk≡r∑(kN)=n1j=0∑n−1ω−jr(1+ωj)N
多出来的 是为了让 的项在求和时幸存、其他项抵消——把 展开自行验证即可。
最熟的一个特例,n=2n=2,r=0r=0: ,
∑k 偶(Nk)=(1+1)N+(1−1)N2=2N−1k 偶∑(kN)=2(1+1)N+(1−1)N=2N−1
奇偶各一半,这就是"偶数项二项式系数之和等于 "的滤波证明,两行搞定。
再算一个 n=3n=3 的,r=0r=0: ,注意 ,所以 ,,两者共轭:
∑k≡0(mod3)(Nk)=13(2N+2cosNπ3)k≡0(mod3)∑(kN)=31(2N+2cos3Nπ)
比如 :。手算验证: 中 是 1+10 = 11。✓
问题: 从 里任选子集,和能被 3 整除的有几个?
生成函数 。
滤波:。
手数一遍:、、、,正好 4 个。✓
注意这个例子里 和 共轭不是巧合——只要原问题是实数计数,单位根取值必然共轭成对,实际只需要算一半的根,这也是工程实现里省一半工作量的常用优化。
1. 模运算环境下没有 CC。 竞赛或算法实现里经常要在 意义下做滤波,此时 次本原单位根存在于 当且仅当 (乘法群是循环群)。不满足就得扩域 ,或者干脆在 里用浮点算再四舍五入(数值小的时候可行)。
2. 权重方向别搞反。 和 ,正变换和逆变换差一个符号加一个 ,用错了筛选出来的余数类会镜像( 变成 )。写代码时拿 的小例子先对拍。
3. 多重条件的叠加。 要同时满足 且 ,等价于 ,用 6 次单位根一次搞定;也可以两次滤波相乘,结果一样,但计算量是 次取值对 次取值,看哪边生成函数好算。
4. 生成函数次数超过周期时。 滤波筛掉的是"下标 "的信息,剩下的和是所有同余类系数的总和,不会丢失——但如果你还想知道各个余数类分别多少个,那就是完整 DFT: 取所有 ,再逆变换回来。
一句话总结:root of unity filter 就是 Z/nZZ/nZ 上的傅里叶分析,核心恒等式 1n∑ωjk=[n∣k]n1∑ωjk=[n∣k] 是正交性的直接推论,用法是把整除条件翻译成"在所有单位根处求值取平均",剩下的就是生成函数的代数操作。 遇到"和被 整除的方案数"这类题,先写生成函数,再套这个壳,基本都不会错。
免责声明:本文系网络转载或改编,未找到原创作者,版权归原作者所有。如涉及版权,请联系删