多项式板子

_SeeleVollerei_ · 2021-12-01 10:50:52 · 个人记录

我觉得板子放在学习笔记里太占用空间了，干脆单独出来放一份。

关于原根

常用的原根都是 3 (998244353)，结果 ldq 和我说 114514 也是 998244353 的原根，改了一下交上去还真过了。

有点像卡常的东西实际上是复杂度问题

期间有很多清空的东西不要用 memset ，因为这会使 O(n) 的清空复杂度变成 O(n\log n) 。手打循环一个个清就好了。

防止重复变量数组的神奇方法

在函数里开

static int [];

然后这个数组只能在这个函数里用，但是是全局变量，非常神奇。

多项式求导/微分

f(x)=\sum \limits_{i=0}^n a_i x^i,f'(x)=\sum \limits_{i=0}^{n-1}(i+1)a_{i+1}x^i

f(x)=\ln x,f'(x)=\frac{1}{x}

f(g(x))'=f'(g(x))g'(x)

多项式积分

f'(x)=\sum \limits_{i=0}^na_ix^i,f(x)=\sum \limits_{i=1}^{n+1}\frac{a_{i-1}x^i}{i}

多项式求逆

已知多项式 f(x) ，求 g(x) 满足 g(x)f(x) \equiv 1 \pmod {x^n}

把 n 搞成 2^k ，求 g(x)f(x) \equiv 1 \pmod {x^{2^k}} 保留 n 位即可。后面的所有 \bmod {x^n} 都采用这个思想

假设已知 g_0(x)f(x) \equiv 1 \pmod {x^{2^{(k-1)}}}

有 g(x)f(x) \equiv 1 \pmod {x^{2^{(k-1)}}}

则有 g(x)-g_0(x) \equiv 0 \pmod {x^{2^{(k-1)}}}

两边同时平方

g(x)^2-2g(x)g_0(x)+g_0(x)^2 \equiv 0 \pmod {x^{2^k}}

同时乘 f(x)

g(x)-2g_0(x)+g_0(x)^2f(x) \equiv 0 \pmod {x^{2^k}}

则有

g(x)\equiv 2g_0(x)-g_0(x)^2f(x) \pmod {x^{2^k}}

递推/递归处理即可。

边界条件：当 k=0 时，相当于常数项的逆元

多项式求 \ln

已知多项式 f(x) ，求 g(x)\equiv \ln\ f(x) \pmod {x^n}

两边求个导，左边就是 g'(x) 。

右边实际上是个复合函数，套一下最上面的公式就是 \ln'(f(x))f'(x)

而 \ln'(f(x))=\frac{1}{f(x)}

所以原式变成

g'(x)=\frac{f'(x)}{f(x)} \pmod {x^n}

对 f(x) 分别求个导求个逆就好了，乘起来就是 g'(x)

然后对 g'(x) 积分一下就是 g(x) 了

泰勒展开

已知多项式 $f(x)$ ，知道当 $x=x0$ 时多项式的值，则有 $$f(x)=f(x0)+\sum \limits_{i=1}^\infty \frac{f^i(x0)}{i!}(x-x0)^i$$ ### 多项式复合/牛顿迭代已知多项式 $f(x)$ ，求 $g(x)$ 满足 $f(g(x))\equiv 0 \pmod {x^n}

假设已知 g_0(x) 满足 f(g_0(x))\equiv 0 \pmod{x^{\lceil\frac{n}{2}\rceil}}

则有

g(x)\equiv g_0(x)-\frac{f(g_0(x))}{f'(g_0(x))}\pmod{x^n}

多项式求 \exp

已知多项式 f(x) ，求 g(x) 满足 g(x)\equiv e^{f(x)} \pmod {x^n}

\exp$ 就是 $\ln$ 的逆运算，则有 $\ln g(x)\equiv f(x) \pmod {x^n}

设 G(g(x))=\ln g(x)-f(x) ,现在要求 g(x) 使得这个式子为 0

也就是已知多项式 G(x) ，求 g(x) 满足G(g(x)) \equiv 0 \pmod {x^n}

就是多项式复合/牛顿迭代了

g(x)\equiv g_0(x)-\frac{G(g_0(x))}{G'(g_0(x))} \pmod {x^n}

对 G 求个导，把后面的 -f(x) 看作常数项，其实就是 G'(g(x))=\frac{1}{g(x)}

拆开来就是最后的式子了

g(x)\equiv g_0(x)-\frac{\ln g_0(x)-f(x)}{\frac{1}{g_0(x)}} \pmod {x^n}

写完它

g(x)\equiv g_0(x)-(\ln g_0(x)-f(x))g_0(x) \pmod {x^n}

多项式开根

已知多项式 f(x) ，求 g(x) 满足 g^2(x)\equiv f(x) \pmod {x^n}

假设已知 g_0^2(x)\equiv f(x) \pmod {x^{\lceil \frac{n}{2} \rceil}}

则有 g(x) \equiv g_0(x) \pmod {x^{\lceil \frac{n}{2}\rceil}}

即 g(x)-g_0(x)\equiv0 \pmod {x^{\lceil \frac{n}{2}\rceil}}

两边同时平方

g^2(x)-2g_0(x)g(x)+g_0^2(x) \equiv 0 \pmod{x^n}

将 g^2(x)\equiv f(x) \pmod {x^n} 代入

f(x)-2g_0(x)g(x)+g_0^2(x)\equiv 0 \pmod {x^n}

移一下项可得 g(x)\equiv \frac{f(x)+g_0^2(x)}{2g_0(x)} \pmod {x^n}

多项式快速幂

已知多项式 f(x) ，求 g(x) \equiv f^k(x) \pmod {x^n}

一开始看到这个式子时，我的反应是这样的：

这不就直接暴力 NTT 乘套一个快速幂就好了吗？？

然后看了一下数据范围

k\le 10^{10^5}

那没事了那没事了还是老老实实推式子吧

想办法把 k 弄到四则运算里来，两边同时取对数就好了，通常取 \ln

\ln (g(x)) \equiv k\times \ln(f(x)) \pmod {x^n}

右边我们是会求的，但是如何把左边的 \ln 去掉？再套一个 \exp 就行了。

e^{\ln(g(x))} \equiv e^{k\times \ln(f(x))} \pmod {x^n}

g(x) \equiv e^{k\times \ln(f(x))} \pmod{x^n}

多项式除法

已知多项式 n 次多项式 A(x) 和 m 次多项式 B(x) ，求 n-m 次多项式 f(x) 和 m-1 次多项式 g(x) 满足 A(x)=B(x)f(x)+g(x)

令 A^{r(n)}(x) 表示 A(x) 翻转的多项式

形式化地说，假设 A(x)=\sum\limits_{i=0}^na_ix^i ，则 A^{r(n)}(x)=\sum\limits_{i=0}^na_{n-i}x^i

然后有一个很神奇的式子 A^{r(n)}(x)=A(\frac{1}{x})x^n

考虑对于原式 A(x)=B(x)f(x)+g(x) ，两边同时翻转

则有 A^{r(n)}(x)=x^n(B(\frac{1}{x})f(\frac{1}{x})+g(\frac{1}{x}))

A^{r(n)}(x)=x^mB(\frac{1}{x})x^{n-m}f(\frac{1}{x})+x^ng(\frac{1}{x})

A^{r(n)}(x)=B^{r(m)}(x)f^{r(n-m)}(x)+g^{r(n)}(x)

考虑 g(x) 的系数是从 0 到 m-1 次的，在 n 位翻转后就会变成 n-m+1 到 n

对两边同时对 x^{n-m+1} 取模，那么 g 就没了，而且对 f 刚好不会影响

A^{r(n)}(x)\equiv B^{r(m)}(x)f^{r(n-m)}(x) \pmod {x^{n-m+1}}

则 f^{r(n-m)}(x) \equiv \frac{A^{r(n)}(x)}{B^{r(m)}(x)} \pmod {x^{n-m+1}}

f(x)\equiv (\frac{A^{r(n)}(x)}{B^{r(m)}(x)})^{r(n-m)} \pmod {x^{n-m+1}}

然后把 f(x) 代回原式算一下就可以搞出 g 了

在最后放一下自己的板子

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1e5+5;
const int Mod=998244353;
const int G=3;
const int INV2=(Mod+1)/2;
inline int Read(){
    char ch;
    int f=1;
    while((ch=getchar())<'0'||ch>'9')
        if(ch=='-') f=-1;
    int x=ch^48;
    while((ch=getchar())>='0'&&ch<='9')
        x=(x<<3)+(x<<1)+(ch^48);
    return x*f;
}
inline void Print(const int x,const char ch='\n',const bool flg=1){
    if(x>=10) Print(x/10,ch,0);
    putchar(x%10+48);
    if(flg) putchar(ch);
    return ;
}
inline int Quick_Pow(int a,int b){
    int ss=1;
    for(;b;b>>=1){
        if(b&1) ss=1ll*ss*a%Mod;
        a=1ll*a*a%Mod;
    }
    return ss;
}
inline void Swap(int&x,int&y){
    int tmp=x;
    x=y;y=tmp;
    return ;
}
int rev[N<<3];
inline void NTT(int*p,const int s1,const bool inv){
    for(register int i=0;i<s1;i++)
        if(i<rev[i]) Swap(p[i],p[rev[i]]);
    for(register int mid=1;mid<s1;mid<<=1){
        int wn=Quick_Pow(G,(Mod-1)/(mid<<1));
        if(inv) wn=Quick_Pow(wn,Mod-2);
        for(register int len=mid<<1,i=0;i<s1;i+=len){
            int w=1;
            for(register int j=0;j<mid;j++,w=1ll*w*wn%Mod){
                int a1=p[i+j],a2=p[i+j+mid];
                p[i+j]=(a1+1ll*w*a2%Mod)%Mod;
                p[i+j+mid]=(a1-1ll*w*a2%Mod+Mod)%Mod;
            }
        }
    }
    return ;
}
inline void GetMul(int*f,int*g,const int n,const int m,int*p){
    int s1=1,pos=0;
    while(s1<=(n+m)) s1<<=1,pos++;
    for(register int i=0;i<s1;i++)
        rev[i]=(rev[i>>1]>>1)|((i&1)<<(pos-1));
    NTT(f,s1,0);NTT(g,s1,0);
    for(register int i=0;i<s1;i++)
        p[i]=1ll*f[i]*g[i]%Mod;
    NTT(f,s1,1);NTT(g,s1,1);NTT(p,s1,1);
    int inv=Quick_Pow(s1,Mod-2);
    for(register int i=0;i<s1;i++){
        f[i]=1ll*f[i]*inv%Mod;
        g[i]=1ll*g[i]*inv%Mod;
        p[i]=1ll*p[i]*inv%Mod;
    }
    return ;
}
inline void GetDao(int*f,int*g,const int n){
    for(register int i=0;i<n-1;i++)
        g[i]=1ll*(i+1)*f[i+1]%Mod;
    return ;
}
inline void GetJi(int*f,int*g,const int n){
    for(register int i=1;i<=n;i++)
        g[i]=1ll*f[i-1]*Quick_Pow(i,Mod-2)%Mod;
    return ;
}
inline void GetInv(int*f,int*g,const int n){
    static int gp[N<<3],tmp[N<<3];
    g[0]=Quick_Pow(f[0],Mod-2);
    for(register int len=1,t=0;len<n;len<<=1,t++){
        int s1=len<<1,pos=t+1;
        for(register int i=0;i<s1;i++){
            gp[i]=g[i];
            tmp[i]=f[i];
        }
        s1<<=1,pos++;
        for(register int i=len<<1;i<s1;i++)
            gp[i]=tmp[i]=0;
        for(register int i=0;i<s1;i++)
            rev[i]=(rev[i>>1]>>1)|((i&1)<<(pos-1));
        NTT(gp,s1,0);NTT(tmp,s1,0);
        for(register int i=0;i<s1;i++){
            g[i]=2*gp[i]%Mod;
            int gl=1ll*gp[i]*gp[i]%Mod*tmp[i]%Mod;
            g[i]=(g[i]-gl+Mod)%Mod;
        }
        NTT(g,s1,1);
        int inv=Quick_Pow(s1,Mod-2);
        for(register int i=0;i<s1;i++)
            g[i]=1ll*g[i]*inv%Mod;
        for(register int i=len<<1;i<s1;i++)
            g[i]=0;
    }
    return ;
}
inline void GetLn(int*f,int*g,const int n){
    static int finv[N<<3],fdao[N<<3],gdao[N<<3];
    GetDao(f,fdao,n);
    GetInv(f,finv,n);
    int s1=1,pos=0;
    while(s1<=(n<<1)) s1<<=1,pos++;
    for(register int i=n;i<s1;i++)
        fdao[i]=finv[i]=0;
    for(register int i=0;i<s1;i++)
        rev[i]=(rev[i>>1]>>1)|((i&1)<<(pos-1));
    NTT(fdao,s1,0);NTT(finv,s1,0);
    for(register int i=0;i<s1;i++)
        gdao[i]=1ll*fdao[i]*finv[i]%Mod;
    NTT(gdao,s1,1);
    int inv=Quick_Pow(s1,Mod-2);
    for(register int i=0;i<s1;i++)
        gdao[i]=1ll*gdao[i]*inv%Mod;
    GetJi(gdao,g,n);
    return ;
}
inline void GetExp(int*f,int*g,const int n){
    static int gp[N<<3],gpln[N<<3],tmp[N<<3];
    g[0]=1;
    for(register int len=1,t=0;len<(n<<1);len<<=1,t++){
        int s1=len<<1,pos=t+1;
        for(register int i=0;i<s1;i++){
            gp[i]=g[i];
            tmp[i]=f[i];
            gpln[i]=0;
        }
        GetLn(gp,gpln,len);
        s1<<=1,pos++;
        for(register int i=len<<1;i<s1;i++)
            gp[i]=tmp[i]=gpln[i]=0;
        for(register int i=0;i<s1;i++)
            rev[i]=(rev[i>>1]>>1)|((i&1)<<(pos-1));
        NTT(gp,s1,0);NTT(gpln,s1,0);NTT(tmp,s1,0);
        for(register int i=0;i<s1;i++){
            int gl=(gpln[i]-tmp[i]+Mod)%Mod;
            g[i]=(gp[i]-1ll*gl*gp[i]%Mod+Mod)%Mod;
        }
        NTT(g,s1,1);
        int inv=Quick_Pow(s1,Mod-2);
        for(register int i=0;i<s1;i++)
            g[i]=1ll*g[i]*inv%Mod;
        for(register int i=len<<1;i<s1;i++)
            g[i]=0;
    }
    return ;
}
inline void GetSqr(int*f,int*g,const int n){
    static int gp[N<<3],gpinv[N<<3],tmp[N<<3];
    g[0]=1;
    for(register int len=1,t=0;len<(n<<1);len<<=1,t++){
        int s1=len<<1,pos=t+1;
        for(register int i=0;i<s1;i++){
            gp[i]=g[i];
            tmp[i]=f[i];
        }
        GetInv(gp,gpinv,len);
        s1<<=1,pos++;
        for(register int i=len<<1;i<s1;i++)
            gp[i]=tmp[i]=gpinv[i]=0;
        for(register int i=0;i<s1;i++)
            rev[i]=(rev[i>>1]>>1)|((i&1)<<(pos-1));
        NTT(gp,s1,0);NTT(tmp,s1,0);NTT(gpinv,s1,0);
        for(register int i=0;i<s1;i++){
            g[i]=(tmp[i]+1ll*gp[i]*gp[i]%Mod)%Mod;
            g[i]=1ll*g[i]*INV2%Mod*gpinv[i]%Mod;
        }
        NTT(g,s1,1);
        int inv=Quick_Pow(s1,Mod-2);
        for(register int i=0;i<s1;i++)
            g[i]=1ll*g[i]*inv%Mod;
        for(register int i=len<<1;i<s1;i++)
            g[i]=0;
    }
    return ;
}
inline void GetPow(int*f,int*g,const int n,const int k){
    static int fln[N<<3];
    GetLn(f,fln,n);
    for(register int i=0;i<n;i++)
        fln[i]=1ll*fln[i]*k%Mod;
    GetExp(fln,g,n);
    return ;
}
inline void GetDiv(int*A,int*B,int*f,const int n,const int m){
    static int Binv[N<<3];
    reverse(A,A+n+1);
    reverse(B,B+m+1);
    GetInv(B,Binv,n-m+1);
    int s1=1,pos=0;
    while(s1<=(2*n-m+2)) s1<<=1,pos++;
    for(register int i=n-m+1;i<s1;i++)
        Binv[i]=0;
    for(register int i=0;i<s1;i++)
        rev[i]=(rev[i>>1]>>1)|((i&1)<<(pos-1));
    NTT(A,s1,0);NTT(Binv,s1,0);
    for(register int i=0;i<s1;i++)
        f[i]=1ll*A[i]*Binv[i]%Mod;
    NTT(A,s1,1);NTT(f,s1,1);
    int inv=Quick_Pow(s1,Mod-2);
    for(register int i=0;i<s1;i++){
        A[i]=1ll*A[i]*inv%Mod;
        f[i]=1ll*f[i]*inv%Mod;
    }
    reverse(A,A+n+1);
    reverse(B,B+m+1);
    reverse(f,f+n-m+1);
    return ;
}
inline void GetMod(int*A,int*B,int*g,const int n,const int m){
    static int f[N<<3];
    GetDiv(A,B,f,n,m);
    int s1=1,pos=0;
    while(s1<=(n+2)) s1<<=1,pos++;
    for(register int i=0;i<s1;i++)
        rev[i]=(rev[i>>1]>>1)|((i&1)<<(pos-1));
    NTT(A,s1,0);NTT(B,s1,0);NTT(f,s1,0);
    for(register int i=0;i<s1;i++)
        g[i]=(A[i]-1ll*B[i]*f[i]%Mod+Mod)%Mod;
    NTT(A,s1,0);NTT(B,s1,0);NTT(g,s1,1);
    int inv=Quick_Pow(s1,Mod-2);
    for(register int i=0;i<s1;i++){
        A[i]=1ll*A[i]*inv%Mod;
        B[i]=1ll*B[i]*inv%Mod;
        g[i]=1ll*g[i]*inv%Mod;
    }
    return ;
}