分治FFT 1

已知函数 $g(x)$,且 $f(x),g(x)$ 存在如下关系,求 $f(x)$

$$f(i)=\sum_{j=1}^{i} f(i-j)g(j)$$

可以利用 CDQ 分治的思想,将一段区间分为两半递归处理,并统计左半部分对右部分的贡献。具体地说,当我们要计算 $f(l \sim r)$ 时,先计算出 $f(l \sim mid)$ 的值,然后将这部分和 $g(1 \sim r-l)$ 卷积起来,就可以得到这部分对后半贡献。递归的边界应该是 $f(0)=1$,然后向上合并就可以计算出 $f(x)$ 的每一项,这样的复杂度是 $O(n \log^2 n)$ 的。

void divide(int l, int r)
{
    if(l==r) return;
    int mid=(l+r)>>1, bit=0;
    divide(l, mid);
    while((1<<bit)<=((r-l+1)<<1)) bit++;
    for(rint i=0; i<(1<<bit); ++i)
    {
        pos[i]=(pos[i>>1]>>1)|((i&1)<<(bit-1));
        a[i]=b[i]=0;
    }
    for(rint i=l; i<=mid; ++i) a[i-l]=f[i];
    for(rint i=0; i<=r-l; ++i) b[i]=g[i];
    ntt(a, 1<<bit, 1), ntt(b, 1<<bit, 1);
    for(rint i=0; i<(1<<bit); ++i) a[i]=1LL*a[i]*b[i]%P;
    ntt(a, 1<<bit, -1);
    for(rint i=mid+1; i<=r; ++i) f[i]=add(f[i], a[i-l]);
    divide(mid+1, r);
}

分治FFT 2

对于给定数组 $a,b$,且 $f(x)$ 有如下形式,求 $f(x)$

$$f(x)=\prod_{i=0}^{n} (a_ix+b_i)$$

可以利用分治的思想,将这个 $n+1$ 个多项式每次分为两部分,递归处理完后再将两部分合并。具体地说,当计算 $\prod_{i=l}^{r} (a_ix+b_i)$ 时,可以分别递归计算 $l \sim mid$ 和 $mid+1 \sim r$ 这两部分多项式的积,然后再用一遍 FFT 合并,这样复杂度也是 $O(n \log^2 n)$ 的。在一些情况下可以利用倍增的思想将复杂度优化至 $O(n \log n)$。

void divide(int a[], int l, int r)
{
    if(l==r) {a[0]=l, a[1]=1; return;}
    int mid=(l+r)>>1, bit=0;
    while((1<<bit)<=(r-l+1)) bit++;
    int b[(1<<bit)+5], c[(1<<bit)+5];
    for(rint i=0; i<1<<bit; ++i) b[i]=c[i]=0;
    divide(b, l, mid), divide(c, mid+1, r);
    for(rint i=0; i<1<<bit; ++i) pos[i]=(pos[i>>1]>>1)|((i&1)<<(bit-1));
    ntt(b, 1<<bit, 1), ntt(c, 1<<bit, 1);
    for(rint i=0; i<1<<bit; ++i) a[i]=1LL*b[i]*c[i]%P;
    ntt(a, 1<<bit, -1);
}

多项式求逆

如果多项式 $f(x),g(x)$ 满足如下关系,我们就记 $g(x)$ 为 $f(x)$ 的逆元。

$$f(x)g(x) \equiv 1 \pmod {x^n}$$

我们可以递归地求解这个问题,首先考虑 $n=1$ 时,不妨设 $f(x) \equiv c \pmod x$,此时显然有 $f^{-1}(x)=c^{-1}$;

当 $n>1$ 时,我们假设 $f(x)$ 在 $\mod x^{\lceil \frac{n}{2} \rceil}$ 意义下的逆元 $g'(x)$ 已经求出,那么就有

$$f(x)*g'(x) \equiv 1 \pmod {x^{\lceil \frac{n}{2} \rceil}}$$

根据定义可以知道

$$f(x)*g(x) \equiv 1 \pmod {x^{\lceil \frac{n}{2} \rceil}}$$

两式相减得到:

$$g(x)-g'(x) \equiv 0 \pmod {x^{\lceil \frac{n}{2} \rceil}} $$

将左边的多项式平方后放在模 $x^n$ 意义下,这个多项式每一项可以写成原多项式的卷积,这个卷积的每一项一定包含一个原多项式的 $0 \sim \lceil \frac{n}{2} \rceil$ 次项,并且原多项式的 $0 \sim \lceil \frac{n}{2} \rceil$ 次项均为 $0$,所以这个 $n$ 次的多项式每一项也一定都为 $0$。即:

$$g^2(x)-2g'(x)g(x)+g’^2(x) \equiv 0 \pmod{ x^n} $$

将两边同时乘上 $f(x)$ 后可以得到:

$$g(x)= 2g'(x) – g'(x)f(x) \pmod{x^n} $$

这样以来,我们就可以用 $O(n \log n)$ 的时间从 $g'(x)$ 推到 $g(x)$,根据主定理可以知道总时间复杂度依然为 $O(n \log n)$。

void inv(int a[], int b[], int n)
{
    if(n==1) {b[0]=ksm(a[0], P-2); return;}
    inv(a, b, (n+1)>>1);
    int bit=0;
    while((1<<bit)<(n<<1)) bit++;
    for(rint i=0; i<(1<<bit); ++i) pos[i]=(pos[i>>1]>>1)|((i&1)<<(bit-1));
    for(rint i=0; i<n; ++i) c[i]=a[i];
    for(rint i=n; i<(1<<bit); ++i) c[i]=0;
    ntt(c, 1<<bit, 1), ntt(b, 1<<bit, 1);
    for(rint i=0; i<(1<<bit); ++i) b[i]=1LL*sub(2, 1LL*c[i]*b[i]%P)*b[i]%P;
    ntt(b, 1<<bit, -1);
    for(rint i=n; i<(1<<bit); ++i) b[i]=0;
}

多项式除法

多项式取模

多项式开根

发表评论

邮箱地址不会被公开。 必填项已用*标注