最后面有约定, 里面有几个比较通用的函数, 建议先看.

多项式表示

形式幂级数 .

不妨定义一个有 $n+1$ 项的多项式 $F(x)=f_0x^0+f_1x^1+\dots+f_nx^n=\sum_{i=0}^n f_ix^i$. 发现这个式子和形式幂级数很像, 如果 $\forall i>n,f_i=0$, 然后把 $F(x)$ 取到 $\infty$ 项, 那就是形式幂级数了, 所以可以用形式幂级数之类的东西来搞多项式.
当然对于 $F(x)$ 或者 $f(x)$ 这样的大小写问题窝也还没听到什么统一的说法, 不过窝个人的习惯是用 $F(x)$ 来代表一个多项式,$f(x_0)$ 代表当 $x=x_0$ 时的取值.

多项式乘法

FFT 和NTT都能弄.

多项式求逆

定义 $F(x)$ 的逆 $G(x)$ 满足

$$ F(x)G(x)\equiv1\pmod{x^n} $$

模板(times()要魔改, 建议 全 文 背 诵 )

inline void times(int *a,int *b,int m) {
    using namespace NTTspace;
    int n=1; for (;n<m;n<<=1);
    NTT(a,n,false,true); NTT(b,n,false);
    for (int i=0;i<n;++i)
        a[i]=(2ll-(ll)a[i]*b[i]%jly+jly)%jly*a[i]%jly;
    NTT(a,n,true);
}

void getinv(int *a,int *b,int m) { /*从a[]里传进来,求逆的结果在b[]里*/
    if (m==1) {b[0]=ksm(a[0],jly-2); return;}
    static int c[400005];
    getinv(a,b,(m+1)>>1);
    int n=1; for (;n<(m<<1);n<<=1);
    memset(c,0,sizeof(int)*n);
    memcpy(c,a,sizeof(int)*m);
    times(b,c,n);
    for (int i=m;i<n;++i) b[i]=0;
}

多项式 $\ln$

求

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

推式子有

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

然后多项式求导求逆就完了.

这次把原来的times()用上了, 魔改的变成了pimes(). 模板

void getinv(int *a,int *b,int m) {
    ...
    pimes(b,c,n); /*就是求逆里面的times()*/
    ...
}

inline void getln(int *a,int m) {
    static int b[400005],c[400005];
    for (int i=1;i<m;++i) b[i-1]=(ll)a[i]*i%jly;
    b[m-1]=0; getinv(a,c,m);
    times(b,c,m<<1); a[0]=0;
    for (int i=1;i<m;++i) a[i]=(ll)b[i-1]*ksm(i,jly-2)%jly;
}

几个约定

因为放在前面会有点长... 就放在最后好了.

typedef long long ll;
const int jly=998244353;

inline int ksm(int a,int b) {
    int r=1;
    while (b) {
        if (b&1) r=(ll)r*a%jly;
        a=(ll)a*a%jly; b>>=1;
    }
    return r;
}

inline int mjly (int x) {
    return x<jly?x:x-jly;
}

namespace NTTspace {
    const int grt=3;
    int qow[400005],inv[400005];

    inline void NTT(int *a,int n,bool f,bool u=false) {
        static int k,r[400005];
        int g0,gx,b,c;
        if (u) {
            k=0;
            for (int i=2;i<n;i<<=1) ++k;
            for (int i=0;i<n;++i)
                r[i]=(r[i>>1]>>1)|((i&1)<<k);
        }
        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) {
            g0=f?inv[i<<1]:qow[i<<1];
            for (int j=0;j<n;j+=(i<<1)) {
                gx=1;
                for (int k=0;k<i;++k) {
                    b=a[j+k]; c=(ll)gx*a[i+j+k]%jly;
                    a[j+k]=mjly(b+c); a[i+j+k]=mjly(b-c+jly);
                    gx=(ll)g0*gx%jly;
                }
            }
        }
        if (f) {
            int iv=ksm(n,jly-2);
            for (int i=0;i<n;++i)
                a[i]=(ll)a[i]*iv%jly;
        }
    }
}

inline void init() {
    using namespace NTTspace;
    int iv=ksm(grt,jly-2);
    for (int i=1;i<262145;i<<=1) {
        qow[i]=ksm(grt,(jly-1)/i);
        inv[i]=ksm(iv,(jly-1)/i);
    }
}

inline void times(int *a,int *b,int m) {
    using namespace NTTspace;
    int n=1; for (;n<m;n<<=1);
    NTT(a,n,false,true); NTT(b,n,false);
    for (int i=0;i<n;++i) a[i]=(ll)a[i]*b[i]%jly;
    NTT(a,n,true);
}