简介

Chirp Z 变换，又称 Bluestein 算法，是任意长度的卷积。

这个算法可以在 $O(n\log n)$ 的时间复杂度内求解等比数列点值。

更形象化地：

给定三个整数 $n,m,c$，以及一个多项式 $A(x)$。

这个算法可以在 $O((n+m)\log (n+m))$ 的时间复杂度内求出

$$A(1),A(c),A(c^2),\cdots,A(c^{m-1})$$

当然，是在模意义下的。

实现

我们有几种实现方式。讲讲最主流的方式：

先想想组合数。根据组合数的定义 $\binom{m}{n}=\frac{n!}{m!(n-m)!}(n\geq m\geq 0)$，我们可以得到

$$\binom{2}{n}=\dfrac{n!}{2!(n-2)!}=\dfrac{n(n-1)}{2} $$

这里即便除以零也没事，因为如同分式方程，没有必要在中途检验。

首先是这个式子

$$\begin{aligned} xy&=\dfrac{x^2+y^2+2xy-x^2-y^2}{2}\\ &=\dfrac{x^2+y^2+2xy-x-y-x^2-y^2+x+y}{2}\\ &=\dfrac{x^2+y^2+2xy-x-y}{2}-\dfrac{x^2-x}{2}-\dfrac{y^2-y}{2}\\ &=\binom{2}{x+y}-\binom{2}{x}-\binom{2}{y} \end{aligned} $$

然后我们将要求的东西代入函数里

$$\begin{aligned} A(c^{k})&=\sum_{i=0}^{\deg A}c^{ik}A\lbrack i\rbrack\\ &=\sum_{i=0}^{\deg A}c^{\binom{2}{i+k}-\binom{2}{i}-\binom{2}{k}}A\lbrack i\rbrack\\ &=c^{-\binom{2}{k}}\sum_{i=0}^{\deg A}c^{\binom{2}{i+k}-\binom{2}{i}}A\lbrack i\rbrack \end{aligned} $$

这已经明摆着的是一个卷积的形式了。

我们只需要预处理出 $c$ 的幂，然后做卷积，最后乘上 $c^{-\binom{2}{k}}$ 就可以了。

---

但是显然这甚至没有直接计算快。我们试着加速。

设

$$\begin{aligned} P(x)&=\sum_{i=0}^{\deg A}A\lbrack \deg A-i\rbrack c^{-\binom{2}{\deg A-i}}x^i\\ Q(x)&=\sum_{i=0}^{\deg A}c^{\binom{2}{i}}x^i \end{aligned} $$

于是我们有

$$\begin{aligned} P(x)\lbrack i\rbrack&=A\lbrack \deg A-i\rbrack c^{-\binom{2}{\deg A-i}}\\ Q(x)\lbrack i\rbrack&=c^{\binom{2}{i}} \end{aligned} $$

再推一波式子。

$$\begin{aligned} (P(x)Q(x))\lbrack\deg A+k\rbrack&=\sum_{i=0}^{\deg A+k}(P(x)\lbrack \deg A+k-i\rbrack\times Q(x)\lbrack i\rbrack)\\ &=\sum_{i=0}^{\deg A+k}(A\lbrack{\color{red}i-k}\rbrack\times c^{-\binom{2}{\color{red}i-k}}\times c^\binom{2}{i}) \end{aligned} $$

注意到此时 $i-k$ 可能小于零。于是我们设 $\forall i\not\in\lbrack0,\deg A\rbrack,A\lbrack i\rbrack=0$。

在这一步中计算组合数发生除以零是没事的，因为如同分式方程，没有必要在中途检验。

$$\begin{aligned} (P(x)Q(x))\lbrack\deg A+k\rbrack&=\sum_{i=0}^{\deg A+k}(A\lbrack i-k\rbrack\times c^{-\binom{2}{i-k}}\times c^\binom{2}{i})\\ &=\sum_{i=-k}^{\deg A}(A\lbrack i\rbrack\times c^{\binom{2}{i+k}-\binom{2}{i}})\\ &=\sum_{i=0}^{\deg A}(A\lbrack i\rbrack\times c^{\binom{2}{i+k}-\binom{2}{i}})\\ &=c^{\binom{2}{k}}\times A(c^k) \end{aligned} $$

于是我们对 $P(x)$ 和 $Q(x)$ 做卷积，可以得到 $c^{\binom{2}{0}}\times A(c^0),c^{\binom{2}{1}}\times A(c^1),\cdots,c^{\binom{2}{m-1}}\times A(c^{m-1})$。

注意到 $\binom{2}{0}$ 和 $\binom{2}{1}$ 是不合法的，所以我们只能套公式。

由于得到的结果是 $m$ 项的，所以我们要做的卷积长度为 $\deg A+m$（精确来说应该是 $2^{\lceil\log(\deg A+m)\rceil}$）。

参考资料：

1. Chirp Z 变换 - OI-Wiki