多项式好毒瘤啊 /kel

本文中一些写法可能不严谨,欢迎指出。

为了方便,下文中的多项式长度和 $n$ 均为 $2$ 的幂,模数均为 $998244353$。

多项式乘法

这是前置知识,如果不会建议「点开洛谷题面单击右边蓝色按钮题解」。

void NTT(int* A,int n,int op) {
    for (int i=0;i<n;++i) if (i<r[i]) swap(A[i],A[r[i]]);
    for (int i=1;i<n;i<<=1) {
        int rot=qpow(op==1?3:332748118,(mod-1)/(i<<1));
        for (int j=0;j<n;j+=i<<1)
            for (int k=0,w=1;k<i;++k,w=1ll*w*rot%mod) {
                int x=A[j+k],y=1ll*w*A[j+k+i]%mod;
                A[j+k]=(x+y)%mod,A[j+k+i]=(x-y+mod)%mod;
            }
    }
    if (op==-1) { int inv=qpow(n,mod-2);
        for (int i=0;i<n;++i) A[i]=1ll*A[i]*inv%mod;
    }
}
int NTT_init(int n) {
    int lim=1,l=-1;
    for (;lim<=n;lim<<=1,++l);
    for (int i=0;i<lim;++i) r[i]=(r[i>>1]>>1)|((i&1)<<l);
    return lim;
}

多项式求导

$$ (x^a)'=ax^{a-1} $$

void getderi(int* F,int* G,int n) {
    for (int i=1;i<n;++i) G[i-1]=1ll*F[i]*i%mod;
    G[n-1]=0;
}

多项式不定积分

$$ \int x^a\mathrm{d}x=\frac{x^{a+1}}{a+1} $$

void getinte(int* F,int* G,int n) {
    for (int i=1;i<n;++i) G[i]=1ll*F[i-1]*qpow(i,mod-2)%mod;
    G[0]=0;
}

多项式牛顿迭代

已知 $G(x)$,求 $F(x)$ 满足 $G(F(x))\equiv 0\pmod{x^n}$。

假设我们已经求出了 $F_o(x)$ 满足 $G(F_0(x))\equiv 0\pmod{x^{\frac{n}{2}}}$,将 $G(x)$ 在 $F_0(x)$ 处泰勒展开得到

$$ G(F(x))=\sum_{i=0}^{+\infty}\frac{G^{(i)}(F_0(x))}{i!}(F(x)-F_0(x))^i $$

可以发现 $i\geq 2$ 时在模 $x^n$ 意义下都为 $0$,所以

$$ G(F(x))\equiv G(F_0(x))+G'(F_0(x))(F(x)-F_0(x))\pmod{x^n} $$

又 $G(F(x))=0$,化简得到

$$ F(x)=F_0(x)-\frac{G(F_0(x))}{G'(F_0(x))}\pmod{x^n} $$

多项式求逆

已知 $F(x)$,求 $G(x)$ 满足 $F(x)G(x)\equiv 1\pmod{x^n}$。

Luogu

假设我们已经求出了 $G_0(x)$ 满足 $F(x)G_0(x)\equiv 1\pmod{x^{\frac{n}{2}}}$,那么

$$ F(x)(G(x)-G_0(x))\equiv 0\pmod{x^\frac{n}{2}} $$

所以

$$ G(x)-G_0(x)\equiv 0\pmod{x^{\frac{n}{2}}} $$

平方得到

$$ G(x)^2-2G(x)G_0(x)+G_0(x)^2\equiv 0\pmod{x^n} $$

乘上 $F(x)$ 即可得到

$$ G(x)\equiv 2G_0(x)-F(x)G_0(x)^2\pmod{x^n} $$

这样就可以由 $G_0(x)$求出 $G(x)$ 了。

void getinv(int* F,int* G,int n) {
    static int A[N],B[N];
    if (n==1) { G[0]=qpow(F[0],mod-2); return; }
    getinv(F,G,n>>1);
    for (int i=0;i<n;++i) A[i]=F[i],B[i]=G[i];
    int lim=NTT_init(n);
    NTT(A,lim,1),NTT(B,lim,1);
    for (int i=0;i<lim;++i) A[i]=1ll*A[i]*B[i]%mod*B[i]%mod;
    NTT(A,lim,-1);
    for (int i=0;i<n;++i) G[i]=(2ll*G[i]-A[i]+mod)%mod;
    for (int i=0;i<lim;++i) A[i]=B[i]=0;
}

多项式对数函数

已知 $F(x)$,求 $G(x)$ 满足 $G(x)\equiv\ln F(x)\pmod{x^n}$。保证 $F(x)$ 常数项为 $1$。

Luogu

两边求导得到

$$ G'(x)\equiv\ln'(F(x))F'(x)\pmod{x^n} $$

$$ G'(x)\equiv\frac{F'(x)}{F(x)}\pmod{x^n} $$

求导+求逆后乘起来再不定积分回去即可。

void getln(int* F,int* G,int n) {
    static int A[N],B[N];
    getderi(F,A,n),getinv(F,B,n);
    int lim=NTT_init(n);
    NTT(A,lim,1),NTT(B,lim,1);
    for (int i=0;i<lim;++i) A[i]=1ll*A[i]*B[i]%mod;
    NTT(A,lim,-1);
    getinte(A,G,n);
    for (int i=0;i<lim;++i) A[i]=B[i]=0;
}

多项式指数函数

已知 $F(x)$,求 $G(x)$ 满足 $G(x)\equiv e^{F(x)}\pmod{x^n}$。保证 $F(x)$ 常数项为 $0$。

Luogu

两边取对数得到

$$ \ln G(x)-F(x)\equiv 0\pmod{x^n} $$

不妨设 $H(G(x))\equiv \ln G(x)-F(x)\pmod{x^n}$,套牛顿迭代得到

$$ \begin{aligned} G(x)&\equiv G_0(x)-\frac{H(G_0(x))}{H'(G_0(x))}\pmod{x^n}\\ &\equiv G_0(x)-\frac{\ln G_0(x)-F(x)}{\frac{1}{G_0(x)}}\pmod{x^n}\\ &\equiv G_0(x)(1-\ln G_0(x)+F(x))\pmod{x^n} \end{aligned} $$

void getexp(int* F,int* G,int n) {
    static int A[N],B[N];
    if (n==1) { G[0]=1; return; }
    getexp(F,G,n>>1);
    for (int i=0;i<n;++i) A[i]=G[i];
    getln(G,B,n);
    for (int i=0;i<n;++i) B[i]=(mod-B[i]+F[i])%mod;
    B[0]=(B[0]+1)%mod;
    int lim=NTT_init(n);
    NTT(A,lim,1),NTT(B,lim,1);
    for (int i=0;i<lim;++i) A[i]=1ll*A[i]*B[i]%mod;
    NTT(A,lim,-1);
    for (int i=0;i<n;++i) G[i]=A[i];
    for (int i=0;i<lim;++i) A[i]=B[i]=0;
}

多项式幂函数

已知 $F(x)$ 和 $k$,求 $G(x)$ 满足 $G(x)\equiv F(x)^k\pmod{x^n}$。保证 $F(x)$ 常数项为 $1$。

Luogu

求 $\ln$ 后将系数乘上 $k$ 再 $\exp$ 回去即可。

void getpow(int* F,int* G,int n) {
    static int A[N];
    getln(F,A,n);
    for (int i=0;i<n;++i) A[i]=1ll*A[i]*k%mod;
    getexp(A,G,n);
    for (int i=0;i<n;++i) A[i]=0;
}

如果不保证常数项为 $1$,可以先提一个 $a\times x^b$ 出来转化成常数项为 $1$ 的情况,最后再乘回去。

多项式开根

已知 $F(x)$,求 $G(x)$ 满足 $G(x)^2\equiv F(x)\pmod{x^n}$,多解保留常数项较小的那一个。保证 $F(x)$ 常数项为 $1$。

Luogu

移项得到

$$ G(x)^2-F(x)\equiv 0\pmod{x^n} $$

不妨设 $H(G(x))\equiv G(x)^2-F(x)\pmod{x^n}$,套牛顿迭代得到

$$ \begin{aligned} G(x)&\equiv G_0(x)-\frac{H(G_0(x))}{H'(G_0(x))}\pmod{x^n}\\ &\equiv G_0(x)-\frac{G_0(x)^2-F(x)}{2G_0(x)}\pmod{x^n}\\ &\equiv \frac{G_0(x)}{2}+\frac{F(x)}{2G_0(x)} \end{aligned} $$

void getsqrt(int* F,int* G,int n) {
    static int A[N],B[N];
    if (n==1) { G[0]=1; return; }
    getsqrt(F,G,n>>1);
    for (int i=0;i<n;++i) A[i]=F[i];
    getinv(G,B,n);
    int lim=NTT_init(n);
    NTT(A,lim,1),NTT(B,lim,1);
    for (int i=0;i<lim;++i) A[i]=1ll*A[i]*B[i]%mod;
    NTT(A,lim,-1);
    for (int i=0;i<n;++i) G[i]=1ll*(A[i]+G[i])*inv2%mod;
    for (int i=0;i<lim;++i) A[i]=B[i]=0;
}

如果不保证常数项为 $1$,则将边界由 $1$ 改为 $F(x)$ 常数项的二次剩余即可。求二次剩余不在本文的讨论范围内。


后面的先咕着,等我什么时候会了再更吧(

最后修改:2020 年 09 月 23 日 02 : 59 PM