多项式小结

· · 个人记录

多项式小结

会过 。 ---XXX

多项式乘法

NTT，FFT，不多说了。

多项式求逆

考虑递归求解。

现求 F(x)^{-1} ，若当前已有 F(x)G(x) \equiv 1~(mod~x^{\frac{n}{2}}) 。

则，

\begin{aligned} F(x)G(x) &\equiv 1~(mod~x^{\lceil\frac{n}{2}\rceil})\\ F(x)G(x)-1 &\equiv 0~(mod~x^{\lceil\frac{n}{2}\rceil})\\ 2F(x)G(x)-F^2(x)G^2(x) &\equiv1~(mod~x^{n})\\ F(x)^{-1}&\equiv 2G(x)-F(x)G^2(x)~(mod~x^{n})\\ \end{aligned}

最后一步是两边同时乘上 F(x)^{-1}。

void Finv(int n,LL *F,LL *G) {//G=F^(-1)
    if(n==1){G[0]=qpow(F[0],P-2);return;}
    Finv((n+1)>>1,F,G);//注意是向上取整
    int len=0;while((1<<len)<(n<<1))++len;
    for(int i=0;i<n;++i)C[i]=F[i];
    for(int i=n;i<(1<<len);++i)C[i]=0;//一定要清空
    NTT(C,len,1);NTT(G,len,1);
    for(int i=0;i<(1<<len);++i)G[i]=(2-C[i]*G[i]%P+P)%P*G[i]%P;
    NTT(G,len,-1);
    for(int i=n;i<(1<<len);++i)G[i]=0;//一定要清空
}

多项式开根

依旧是考虑递归求解。

现求 G(x) 满足 G(x)^2 \equiv F(x)~(mod~x^{n})，若已有 H(x)^2 \equiv F(x)~(mod~x^{\lceil\frac{n}{2}\rceil})。

\begin{aligned} H(x) &\equiv G(x)~(mod~x^{\lceil\frac{n}{2}\rceil})\\ (H(x)-G(x))^2&\equiv 0~(mod~x^{n})\\ H^2(x)+G^2(x)-2H(x)G(x)&\equiv 0~(mod~x^{n})\\ G(x)&\equiv \frac{H^2(x)+G^2(x)}{2H(x)}~(mod~x^n)\\ G(x)&\equiv \frac{H^2(x)+F(x)}{2H(x)}~(mod~x^n)\\ \end{aligned}

最后一步是因为 G(x)^2 \equiv F(x)~(mod~x^{n}) ，注意到 H(x)^2 \ne F(x)~(mod~x^{n})。

多项式开根要求常数项一定要是1。

void Fsqrt(int n,LL *F,LL *G) {
    if(n==1){G[0]=1;return;}
    Fsqrt((n+1)>>1,F,G);
    int len=0;while((1<<len)<(n<<1))++len;
    for(int i=0;i<n;++i)C[i]=F[i];
    for(int i=n;i<(1<<len);++i)C[i]=0;
    for(int i=0;i<(1<<len);++i)Ni[i]=D[i]=0;//注意清空
    Finv(n,G,Ni);
    NTT(C,len,1);NTT(G,len,1);NTT(Ni,len,1);
    for(int i=0;i<(1<<len);++i)
        G[i]=(C[i]+G[i]*G[i]%P)*Ni[i]%P*inv2%P;
    NTT(G,len,-1);
    for(int i=n;i<(1<<len);++i)G[i]=0;
}

多项式 \ln

求 G(x) \equiv \ln(F(x))。

首先要会一点求导。

\begin{aligned} G(x) &\equiv \ln(F(x))\\ G'(x) &\equiv F'(x)F(x)^{-1} \\ \end{aligned}

具体实现就是求导算 F'(x)，求逆算 F(x)^{-1}，乘起来算 G'(x) ，再积分算出 G(x)。

关于多项式求导，其实是逐项求导再加起来。

若 F(x)=\sum_{i=0}^{n}a_ix^i\\，则 F'(x)=\sum_{i=0}^{n-1}a_{i+1}(i+1)x^i。

若 F'(x)=\sum_{i=0}^{n-1}a_ix^i\\，则 F(x)=0+\sum_{i=1}^{n}\frac{a_{i-1}}{i}x^i。

多项式 \ln 要求常数项是 0。

void Fln(int n,LL *F,LL *G){
    Finv(n,F,Ni);
    for(int i=0;i<n-1;++i)DF[i]=F[i+1]*(i+1)%P;
    int len=0;while((1<<len)<(n<<1))++len;
    NTT(Ni,len,1);NTT(DF,len,1);
    for(int i=0;i<(1<<len);++i)G[i]=DF[i]*Ni[i]%P;
    NTT(G,len,-1);
    for(int i=n-1;i>0;--i)G[i]=G[i-1]*qpow(i,P-2)%P;
    G[0]=0;
}

多项式 \exp

这个最复杂了，既要求逆，求 \ln，还要递归求解，还要会一点泰勒展开。

现求 G(x) \equiv e^{A(x)}~(mod~x^n)，两边同时取对数 \ln(G(x))-A(x)\equiv 0~(mod~ x^n)。

令 F(G(x))=\ln(G(x))-A(x)。

若已知 F(G_0(x))\equiv0~(mod~x^{\lceil\frac{n}{2}\rceil})，先求 G(x) 满足 F(G(x))\equiv 0~(mod~x^n)。

将后面的式子泰勒展开，

F(G(x))=\sum_{i=0}\frac{F^{(i)}(G_0(x))}{i!}(G(x)-G_0(x))^i

其中 F^{(i)}(x) 指 F(x) 的 i 阶导数。

注意到 G(x)\equiv G_0(x)~(mod~x^{\lceil\frac{n}{2}\rceil})，

原因大概是 \ln(G(x))\equiv\ln(G_0(x))~(mod~x^{\lceil\frac{n}{2}\rceil})，而由之前的多项式求 \ln 知道，k 次多项式求 \ln 后还是 k 次多项式（我乱说的）。

所以有，

\sum_{i=2}(G(x)-G_0(x))^i\equiv0~(mod~x^{n})

于是，

\begin{aligned} F(G(x))&\equiv F(G_0(x))+F'(G_0(x))(G(x)-G_0(x))~(mod~x^{n})\\ F(G_0(x))+F'(G_0(x))(G(x)-G_0(x))&\equiv0~(mod~x^{n})\\ G(x)&\equiv G_0(x)-\frac{F(G_0(x))}{F'(G_0(x))}~(mod~x^{n}) \end{aligned}

把 F(x) 拆开，

\begin{aligned} G(x)&\equiv G_0(x)-\frac{\ln(G_0(x))-A(x)}{\frac{1}{G_0(x)}}~(mod~x^{n})\\ G(x)&\equiv G_0(x)(1-\ln(G_0(x))+A(x))~(mod~x^{n}) \end{aligned} 
void Fexp(int n,LL *F,LL *G) {
    if(n==1){G[0]=1;return;}
    Fexp((n+1)>>1,F,G);
    int len=0;while((1<<len)<(n<<1))++len;
    Fln(n,G,Ln);
    for(int i=0;i<n;++i)D[i]=F[i];
    for(int i=n;i<(1<<len);++i)D[i]=0;
    NTT(D,len,1);NTT(Ln,len,1);NTT(G,len,1);
    for(int i=0;i<(1<<len);++i)G[i]=G[i]*(1-Ln[i]+D[i]+P)%P; 
    NTT(G,len,-1);
    for(int i=n;i<(1<<len);++i)G[i]=0;
}