多项式小结

未完待续……

Orz great_influence

树套树每套一层就多一个log，但是多项式可以倍增随便套都可以分析得$O(n\log n)$，瑟瑟发抖

0. 定义

deg(F)表示F(x)的次数。

$F_r(x)=x^{deg(F)}F(\frac{1}{x})$也就是把系数反转。

1. 多项式乘法

就是FFT/NTT。传送门

2. 多项式求逆

给定$F(x)$，求$G(x)$使得$F(x)G(x)\equiv1\pmod {x^n}$

倍增。假设我们求出来了$G_1(x)$使得$F(x)G_1(x)\equiv 1\pmod{x^{\lceil\frac{n}{2}\rceil}}$

$$ G(x)-G_1(x)\equiv 0\pmod{x^{\lceil\frac{n}{2}\rceil}}\\ (G(x)-G_1(x))^2\equiv 0\pmod{x^n}\\ G^2(x)-2G(x)G_1(x)+G_1(x)\equiv 0\pmod{x^n}\\ F(x)(G^2(x)-2G(x)G_1(x)+G_1^2(x))\equiv 0\pmod{x^n}\\ G(x)-2G_1(x)+F(x)G_1^2(x)\equiv 0\pmod{x^n}\\ G(x)\equiv 2G_1(x)-F(x)G_1^2(x)\pmod{x^n} $$

递归计算即可。根据主定理$T(n)=T(\frac{n}{2})+O(n\log n)=O(n\log n)$

3. 多项式除法

给定$F(x),G(x)$，求$Q(x),R(x)$使得$Q(x)G(x)+R(x)=F(x)$，其中$deg(R)<deg(G)$。

设$deg(F)=n,deg(G)=m$，则$deg(Q)=n-m,deg(R)=m-1$（r的高次补0）

$$ Q(x)G(x)+R(x)=F(x)\\ Q(\frac{1}{x})G(\frac{1}{x})+R(\frac{1}{x})=F(\frac{1}{x})\\ x^n(Q(\frac{1}{x})G(\frac{1}{x})+R(\frac{1}{x}))=x^n(F(\frac{1}{x}))\\ Q_r(x)G_r(x)+R_r(x)(x^{n-m+1})=F_r(x) $$

由于$deg(Q)=n-m$，

$$ Q_r(x)G_r(x)\equiv F_r(x)\pmod{x^{n-m+1}}\\ Q_r(x)\equiv F_r(x)\cdot G_r^{-1}(x)\pmod{x^{n-m+1}} $$

求逆乘完以后需要反转回来。

什么？R？直接$R=F-GQ$就可以了啊。

还是$O(n\log n)$

4. 多项式sqrt

给定$F(x)$，求$G(x)$使得$G^2(x)\equiv F(x)\pmod {x^n}$

还是倍增。假设求出来了$G_1(x)$使得$G_1^2(x)\equiv F(x)\pmod{x^{\lceil\frac{n}{2}\rceil}}$

$$ G(x)\equiv G_1(x)\pmod{x^{\lceil\frac{n}{2}\rceil}}\\ G(x)-G_1(x)\equiv 0 \pmod{x^{\lceil\frac{n}{2}\rceil}}\\ (G(x)-G_1(x))^2\equiv 0 \pmod {x^{\lceil\frac{n}{2}\rceil}}\\ G^2(x)-2G_1(x)G(x)+G_1^2(x)\equiv 0 \pmod{x^n}\\ F(x)-2G_1(x)G(x)+G_1^2(x)\equiv 0 \pmod{x^n}\\ G(x)\equiv \frac{F(x)+G_1^2(x)}{2G_1(x)} $$

复杂度依然$O(n\log n)$

5. 多项式求导、积分

给定$F(x)$，求$F'(x)$和$\int F(x)$。

设$F(x)=\sum\limits_{i=0}^na_ix^i$，则$F'(x)=\sum_{i=1}^nia_ix^{i-1}$，$\int F(x)=\sum_{i=0}^n \frac{a_ix^{i+1}}{i+1}$

6. 多项式ln

给定$F(x)$，求$G(x)\equiv\ln F(x)\pmod {x^n}$。

由于$G'(x)=ln' F(x)=\frac{F'(x)}{F(x)}$（链式法则），$G(x)=\int\frac{F'(x)}{F(x)}$。

时间复杂度$O(n\log n)$

7. 多项式牛顿迭代

给定$F$，求$G(x)$使得$F(G(x))\equiv 0\pmod {x^n}$

倍增。

已知$F(G_1(x))\equiv 0 \pmod{x^{\lceil\frac{n}{2}\rceil}}$。

在$G_1(x)$这点泰勒展开$F(G(x))=F(G_1(x))+\frac{F'(G_1(x))}{1!}(G(x)-G_1(x))+\frac{F''(G_1(x))}{2!}(G(x)-G_1(x))^2+\cdots$。

显然$G(x)-G_1(x)\equiv 0\pmod{x^{\lceil\frac{n}{2}\rceil}}$

那么$(G(x)-G_1(x))^2\equiv \pmod{x^n}$，所以后面的项就不用管了。

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

​ 时间复杂度仍然是$O(n\log n)$

8. 多项式exp

给定$F(x)$，求$G(x)\equiv e^{F(x)}\pmod{x^n}$。

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

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

设$H(G(x))=\ln(G(x))-F(x)$，显然$H'(G(x))\equiv \frac{1}{G(x)}\pmod{x^n}$。

牛顿迭代，直接可以得到$G(x)\equiv G'(x)(1-\ln G(x)+F(x))$。

时间复杂度当然还是$O(n\log n)$

9. 多项式幂次

给定$F(x),k$，求$G(x)\equiv F^k(x)\pmod{x^n}$

$F^k(x)=e^{k\ln F(x)}$，时间复杂度$O(n\log n)$

10. 例题

#### 1.【模板】多项式乘法

FFT模板。

2.【模板】多项式求逆

求逆模板。

3.【模板】多项式除法

除法模板

4.CF438E 小朋友与二叉树

多项式开根。题解

5.【模板】多项式对数函数

多项式ln模板

6.【模板】多项式指数函数

多项式exp模板

7. COGS2189 帕秋莉的超级多项式

一个集合了大部分多项式操作的模板。

所有操作的模板以及这题的题解：

/*
Author: CNYALI_LK
LANG: C++
PROG: polynomial.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
#define x first
#define y second
using namespace std;
const double eps=1e-8;
const double pi=acos(-1.0);
typedef long long ll;
typedef pair<ll,ll> pii;
template<class T>ll chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>ll chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
#define min mmin
#define max mmax
#define abs aabs
ll read(){
    ll s=0,base=1;
    char c;
    while(!isdigit(c=getchar()))if(c=='-')base=-base;
    while(isdigit(c)){s=s*10+(c^48);c=getchar();}
    return s*base;
}
namespace Polynomial{
    const ll p=998244353,g_=3;
    ll rev[266667];
    ll fpm(ll a,ll b){
        ll c=1;
        while(b){
            if(b&1)c=c*a%p;
            a=a*a%p;
            b>>=1;
        }
        return c;
    }
    void Rev(ll n,ll *f){
        for(ll i=0;i<=n&&i<n-i;++i)swap(f[i],f[n-i]);
    }
    void NTT(ll *f,ll n,ll flag){
        for(ll i=1;i<n;++i){
            rev[i]=(rev[i>>1]>>1)|((i&1)*(n>>1));
            if(i<rev[i])swap(f[i],f[rev[i]]);
        }
        for(ll i=1;i<n;i<<=1){
            ll ww=fpm(g_,flag*((p-1)/(i+i))+p-1);
            for(ll j=0;j<n;j+=i+i){
                ll w=1,u,v; 
                for(ll k=0;k<i;++k){
                    u=f[j+k];v=f[j+k+i]*w%p;
                    f[j+k]=(u+v)%p;
                    f[j+k+i]=(u-v+p)%p;
                    w=w*ww%p;
                }
            }
        }
        if(!~flag){
            ll in=fpm(n,p-2);
            for(ll i=0;i<n;++i)f[i]=f[i]*in%p;
        }
    }
    ll f1[266667],g1[266667];
    void Mul(ll n,ll *f,ll m,ll *g,ll *h){//卷积
        ll N=1;
        while(N<=n+m)N<<=1;
        for(ll i=0;i<N;++i){f1[i]=f[i];if(i>n)f[i]=0;}
        for(ll i=0;i<N;++i){g1[i]=g[i];if(i>m)g[i]=0;}
        NTT(f,N,1);
        if(f!=g)NTT(g,N,1);
        for(ll i=0;i<N;++i)h[i]=f[i]*g[i]%p;
        NTT(h,N,-1);
        if(f!=h){for(ll i=0;i<N;++i)f[i]=f1[i];}
        if(g!=h){for(ll i=0;i<N;++i)g[i]=g1[i];}
    }
    /*
1: Inv
2: Div ln
3. Sqrt exp
4. Sqrt Pow
*/
    ll h1[266667],h2[266667],h3[266667],h4[266667];
    void Inv(ll n,ll *f,ll *g){//求逆
        if(n==1){
            g[0]=fpm(*f,p-2);
            g[1]=g[2]=g[3]=0;
            return;
        }
        else{
            ll m=(n+1)>>1;
            Inv(m,f,g);
            ll N=1;
            while(N<=n+m+m-3)N<<=1;
            for(ll i=0;i<N;++i){f1[i]=f[i];if(i>=n)f[i]=0;if(i>=m)g[i]=0;}
            NTT(f,N,1);
            NTT(g,N,1);
            for(ll i=0;i<N;++i)g[i]=(g[i]+g[i]-g[i]*g[i]%p*f[i]%p+p)%p;
            NTT(g,N,-1);
            for(ll i=0;i<N;++i)f[i]=f1[i];
            for(ll i=n;i<N;++i)g[i]=0;
        }
    }
    void Div(ll n,ll *f,ll m,ll *g,ll *q,ll *r){//除法
        Rev(n,f);
        Rev(m,g);
        Inv(n-m+1,g,h2);
        for(ll i=n-m+1;i<=n+n-m-m+2;++i)q[i]=0;
        Rev(n,f);
        Rev(m,g); 
        Rev(n-m,q);
        Mul(m,g,n-m,q,r);
        for(ll i=0;i<=n;++i){r[i]=(f[i]-r[i]+p)%p;}
    }
    void Sqrt(ll n,ll *f,ll *g){//开根
        if(n==1){
            g[0]=(ll)(sqrt(f[0])+0.5);
            g[1]=0;
        }
        else{
            ll m;
            Sqrt(m=(n+1)>>1,f,g);
            Mul(m-1,g,m-1,g,h3);
            if(n-1>m+m-2)h3[n-1]=0;
            for(ll i=0;i<n;++i)h3[i]=(h3[i]+f[i])%p;
            for(ll i=0;i<m;++i)g[i]=g[i]*2%p;
            Inv(n,g,h4);
            Mul(n-1,h4,n-1,h3,g);
            for(ll i=n;i<n+n;++i)g[i]=0;
        }
    }
    ll inv[266667];
    void Integ(ll n,ll *f,ll *g){//积分
        inv[1]=1;
        for(ll i=2;i<=n+1;++i)inv[i]=(p-p/i)*inv[p%i]%p;
        for(ll i=n;~i;--i)g[i+1]=f[i]*inv[i+1]%p;
        g[0]=0;
    }
    void Deriv(ll n,ll *f,ll *g){//求导
        for(ll i=1;i<=n;++i)g[i-1]=f[i]*i%p;
        g[n]=0;
    }
    void ln(ll n,ll *f,ll *g){//对数
        Inv(n,f,h2);
        Deriv(n-1,f,g);
        Mul(n-1,h2,n-2,g,g);
        for(ll i=n-1;i<=n+n-3;++i)g[i]=0;
        Integ(n-2,g,g);
    }
    void exp(ll n,ll *f,ll *g){//指数
        if(n==1){
            g[0]=1;
            g[1]=0;
        }
        else{
            exp((n+1)>>1,f,g);
            ln(n,g,h3);
            for(int i=0;i<n;++i){
                h3[i]=(f[i]-h3[i]+p)%p;
            }
            h3[0]=(h3[0]+1)%p;
            Mul(n-1,h3,(n-1)>>1,g,g);
            for(int i=n;i<n+n;++i)g[i]=0;
        }
    }
    void Pow(ll n,ll *f,ll k,ll *g){//幂次
        ln(n,f,h4);
        for(ll i=0;i<n;++i)h4[i]=(h4[i]*k)%p;
        exp(n,h4,g);
    }
}
using namespace Polynomial;
ll f[266667],g[266667],h[266667];
int main(){
    freopen("polynomial.in","r",stdin);
    freopen("polynomial.out","w",stdout);
    ll n,m,k;
    n=read();
    k=read();
    for(ll i=0;i<n;++i)f[i]=read();
    Sqrt(n,f,g);
    Inv(n,g,f);
    Integ(n-1,f,f);
    f[n]=0;
    exp(n,f,g);
    Inv(n,g,f);
    f[0]=(f[0]+1)%p;
    ln(n,f,g);
    g[0]=(g[0]+1)%p;
    Pow(n,g,k,f);
    Deriv(n-1,f,f);
    for(ll i=0;i<n;++i)printf("%lld%c",f[i],i==n-1?'\n':' ');   

    return 0;
}