多项式全家桶学习笔记

多项式乘法

Luogu 3803

没有什么好说的,放个代码走人。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=4000000+10;
const int mod=998244353,G=3,Gi=(mod+1)/G;

inline int qpow(int a,int b) {
    int c=1;
    for (;b;b>>=1,a=1ll*a*a%mod)
        if (b&1) c=1ll*c*a%mod;
    return c;
}

int n,m;
int f[N],g[N],r[N];

inline void NTT(int* A,int n,int op) {
    for (re int i=0;i<n;++i) if (i<r[i]) swap(A[i],A[r[i]]);
    for (re int i=1;i<n;i<<=1) {
        int rot=qpow(op==1?G:Gi,(mod-1)/(i<<1));
        for (re int j=0;j<n;j+=(i<<1)) {
            int w=1;
            for (re int k=0;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 (re int i=0;i<n;++i) A[i]=1ll*A[i]*inv%mod;
    }
}

int main() {
    n=read(),m=read();
    for (re int i=0;i<=n;++i) f[i]=read();
    for (re int i=0;i<=m;++i) g[i]=read();
    int lim=1,l=0;
    for (;lim<=n+m;lim<<=1,++l);
    for (re int i=0;i<lim;++i) r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
    NTT(f,lim,1),NTT(g,lim,1);
    for (re int i=0;i<lim;++i) f[i]=1ll*f[i]*g[i]%mod;
    NTT(f,lim,-1);
    for (re int i=0;i<=n+m;++i) printf("%d ",f[i]); puts("");
    return 0;
}

泰勒展开

如果 $f(x)$ 在 $x_0$ 处存在 $n$ 阶导,那么

$$ \displaystyle \begin{aligned} f(x)=&f(x_0)+\frac{f'(x_0)}{1!}(x-x_0)+\frac{f''(x_0)}{2!}(x-x_0)^2+\cdots+\frac{f^n(x_0)}{n!}(x-x_0)^n+\xi\\ =&\sum_{i=0}^n\frac{f^i(x_0)}{i!}(x-x_0)^i+\xi \end{aligned} $$

这里的 $\xi$ 是余项,当 $n\to \infty$ 时 $\xi\to 0$ 。

一个栗子:$\displaystyle e^x=1+\frac{x}{1!}+\frac{x^2}{2!}+\frac{x^3}{3!}+\cdots$ 。

牛顿迭代

假设 $F(x)$ 是一个已知的多项式,现在要求一个 $G_t(x)$ 使得 $F(G_t(x))\equiv 0\pmod {x^{2^t}}$ 。

假设我们已经知道 $G_t(x)$ ,要求 $G_{t+1}(x)$ 。

对于 $F(G_{t+1}(x))$ 在 $G_t(x)$ 处泰勒展开,可以得到

$$ \displaystyle F(G_{t+1}(x))=F(G_t(x))+\frac{F'(G_t(x))}{1!}\big(G_{t+1}(x)-G_t(x)\big) $$

化简后得到

$$ \displaystyle G_{t+1}(x)=G_t(x)-\frac{F(G_t(x))}{F'(G_t(x))} $$

求导与积分

没什么好说的。

代码

inline void getderi(int* f,int* g,int n) { //求导
    for (re int i=1;i<n;++i) g[i-1]=1ll*i*f[i]%mod;
    g[n]=g[n-1]=0;
}

inline void getinte(int* f,int* g,int n) { //积分
    for (re int i=1;i<n;++i) g[i]=1ll*f[i-1]*qpow(i,mod-2)%mod;
    g[0]=0;
}

多项式求逆

Luogu 4238

假设求出了模 $x^{\frac{n}{2}}$ 时的答案 $H(x)$ ,现在要求模 $x^n$ 时的答案 $G(x)$ 。

于是可以大力推一推:

$$ \displaystyle \begin{aligned} &F(x)H(x)\equiv 1\pmod{x^{\frac{n}{2}}},F(x)G(x)\equiv 1\pmod{x^n}\\ \Longrightarrow& F(x)\big(G(x)-H(x)\big)\equiv 0\pmod{x^{\frac{n}{2}}}\\ \Longrightarrow& G(x)-H(x)\equiv0\pmod{x^{\frac{n}{2}}}\\ \Longrightarrow& G(x)^2-2G(x)H(x)+H(x)^2\equiv0\pmod{x^n}\\ \Longrightarrow& G(x)\equiv2H(x)-F(x)H(x)^2\pmod{x^n} \end{aligned} $$

直接递归计算即可。

代码

inline 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 (re int i=0;i<n;++i) A[i]=f[i],B[i]=g[i];
    int lim=1,l=0;
    for (;lim<=n;lim<<=1,++l);
    for (re int i=0;i<lim;++i) r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
    NTT(A,lim,1),NTT(B,lim,1);
    for (re int i=0;i<lim;++i) A[i]=1ll*A[i]*B[i]%mod*B[i]%mod;
    NTT(A,lim,-1);
    for (re int i=0;i<n;++i) g[i]=(g[i]+g[i])%mod;
    for (re int i=0;i<n;++i) g[i]=(g[i]+mod-A[i])%mod;
    for (re int i=0;i<lim;++i) A[i]=B[i]=0;
}

多项式开根

考虑牛顿迭代。可以写出 $F(B_t(x))=B_t(x)^2-A(x)=0$ 。

套式子得到

$$ \displaystyle \begin{aligned} B_{t+1}(x)=&B_t(x)-\frac{B_t(x)^2-A(x)}{2B_t(x)}\\ =&\frac{B_t(x)+\frac{A(x)}{B_t(x)}}{2} \end{aligned} $$

直接递归+多项式求逆即可。

代码

inline 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 (re int i=0;i<n;++i) A[i]=f[i];
    getinv(g,B,n);
    int lim=1,l=0;
    for (;lim<=n;lim<<=1,++l);
    for (re int i=0;i<lim;++i) r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
    NTT(A,lim,1),NTT(B,lim,1);
    for (re int i=0;i<lim;++i) A[i]=1ll*A[i]*B[i]%mod;
    NTT(A,lim,-1);
    for (re int i=0;i<n;++i) g[i]=1ll*(g[i]+A[i])%mod*inv2%mod;
    for (re int i=0;i<lim;++i) A[i]=B[i]=0;
}

多项式 ln

大力推推推。

$$ \displaystyle \begin{aligned} &\ln\big(A(x)\big)=B(x)\\ \Longrightarrow&\Big(\ln\big(A(x)\big)\Big)'=B'(x)\\ \Longrightarrow&\frac{A'(x)}{A(x)}=B'(x) \end{aligned} $$

于是求导、求逆,乘起来再积分回去即可。

代码

inline void getln(int* f,int* g,int n) {
    static int A[N],B[N];
    getderi(f,A,n),getinv(f,B,n);
    int lim=1,l=0;
    for (;lim<=n;lim<<=1,++l);
    for (re int i=0;i<lim;++i) r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
    NTT(A,lim,1),NTT(B,lim,1);
    for (re int i=0;i<lim;++i) A[i]=1ll*A[i]*B[i]%mod;
    NTT(A,lim,-1); getinte(A,g,n);
    for (re int i=0;i<lim;++i) A[i]=B[i]=0;
}

多项式 exp

求导看上去不行了,考虑两边取对数。

要求的是 $B(x)=\exp\big(A(x)\big)$ ,两边取对数得到 $\ln\big(B(x)\big)=A(x)$ 。

考虑牛顿迭代,可以得到 $F(B_t(x))=\ln\big(B(x)\big)-A(x)$ 。

套式子得到

$$ \displaystyle \begin{aligned} B_{t+1}(x)=&B_t(x)-\frac{\ln\big(B_t(x)\big)-A(x)}{\frac{1}{B_t(x)}}\\ =&B_t(x)\Big(1-\ln\big(B_t(x)\big)+A(x)\Big) \end{aligned} $$

直接递归+多项式 ln 计算即可。

代码

inline 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 (re int i=0;i<n;++i) A[i]=g[i];
    getln(g,B,n);
    for (re int i=0;i<n;++i) B[i]=(mod-B[i]+f[i])%mod;
    B[0]=(B[0]+1)%mod;
    int lim=1,l=0;
    for (;lim<=n;lim<<=1,++l);
    for (re int i=0;i<lim;++i) r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
    NTT(A,lim,1),NTT(B,lim,1);
    for (re int i=0;i<lim;++i) A[i]=1ll*A[i]*B[i]%mod;
    NTT(A,lim,-1);
    for (re int i=0;i<n;++i) g[i]=A[i];
    for (re int i=0;i<lim;++i) A[i]=B[i]=0;
}

多项式快速幂

$$ \displaystyle A^k(x)=\exp\Big(k\times\ln\big(A(x)\big)\Big) $$

直接 ln + exp 计算即可。常数略大。

代码

inline void getpow(int* f,int* g,int n,int k) {
    static int h[N];
    getln(f,h,n);
    for (re int i=0;i<n;++i) h[i]=1ll*k*h[i]%mod;
    getexp(h,g,n);
    for (re int i=0;i<n;++i) h[i]=0;
}

多项式除法

咕咕咕

多项式三角函数

$\color{black}{\text{x}}\color{red}{\text{gzc}}$ 更了我就更

多项式反三角函数

$\color{black}{\text{x}}\color{red}{\text{gzc}}$ 更了我就更

多项式多点求值

$\color{black}{\text{x}}\color{red}{\text{gzc}}$ 更了我就更

多项式快速插值

$\color{black}{\text{x}}\color{red}{\text{gzc}}$ 更了我就更

多项式复合

$\color{black}{\text{x}}\color{red}{\text{gzc}}$ 更了我就更

最后修改:2019 年 09 月 27 日 01 : 24 PM

7 条评论

  1. memset0

    Orz M_sea !

    1. M_sea
      @memset0

      memset0 小姐姐!

      1. Karry5307
        @M_sea

        orz memset0 && orz M_sea !

  2. xgzc

    M_sea你搞什么

    1. M_sea
      @xgzc

      搞生物(不是)

  3. Karry5307

    会多项式复合的大神仙%%%%

    1. M_sea
      @Karry5307

      不是我哪句话说我会了

发表评论