Chirp Z-Transform Chirp Z-Transform
其实不是什么特别难的东西。
用于解决等比数列/类等比数列多点求值。
-
(b_i=sum_{j=0}^{n}a_jc^{ij})
注意到 (ij=inom{i+j}{2}-inom{i}{2}-inom{j}{2})，所以有
[b_i=c^{-inom i 2}sum_{j=0}^{n}a_jc^{-inom j 2}c^{inom {i+j}{2}}
]
容易发现这是一个减法卷积的形式，卷就完事了。
- 循环卷积
你发现 ( exttt{DFT/IDFT}) 和上面那东西长得非常像，所以直接做就完了。
- (b_i=sum_{j=0}^{n}a_jc_i^j,c_0=z,c_i=xc_{i-1}+y(ige 1,x eq 1))
首先当 (y=0) 时你可以解出 (c_i=c_0x^i)。
然后你发现这玩意和上面那东西长得特别像，只要令 (x=c_0x)，就可以直接做。
(y eq0) 时你可以解出它的通项公式。
[c_i=x^i(c_0-frac{y}{1-x})+frac{y}{1-x}
]
然后这个东西你可以通过平移原多项式来做，平移过后就变成了和上面一样的问题了。
平移的话也很简单，只需要利用二项式定理展开一下，你就会发现这是个减法卷积的形式，卷就完事了。
- 质数 (p) 较小时的多点求值
根据原根的定义，(g^0,g^1,cdots,g^{p-2}) 的若干次方可以取遍 ([1,p-1]) 的所有整数。
然后 (f(g^i)=sum_{j=0}^{n}a_jg^{ij}) 显然我们是会求的。
然后就没了。
不是质数的时候可以用中国剩余定理之类的东西合并。