题解：P14993 【模板】Inverse Chirp Z-Transform

bcdmwSjy · 2026-01-25 11:59:04 · 题解

首先，我们先来复习一下 Chirp Z-Transform，这个算法可以快速求出一个多项式在等比数列处的点值，形式化的，给定 n 项的多项式 f 和公比 c，你需要求出 f(1),f(c),f(c^2),\cdots,f(c^{m-1})。

我们发现答案 g 可以表示为 g_i=\sum\limits_{j=0}^{n-1} f_jc^{ij}，然后我们把 ij 拆为 \binom{i+j}2-\binom i2-\binom j2，代入后得到 g_i=c^{-\binom i2}\sum\limits_{j=0}^{n-1}f_jc^{-\binom j2}c^{\binom{i+j}2}，我们发现这很像一个卷积的形式。

设 p_i=f_ic^{-\binom i2},q_{n-1+m-1-i}=c^{-\binom i2}，则上述式子可以改写为 g_i=c^{-\binom i2}\sum\limits_{j=0}^{n-1}p_jq_{n-1-m-1-i-j}，此时可以直接利用一次卷积完成。

Poly ChirpZ(const Poly &p,int c,int m){
    int n=p.n;
    Poly f(p),g,ans;
    f.resize(n+m-1);
    g.resize(n+m-1);
    ans.resize(n+m-1);
    for (int i=0;i<n+m-1;i++){
        ans[n-1+m-1-i]=qpow(c,((ll(i-1)*i)>>1)%(mod-1));
        g[i]=f[i]*qpow(c,mod-1-((ll(i-1)*i)>>1)%(mod-1))%mod;
    }
    f=ans*g;
    for (int i=0;i<m;i++) ans[i]=f[n-1+m-1-i]*qpow(c,mod-1-((ll(i-1)*i)>>1)%(mod-1))%mod;
    ans.resize(m);
    ans.n=m;
    return ans;
}

接下来我们考虑逆 Chirp Z-Transform，我们发现这实际上是一个插值的过程，所以我们先拿出拉格朗日插值公式 f(x)=\sum\limits_{i=0}^{n-1}y_i\prod\limits_{j\neq i}\frac{x-x_j}{x_i-x_j}。

设 M_n(x)=\prod\limits_{i=0}^{n-1}(x-x_i)，则 \prod\limits_{j\neq i}(x_i-x_j)=\lim\limits_{x\to x_i}\dfrac{\prod\limits_{i=0}^{n-1}(x-x_i)}{x-x_i}，由洛必达法则得其为 M_n'(x_i)。

基于此，我们可以把拉格朗日插值式改写为 \sum\limits_{i=0}^{n-1}\dfrac{y_i}{M_n'(x_i)}\prod\limits_{j\neq i}(x-x_j)=M_n(x)\sum\limits_{i=0}^{n-1}\dfrac{y_i}{M_n'(x_i)(x-x_i)}。

我们先考虑在首项为 1 的等比数列上的插值，此时 x_i=c^i,M_n(x)=\prod\limits_{i=0}^{n-1}(x-c^i)，直接分治计算的时间复杂度是 O(n\log^2n) 的，我们考虑能否优化。

设 n 是偶数，我们尝试找到 M_n(x) 和 M_\frac n2(x) 之间的关系（这个思想在求斯特林数时也用到过），我们把乘积拆成前后两部分，M_n(x)=\prod\limits_{i=0}^{\frac n2-1}(x-c^i)\prod\limits_{i=\frac n2}^{n-1}(x-c^i)，后一半乘积等于 \prod\limits_{i=0}^{\frac n2-1}(x-c^{i+\frac n2})，提出 c^{\frac n2} 可得 \prod\limits_{i=0}^{\frac n2-1}c^\frac n2\left(\dfrac x{c^\frac n2}-c^i\right)=c^{(\frac n2)^2}\prod\limits_{i=0}^{\frac n2-1}\left(\dfrac x{c^\frac n2}-c^i\right)=c^{(\frac n2)^2}M_\frac n2\left(\dfrac x{c^\frac n2}\right)，故 M_n(x)=c^{(\frac n2)^2}M_\frac n2(x)M_\frac n2\left(\dfrac x{c^\frac n2}\right)。

假设我们已经计算出了 M_\frac n2(x)，我们容易 O(n) 计算出 M_\frac n2\left(\dfrac x{c^\frac n2}\right)，时间复杂度 T(n)=T(n/2)+O(n\log n)=O(n\log n)。

算出 M_n(x) 后，我们使用 Chirp Z-Transform 算出 M_n'(1),M_n'(c),\cdots,M_n'(c^{n-1})，设 p_i=\dfrac{y_i}{M_n'(c^i)}，则我们要求的 f(x)=M_n(x)\sum\limits_{i=0}^{n-1}\dfrac{p_i}{x-c^i}。

尝试将封闭形式展开，\dfrac1{x-c^i}=-\dfrac1{c^i-x}=-\dfrac1{c^i}\dfrac1{1-\frac1{c^i}x}，展开 \dfrac1{1-\frac1{c^i}x} 得 \sum\limits_{j=0}^\infty\dfrac1{c^{ij}}x^j，由于我们要对 x^n 取模，所以求和只需要前 n 项。