多项式全家桶

多项式乘法

多项式全家桶的前置知识肯定就是多项式乘法了啊, 放个板子

struct NTT {
    ll wn[2][maxn],tmp1[maxn],tmp2[maxn];
    int rev[maxn];
    void get_wn(int len) {
        for(int i=2;i<=(1<<len);i<<=1) {
            ll w1=ksm(3,(mod-1)/i),w0=ksm(3,mod-1-(mod-1)/i);
            wn[1][i>>1]=wn[0][i>>1]=1;
            for(int j=1;j<(i>>1);j++) {
                wn[0][(i>>1)+j]=w0*wn[0][(i>>1)+j-1]%mod;
                wn[1][(i>>1)+j]=w1*wn[1][(i>>1)+j-1]%mod;
            }
        }
    }
    NTT(){
        int cnt=0,len=1,top=2e5+10;while(len<=top)len<<=1,cnt++;
        get_wn(cnt);
    }
    void ntt(int len,ll *c,int f){
        for(int i=0;i<len;i++)if(rev[i]>i)swap(c[i],c[rev[i]]);
        for(int l=2;l<=len;l<<=1) {
            for(int i=0;i+l<=len;i+=l) {
                for(int j=i;j<i+(l>>1);j++) {
                    ll tmpa=c[j],tmpb=c[j+(l>>1)]*wn[f][j+(l>>1)-i]%mod;
                    c[j]=tmpa+tmpb;c[j]%=mod;
                    c[j+(l>>1)]=tmpa-tmpb;c[j+(l>>1)]=(c[j+(l>>1)]%mod+mod)%mod;
                }
            }
        }
        if(!f) {
            ll inv=ksm(len,mod-2);
            for(int i=0;i<len;i++)c[i]=c[i]*inv%mod;
        }
    }
    void get_rev(int len){rep(i,1,1<<len)rev[i]=(rev[i>>1]>>1)|((i&1)<<(len-1));}
    vi mul1(const vi &a,const vi &b) {//普通多项式乘法
        int l1=a.size(),l2=b.size(),len=1,cnt=0;while(len<=l1+l2)len<<=1,cnt++;
        get_rev(cnt);rep(i,0,len)tmp1[i]=tmp2[i]=0;
        rep(i,0,l1-1)tmp1[i]=a[i];
        rep(i,0,l2-1)tmp2[i]=b[i];
        ntt(len,tmp1,1);ntt(len,tmp2,1);
        rep(i,0,len-1)tmp1[i]=tmp1[i]*tmp2[i]%mod;
        ntt(len,tmp1,0);vi re;re.clear();
        rep(i,0,len-1)re.pb(tmp1[i]);
        re.resize(l1+l2);
        return re;
    }
}t;

多项式求逆

在多项式运算中,很多时候需要用到除法,那么多项式求逆就是必不可少的了。

多项式求逆,其实就是要解决A(x)×B(x)1(modxn)A(x) \times B(x) \equiv 1\left(\bmod x^{n}\right)的问题,其中AA已知,且A00A_0 \neq 0

为什么需要保证A00A_0 \neq 0?

之所以需要保证A00A_0 \neq 0,是因为多项式对xnx^n取模实际上就是舍掉多项式大于等于nn次的项。所以如果常数项为0,那么不管模数是多少,都不可能使取模后的常数项为1,所以无解

如何求逆?

推柿子

首先我们发现,如果找出了BB'使得A(x)×B(x)1(modxn2)A(x) \times B'(x) \equiv 1 \quad\left(\bmod x^{\lceil\frac{n}{2}\rceil}\right)

那么显然有A(x)×B(x)1(modxn2)A(x) \times B(x) \equiv 1 \quad\left(\bmod x^{\lceil\frac{n}{2}\rceil}\right),因为BB现在的模数是原来模数的因子。

因此B(x)B(x)(modxn2)B(x) \equiv B^{\prime}(x) \quad\left(\bmod x^{\left\lceil\frac{n}{2}\right\rceil}\right)

然后:

B(x)B(x)0(modxn2)B(x)-B'(x)\equiv0 \quad\left(\bmod x^{\left\lceil\frac{n}{2}\right\rceil}\right)\\

因此这个多项式后xn2x^{\left\lceil\frac{n}{2}\right\rceil}项均为0,然后这个柿子平方一下就是:

B(x)22B(x)B(x)+B(x)20(modxn)B(x)^{2}-2 B(x) B^{\prime}(x)+B^{\prime}(x)^{2} \equiv 0 \quad\left(\bmod x^{n}\right) (因为平方之后后n项均为0)

我们想得到B和B'的关系柿,那么就随便搞搞:

B(x)2B(x)+B(x)2A(x)0(modxn)2B(x)B(x)2A(x)B(x)(modxn)\begin{aligned} B(x)-2 B^{\prime}(x)+B^{\prime}(x)^{2} A(x) & \equiv 0 \quad\left(\bmod x^{n}\right) \\ 2 B^{\prime}(x)-B^{\prime}(x)^{2} A(x) & \equiv B(x) \quad\left(\bmod x^{n}\right) \end{aligned}

然后就没了 写一个递归多项式乘法就好了。实现上有个小技巧 ,就是多项式乘法这里有一个二次的BB'。我们可以直接在转换为点值表示之后的乘法里下功夫,具体看代码吧。

代码实现的时候需要注意一个比较严重的问题 就是这个多项式中有一个B(x)2A(x)B'(x)^2A(x),所以我们在NTT初始化计算长度的时候的时候要注意长度需要给到2len(B)+len(A)2*len(B')+len(A')也就是当前层的2n2n

多项式对数函数(多项式ln)

多项式对数函数,其实就是要解决B(x)lnA(x)(modxn)B(x) \equiv \ln A(x)\left(\bmod x^{n}\right)的问题,其中AA已知,且A0=1A_0=1

为什么需要保证A0=1A_0=1?

因为众所周知,对数函数的函数图像定点是(1,0)(1,0)

如何求对数函数?

推柿子

我们把对数函数设成FF,则有B(x)F(A(x))(modxn)B(x) \equiv F( A(x))\left(\bmod x^{n}\right)

由微积分里面的链式法则,两边求一下导,就有了B(x)F(A(x))A(x)(modxn)B'(x) \equiv F'( A(x))\cdot A'(x)\left(\bmod x^{n}\right)

我们知道对数函数的导函数是F(x)=1xF'(x)=\frac{1}{x},那么就有B(x)A(x)A(x)(modxn)B'(x) \equiv \frac{A'(x)}{A(x)}\left(\bmod x^{n}\right)

上面的分子利用多项式求导能很方便的求出来:xa=axa1x^{a^{\prime}}=a x^{a-1},如果带了系数的话,那bxa=baxa1bx^{a^{\prime}}=ba x^{a-1},这个可以用链式法则解释。

下面的部分多项式求个逆序也很简单。

然后我们就得到了B(x)B'(x)这个多项式,接着不定积分一波就没了。xadx=1a+1xa+1\int x^{a} d x=\frac{1}{a+1} x^{a+1}

多项式指数函数(多项式exp)

前置知识

泰勒展开

我们发现,对于一个多项式求导,会使其丢失常数项的信息。

有一句话说得很好:原函数的信息 = 导函数的信息 + 初始值信息

具体的引入有一篇知乎答案 怎样更好地理解并记忆泰勒展开式?这里就不细说了。

总的来说 就是把一个多项式展开成无穷级数的样子。

最后推导出来的公式就是:H(x)=i0H(i)(x0)i!(xx0)iH(x)=\sum_{i \geq 0} \frac{H^{(i)}\left(x_{0}\right)}{i !}\left(x-x_{0}\right)^{i},其中H(i)H^{(i)}代表函数HHii阶导,x0x_0为我们选择的展开点。

牛顿迭代

已知G[F(x)]0(modxn)G[F(x)] \equiv 0\left(\bmod x^{n}\right),给出GG,求出FF。其实就是求GG这个函数的零点。

大体的思路就是求在模一个很小的数意义下的FF,然后逆用泰勒展开 看看如何转换才能使模数变大。

我们令Ft(x)F_{t}(x)表示经过 t 次迭代之后的 F(x)F(x),满足G[Ft(x)]0(modx2t)G\left[F_{t}(x)\right] \equiv 0 \quad\left(\bmod x^{2^{t}}\right)

考虑将 $G[F_{t+1}(x)] F_t(x) $处展开:

G[Ft+1(x)]=i0G(i)[Ft(x)]i![Ft+1(x)Ft(x)]i=G[Ft(x)]+G[Ft(x)]×[Ft+1(x)Ft(x)]+i2\begin{aligned} G\left[F_{t+1}(x)\right] &=\sum_{i \geq 0} \frac{G^{(i)}\left[F_{t}(x)\right]}{i !}\left[F_{t+1}(x)-F_{t}(x)\right]^{i} \\ &=G\left[F_{t}(x)\right]+G^{\prime}\left[F_{t}(x)\right] \times\left[F_{t+1}(x)-F_{t}(x)\right]+\sum_{i \geq 2} \cdots \end{aligned}

因为i2i\geq2的时候,[Ft+1(x)Ft(x)]i\left[F_{t+1}(x)-F_{t}(x)\right]^i的次数是大于等于22的,而且这两项在modx2t\bmod x^{2^t}意义下都是0,所以差也是0,差的平方就会在modx2t+1\bmod x^{2^{t+1}}意义下变成0。

所以后面那一坨一定是0,来看前面的部分,就有

0G[Ft(x)]+G[Ft(x)]×[Ft+1(x)Ft(x)](modx2t+1)0 \equiv G\left[F_{t}(x)\right]+G^{\prime}\left[F_{t}(x)\right] \times\left[F_{t+1}(x)-F_{t}(x)\right] \quad\left(\bmod x^{2^{t+1}}\right)

然后有:

Ft+1(x)Ft(x)G[Ft(x)]G[Ft(x)](modx2t+1)F_{t+1}(x) \equiv F_{t}(x)-\frac{G\left[F_{t}(x)\right]}{G^{\prime}\left[F_{t}(x)\right]} \quad\left(\bmod x^{2^{t+1}}\right)

就没啦~~~

如何求指数函数?

多项式指数函数,其实就是要解决A(x)expB(x)(modxn)A(x) \equiv \exp B(x)\left(\bmod x^{n}\right)的问题,其中BB已知,且保证B0=0B_0=0

我们令G[A(x)]=lnA(x)B(x)G[A(x)]=\ln A(x)-B(x)。需要注意的是 这个柿子里面A(x)A(x)这个多项式是自变量,B(x)B(x)这个多项式是常数。(看起来很玄学 其实是蛮有道理的,很多多项式算法都是把一个多项式当作一个变量来看待,也就是形式幂级数)。

然后牛顿迭代一波:

G[A(x)]=1A(x)Ft+1(x)Ft(x)G[Ft(x)]G[Ft(x)](modx2t+1)Ft(x)[1lnFt(x)+B(x)](modx2t+1)\begin{aligned} G^{\prime}[A(x)] &=\frac{1}{A(x)} \\ F_{t+1}(x) & \equiv F_{t}(x)-\frac{G\left[F_{t}(x)\right]}{G^{\prime}\left[F_{t}(x)\right]} \quad\left(\bmod x^{2^{t+1}}\right) \\ & \equiv F_{t}(x)\left[1-\ln F_{t}(x)+B(x)\right] \quad\left(\bmod x^{2^{t+1}}\right) \end{aligned}

在最底层的时候,模数是xx,因此零点就是11。(ln1=0,B(0)=0\ln 1=0,B(0)=0,所以G(1)=0G(1)=0,这也是为什么需要保证B0=0B_0=0)

就没啦~~~

P.S. 在实际写代码的时候,对于模数可以向下递归,不停的除二且向上取整就行。因为你只要保证前一次的模数平方之后是大于现在的模数的就行了。

多项式全家桶代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
#include<queue>
#define vi vector<int>
#define pb push_back
#define mk make_pair
#define pii pair<int,int>
#define rep(i,a,b) for(int i=(a),i##end=(b);i<=i##end;i++)
#define fi first
#define se second
typedef long long ll;
using namespace std;
const int maxn=2e5*4+1000;
const int mod=998244353;
int ksm(ll num,ll t) {
    int res=1;
    for(;t;t>>=1,num=1ll*num*num%mod) {
        if(t&1)res=1ll*res*num%mod;
    }
    return res%mod;
}
struct NTT {
    ll wn[2][maxn],tmp1[maxn],tmp2[maxn];
    int rev[maxn];
    void get_wn(int len) {
        for(int i=2;i<=(1<<len);i<<=1) {
            ll w1=ksm(3,(mod-1)/i),w0=ksm(3,mod-1-(mod-1)/i);
            wn[1][i>>1]=wn[0][i>>1]=1;
            for(int j=1;j<(i>>1);j++) {
                wn[0][(i>>1)+j]=w0*wn[0][(i>>1)+j-1]%mod;
                wn[1][(i>>1)+j]=w1*wn[1][(i>>1)+j-1]%mod;
            }
        }
    }
    NTT(){
        int cnt=0,len=1,top=maxn/2-100;while(len<=top)len<<=1,cnt++;
        get_wn(cnt);
    }
    void ntt(int len,ll *c,int f){
        for(int i=0;i<len;i++)if(rev[i]>i)swap(c[i],c[rev[i]]);
        for(int l=2;l<=len;l<<=1) {
            for(int i=0;i+l<=len;i+=l) {
                for(int j=i;j<i+(l>>1);j++) {
                    ll tmpa=c[j],tmpb=c[j+(l>>1)]*wn[f][j+(l>>1)-i]%mod;
                    c[j]=tmpa+tmpb;c[j]%=mod;
                    c[j+(l>>1)]=tmpa-tmpb;c[j+(l>>1)]=(c[j+(l>>1)]%mod+mod)%mod;
                }
            }
        }
        if(!f) {
            ll inv=ksm(len,mod-2);
            for(int i=0;i<len;i++)c[i]=c[i]*inv%mod;
        }
    }
    void get_rev(int len){rep(i,1,1<<len)rev[i]=(rev[i>>1]>>1)|((i&1)<<(len-1));}
    vi mul1(const vi &a,const vi &b,const int &mx) {//普通多项式乘法
        int l1=a.size(),l2=b.size(),len=1,cnt=0;l1=min(l1,mx),l2=min(l2,mx);while(len<=l1+l2)len<<=1,cnt++;
        get_rev(cnt);rep(i,0,len)tmp1[i]=tmp2[i]=0;
        rep(i,0,l1-1)tmp1[i]=a[i];
        rep(i,0,l2-1)tmp2[i]=b[i];
        ntt(len,tmp1,1);ntt(len,tmp2,1);
        rep(i,0,len-1)tmp1[i]=tmp1[i]*tmp2[i]%mod;
        ntt(len,tmp1,0);vi re;re.clear();
        rep(i,0,len-1)re.pb(tmp1[i]);
        re.resize(mx);
        return re;
    }
    vi mul2(const vi &a,const vi &b,const int &mx) {//多项式求逆用到的多项式乘法(唯一的不同是点值)
        int l1=a.size(),l2=b.size(),len=1,cnt=0;l1=min(l1,mx),l2=min(l2,mx);while(len<=l1+l2)len<<=1,cnt++;
        get_rev(cnt);rep(i,0,len)tmp1[i]=tmp2[i]=0;
        rep(i,0,l1-1)tmp1[i]=a[i];
        rep(i,0,l2-1)tmp2[i]=b[i];
        ntt(len,tmp1,1);ntt(len,tmp2,1);
        rep(i,0,len-1)tmp1[i]=((tmp2[i]*2-tmp2[i]*tmp2[i]%mod*tmp1[i]%mod)%mod+mod)%mod;
        ntt(len,tmp1,0);vi re;re.clear();
        rep(i,0,len-1)re.pb(tmp1[i]);
        re.resize(mx);
        return re;
    }
}t;
vi get_inv(const vi &a,int n){
    if(n==1){vi re;re.clear();re.pb(ksm(a[0],mod-2));return re;}
    vi b_=get_inv(a,(n+1)>>1);b_.resize(n);vi a_=a;a_.resize(n);
    return t.mul2(a_,b_,n);
}
vi der(vi a) {//多项式求导
    for(int i=1;i<a.size();i++)a[i-1]=1ll*a[i]*i%mod;
    a.resize(a.size()-1);
    return a;
}
vi inte(vi a) {//多项式积分
    a.resize(a.size()+1);
    for(int i=a.size()-1;i>0;i--)a[i]=(1ll*a[i-1]*ksm(i,mod-2)%mod)%mod;
    a[0]=0;
    return a;
}
vi ln(const vi &a,int n) {
    vi u=der(a),d=get_inv(a,n);
    vi bder=t.mul1(u,d,n);
    vi ans=inte(bder);ans.resize(n);
    return ans;
}
vi exp(const vi &a,int n) {
    if(n==1){vi re;re.pb(1);return re;}
    vi last=exp(a,(n+1)>>1);
    vi ln_=ln(last,n);
    for(int i=0;i<n;i++)ln_[i]=((a[i]-ln_[i])%mod+mod)%mod;
    ln_[0]++;
    ln_=t.mul1(ln_,last,n);
    return ln_;
}
int main(){
    int n;scanf("%d",&n);
    vi a;rep(i,1,n){int u;scanf("%d",&u);a.pb(u);}
    a=exp(a,n);
    rep(i,1,n){printf("%d ",a[i-1]);}
    return 0;
}