许可优化
许可优化
产品
产品
解决方案
解决方案
服务支持
服务支持
关于
关于
软件库
当前位置:服务支持 >  软件文章 >  把条件函数按傅里叶展开,root of unity filter推导

把条件函数按傅里叶展开,root of unity filter推导

阅读数 12
点赞 0
article_banner


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

单位根滤波:把"整除条件"拆成傅里叶级数

先说核心公式,一切推导都从这一行开始:

对  次本原单位根 ,指示函数有展开:

[n∣k]=1n∑j=0n−1ωjk[n∣k]=n1​j=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​

分两种情况看:

  • n∣kn∣k:……直接算,,所以 ,公比是 1,求和就是  项 1 相加,得 。除以  得 1。
  • n∤kn∤k: 但 ,也就是说  是一个不是 1 的  次单位根。分子 ,分母非零,整个分式为 0。除以  还是 0。

证完,就这么短。本质是"把所有  次单位根的幂平均一下,只有周期对得上的时候才不被抵消"。

二、换个视角:循环群上的傅里叶级数

上面看着像技巧,其实它就是  上的离散傅里叶变换(DFT),跟信号处理里那套是同一个东西。

取函数 。 个特征(character) 构成一组正交基,正交性就是刚才那个等比求和:

1n∑k=0n−1ωjk⋅ωj′k‾=[j=j′]n1​k=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−1​f^​(j)ωjk,f^​(j)=n1​k=0∑n−1​f(k)ω−jk

而" 的指示函数"就是 (只在 0 处取 1 的函数)。代入算系数:,对所有  都一样。所以

δ0(k)=1n∑j=0n−1ωjkδ0​(k)=n1​j=0∑n−1​ωjk

和第一节完全吻合。单位根滤波 = 循环群上的傅里叶反演,没有新东西,只是换了个说法。

三、它到底用来干嘛:整除计数

组合计数里最常见的困境:求"满足  的方案数",直接枚举是指数级的。滤波的做法是把条件函数塞进生成函数的求值里。

通用套路: 设  是普通生成函数, 里编码了"和为 "的方案数。那么

1n∑j=0n−1F(ωj)=1n∑j∑kck ωjk=∑kck [n∣k]n1​j=0∑n−1​F(ωj)=n1​j∑​k∑​ck​ωjk=k∑​ck​[n∣k]

中间那步就是交换求和顺序然后用第一节的核心恒等式。一次滤波 = 对生成函数在所有 nn 次单位根处取值再平均,剩下的恰好是下标被 nn 整除的那些系数之和。

四、经典应用:二项式系数按余数分类

求 。

生成函数是 ,但这次要选余数  不是 0,得加权转一下:

∑k≡r(Nk)=1n∑j=0n−1ω−jr(1+ωj)Nk≡r∑​(kN​)=n1​j=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+2cos⁡Nπ3)k≡0(mod3)∑​(kN​)=31​(2N+2cos3Nπ​)

比如 :。手算验证: 中  是 1+10 = 11。✓

五、完整走一个例子:小规模验证

问题: 从  里任选子集,和能被 3 整除的有几个?

生成函数 。

滤波:。

  • (全部子集)
  • :,且 ,所以
  • 同理 ( 与  共轭,系数是实数时取值共轭)
  • 8+2+23=438+2+2​=4

手数一遍:、、、,正好 4 个。✓

注意这个例子里  和  共轭不是巧合——只要原问题是实数计数,单位根取值必然共轭成对,实际只需要算一半的根,这也是工程实现里省一半工作量的常用优化。

六、几个容易卡住的点

1. 模运算环境下没有 CC。 竞赛或算法实现里经常要在  意义下做滤波,此时  次本原单位根存在于  当且仅当 (乘法群是循环群)。不满足就得扩域 ,或者干脆在  里用浮点算再四舍五入(数值小的时候可行)。

2. 权重方向别搞反。  和 ,正变换和逆变换差一个符号加一个 ,用错了筛选出来的余数类会镜像( 变成 )。写代码时拿  的小例子先对拍。

3. 多重条件的叠加。 要同时满足  且 ,等价于 ,用 6 次单位根一次搞定;也可以两次滤波相乘,结果一样,但计算量是  次取值对  次取值,看哪边生成函数好算。

4. 生成函数次数超过周期时。 滤波筛掉的是"下标 "的信息,剩下的和是所有同余类系数的总和,不会丢失——但如果你还想知道各个余数类分别多少个,那就是完整 DFT: 取所有 ,再逆变换回来。

一句话总结:root of unity filter 就是 Z/nZZ/nZ 上的傅里叶分析,核心恒等式 1n∑ωjk=[n∣k]n1​∑ωjk=[n∣k] 是正交性的直接推论,用法是把整除条件翻译成"在所有单位根处求值取平均",剩下的就是生成函数的代数操作。 遇到"和被  整除的方案数"这类题,先写生成函数,再套这个壳,基本都不会错。


免责声明:本文系网络转载或改编,未找到原创作者,版权归原作者所有。如涉及版权,请联系删

相关文章
技术文档
QR Code
微信扫一扫,欢迎咨询~
customer

online

联系我们
武汉格发信息技术有限公司
湖北省武汉市经开区科技园西路6号103孵化器
电话:155-2731-8020 座机:027-59821821
邮件:tanzw@gofarlic.com
Copyright © 2023 Gofarsoft Co.,Ltd. 保留所有权利
遇到许可问题?该如何解决!?
评估许可证实际采购量? 
不清楚软件许可证使用数据? 
收到软件厂商律师函!?  
想要少购买点许可证,节省费用? 
收到软件厂商侵权通告!?  
有正版license,但许可证不够用,需要新购? 
联系方式 board-phone 155-2731-8020
close1
预留信息,一起解决您的问题
* 姓名:
* 手机:

* 公司名称:

姓名不为空

姓名不为空

姓名不为空
手机不正确

手机不正确

手机不正确
公司不为空

公司不为空

公司不为空