1 条题解

  • 3
    @ 2022-11-24 21:13:12

    简介

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

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

    更形象化地:

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

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

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

    当然,是在模意义下的。

    实现

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

    先想想组合数。根据组合数的定义 (mn)=n!m!(nm)!(nm0)\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} $$

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

    我们只需要预处理出 cc 的幂,然后做卷积,最后乘上 c(2k)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} $$

    注意到此时 iki-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)P(x)Q(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})$。

    注意到 (20)\binom{2}{0}(21)\binom{2}{1} 是不合法的,所以我们只能套公式。

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

    参考资料:

    1. Chirp Z 变换 - OI-Wiki

    信息

    ID
    122
    时间
    1000ms
    内存
    256MiB
    难度
    8
    标签
    (无)
    递交数
    28
    已通过
    6
    上传者