Polynomial_Industry

发表于 2022-03-20 更新于 2022-05-04 分类于模板

多项式工业

方便复习直接把重要的式子放在前面：

求逆，采用倍增，式子（牛顿迭代记忆可能比较方便？）：

$B (x) \equiv 2 B_{*} (x) - B_{*}^{2} (x) A (x) (\mod x^{n})$

求导、积分与复合，即经典求导、积分与复合，式子：

$F^{'} (x) = \sum_{i = 0}^{\infty} i f_{i} x^{i - 1}$

$F^{'} (x) = C + \sum_{i = 0}^{\infty} \frac{f_{i}}{i} x^{i + 1}$

$F (G (x)) = \sum_{i = 0}^{\infty} f_{i} G^{i} (x)$

牛顿迭代（非常重要）：

$F (x) \equiv F_{*} (x) - \frac{G (F_{*} (x))}{G^{'} (F_{*} (x))} (\mod x^{n})$

开根，采用倍增（可以用牛顿迭代直接推）：

$B (x) \equiv \frac{A (x) + B_{*}^{2} (x)}{2 B_{*} (x)} (\mod x^{n})$

多项式带余除法（换元翻转再取余）：

$Q^{T} (x) \equiv F^{T} (x) G^{T} (x)^{- 1} (\mod x^{n - m + 1})$

$R (x) = F (x) - Q (x) G (x)$

多项式 $\ln$ （两边求导再积分）：

$\ln F (x) = - \sum_{i = 0}^{\infty} \frac{(1 - F (x))^{i}}{i}$

$B (x) = \int \frac{A^{'} (x)}{A (x)}$

多项式 $\exp$ ，采用倍增（牛顿迭代推）：

$B (x) \equiv B_{*} (x) (1 - \ln B_{*} (x) + A (x)) (\mod x^{n})$

多项式快速幂：

$A^{k} (x) = \exp (k \ln A (x))$

方便粘板子直接把全家桶放这里了。

基本是复读 cmd 博客的。

模板题洛谷上基本都有。

占时没有 MTT 的东西（因为写不对）。。。

工业基础：NTT & FFT。

学完 NTT 后就可以来看这些操作了。

我们先把基本的模板贴在这里：

#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
#define Clr(f,n) memset(f,0,sizeof(ll)*(n))
#define Cpy(f,g,n) memcpy(f,g,sizeof(ll)*(n))
using namespace std;
namespace Ehnaev{
  inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
    while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
    return ret*f;
  }
  inline void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
    else {putchar(45);do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
    while(len>=0) putchar(buf[len--]);
  }
}using Ehnaev::read;using Ehnaev::write;
inline void writes(ll x) {write(x);putchar(32);}

const ll N=1e6,mo=998244353ll,G=3;

namespace Aeft{
  inline ll Pow(ll b,ll p) {
    ll res=1;while(p) {if(p&1) res=res*b%mo;b=b*b%mo;p>>=1;}return res;
  }
}using Aeft::Pow;

const ll invG=Pow(G,mo-2);

ll n;
ll rev[N*2+5],f[N*2+5],inv[N+5];

// NTT.
inline void Prev(ll n) {
  for(ll i=0;i<n;i++) rev[i]=(rev[i>>1]>>1)|((i&1)?(n>>1):0);
}
inline void NTT(ll *f,ll n,bool op) {
  Prev(n);for(ll i=0;i<n;i++) if(i<rev[i]) swap(f[i],f[rev[i]]);
  for(ll p=2;p<=n;p<<=1) {
    ll len=p>>1,tG=Pow(op?invG:G,(mo-1)/p);
    for(ll k=0;k<n;k+=p) {
      for(ll l=k,buf=1;l<k+len;l++,buf=buf*tG%mo) {
        ll t=f[l+len]*buf%mo;
        f[l+len]=f[l]-t;if(f[l+len]<0) f[l+len]+=mo;
        f[l]+=t;if(f[l]>mo) f[l]-=mo;
      }
    }
  }
  if(op) {ll invn=Pow(n,mo-2);for(ll i=0;i<n;i++) f[i]=f[i]*invn%mo;}
}
inline void Conv(ll *f,ll *g,ll n) {for(ll i=0;i<n;i++) f[i]=f[i]*g[i]%mo;}
inline void Times(ll *f,ll *g,ll len,ll lim) {
  static ll sav[N*2+5];ll n=1;for(;n<len+len;n<<=1);
  Clr(sav,n);Cpy(sav,g,n);NTT(f,n,0);NTT(sav,n,0);
  Conv(f,sav,n);NTT(f,n,1);Clr(f+lim,n-lim);Clr(sav,n);
}

一、多项式求逆

递推法就不写了。。。

我们采用倍增。

首先，如果在 $(\mod x^{1})$ 的时候，多项式显然只有常数项。直接求数字逆元。

设 $R (x)$ 表示 $(\mod x^{n})$ 时 $F (x)$ 的逆。

现在，假设我们已经得到了：

$R^{'} (x) \equiv F^{- 1} (x) (\mod x^{\frac{n}{2}})$

即逆元的前 $\frac{n}{2}$ 位。

显然：

$R (x) \equiv R_{*} (x) (\mod x^{\frac{n}{2}})$

移项一下：

$R (x) - R_{*} (x) \equiv 0 (\mod x^{\frac{n}{2}})$

然后平方一下：

$(R (x) - R_{*} (x))^{2} \equiv 0 (\mod x^{n})$

拆开：

$R^{2} (x) - 2 R_{*} (x) R (x) + R_{*}^{2} (x) \equiv 0 (\mod x^{n})$

两边同乘 $F (x)$ ：

$R (x) - 2 R_{*} (x) + R_{*}^{2} (x) F (x) \equiv 0 (\mod x^{n})$

移项：

$R (x) \equiv 2 R_{*} (x) - R_{*}^{2} (x) F (x) (\mod x^{n})$

显然可以算了。

根据主定理：

$T (n) = T (n / 2) + Θ (n \log n) = Θ (n \log n)$

所以最后时间复杂度 $O (n \log n)$ 。

一个简单的实现方法是先求 $(2 R_{*}) (x)$ ，然后求 ${R_{*}}^{2} (x)$ （自己和自己卷），然后把 ${R_{*}}^{2} (x)$ 和 $F (x)$ 卷，最后两个一减。

然后可能还有什么优化方法，但是我不想用。。。

最后记得清空。

代码：

// Inversion
inline void Invp(ll *f,ll m) {
  ll n;for(n=1;n<m;n<<=1);
  static ll w[N*2+5],r[N*2+5],tmp[N*2+5];
  w[0]=Pow(f[0],mo-2);
  for(ll len=2;len<=n;len<<=1) {
    for(ll i=0;i<(len>>1);i++) r[i]=(w[i]<<1)%mo;
    Cpy(tmp,f,len);NTT(w,len<<1,0);Conv(w,w,len<<1);
    NTT(tmp,len<<1,0);Conv(w,tmp,len<<1);
    NTT(w,len<<1,1);Clr(w+len,len);
    for(ll i=0;i<len;i++) w[i]=(r[i]-w[i]+mo)%mo;
  }
  Cpy(f,w,m);Clr(tmp,n<<1);Clr(w,n<<1);Clr(r,n<<1);
}

二、多项式牛顿迭代

关于求导、积分与复合。

定义多项式导数：

$F^{'} (x) = \sum_{i = 0}^{\infty} i f_{i} x^{i - 1}$

定义多项式积分：

$F^{'} (x) = C + \sum_{i = 0}^{\infty} \frac{f_{i}}{i} x^{i + 1}$

定义多项式的复合：

$F (G (x)) = \sum_{i = 0}^{\infty} f_{i} G^{i} (x)$

积分使用前需要先线性求一波逆元。

代码：

// Newton Iteration.
inline void Deriv(ll *f,ll m) {
  for(ll i=1;i<m;i++) {f[i-1]=f[i]*i%mo;}f[m-1]=0;
}
inline void Integr(ll *f,ll m) {
  for(ll i=m;i;i--) {f[i]=f[i-1]*inv[i]%mo;}f[0]=0;
}
inline void Init(ll n) {
  inv[1]=1;for(ll i=2;i<=n;i++) inv[i]=inv[mo%i]*(mo-mo/i)%mo;
}

关于多项式牛顿迭代：

若 $G (F (x)) = 0$ ，且 $G (F_{*} (x)) \equiv 0 (\mod x^{\frac{n}{2}})$ ，则我们有：

$F (x) \equiv F_{*} (x) - \frac{G (F_{*} (x))}{G^{'} (F_{*} (x))} (\mod x^{n})$

证明：

显然 $F (x) \equiv F_{*} (x) (\mod x^{\frac{n}{2}})$ 。

将 $G (F (x))$ 在 $F_{*} (x)$ 处展开：

$\begin{aligned} G (F (x)) & = G (F_{*} (x)) + \frac{G^{'} (F_{*} (x))}{1!} (F (x) - F_{*} (x)) \\ + \frac{G^{″} (F_{*} (x))}{2!} (F (x) - F_{*} (x))^{2} + \dots \end{aligned}$

可知 $F (x) - F_{*} (x)$ 的最低次项至少是 $x^{n / 2}$ 。

可知 $(F (x) - F_{*} (x))^{2}, (F (x) - F_{*} (x))^{3}, \dots$ 等的最低次项是 $x^{n}$ 。

但上面的运算是 $(\mod x^{n})$ 下的，所以这些项全部木大，故：

$G (F (x)) = G (F_{*} (x)) + \frac{G^{'} (F_{*} (x))}{1!} (F (x) - F_{*} (x))$

因为 $G (F (x)) = 0$ ，整理一下就是上面的结论了。

这个式子很牛逼。

多项式求逆再推导

这个用牛顿迭代推导。求 $A (x)$ 的逆 $B (x)$ 。

那么我们就有 $A (x) B (x) \equiv 1 (\mod x^{n})$ 。

然后我们设 $G (B (x)) \equiv A (x) B (x) - 1 (\mod x^{n})$ 。

则 $G^{'} (B (x)) \equiv A (x) (\mod x^{n})$ 。

设 $B_{*} (x)$ 为 $(\mod x^{n / 2})$ 下的解。

用上文牛顿迭代的式子：

$B (x) \equiv B_{*} (x) - \frac{G (B_{*} (x))}{G^{'} (B_{*} (x))} \equiv B_{*} (x) - \frac{A (x) B_{*} (x) - 1}{A_{*} (x)} (\mod x^{n})$

上面的 $\frac{1}{A_{*} (x)}$ 就是 $B_{*} (x)$ ，因为这俩多项式都是在 $(\mod x^{n / 2})$ 下的。

然后就有了：

$B (x) \equiv B_{*} (x) - B_{*} (x) (A (x) B_{*} (x) - 1) \equiv 2 B_{*} (x) - B_{*}^{2} (x) A (x) (\mod x^{n})$

这玩意就是上面那个求逆的式子。

三、多项式开根

即 $B^{2} (x) - A (x) \equiv 0 (\mod x^{n})$ 。

于是我们套路令 $G (B (x)) \equiv B^{2} (x) - A (x) (\mod x^{n})$ 。

于是有 $G^{'} (B (x)) \equiv 2 B (x) (\mod x^{n})$ 。

再根据牛顿迭代：

$B (x) \equiv B_{*} (x) - \frac{G (B_{*} (x))}{G^{'} (B_{*} (x))} \equiv B_{*} (x) - \frac{B_{*}^{2} (x) - A (x)}{2 B_{*} (x)} (\mod x^{n})$

化简后就是：

$B (x) \equiv \frac{A (x) + B_{*}^{2} (x)}{2 B_{*} (x)} (\mod x^{n})$

这个东西可以倍增了（还要用一下求逆），时间复杂度可以用定积分推导（不关心这个的可以跳过）：

$T (n) = Θ (\sum_{i = 0}^{\log_{2} n} \frac{n}{2^{i}} \log_{2} \frac{n}{2^{i}}) = Θ (n \sum_{i = 0}^{\log_{2} n} (\frac{1}{2})^{i} (\log_{2} n - i))$

我们积分近似一下：

$T (n) = Θ (n \int_{0}^{\log_{2} n} (\frac{1}{2})^{x} (\log_{2} n - x) δ x)$

积分线性性拆一下：

$T (n) = Θ (n \log_{2} n \int_{0}^{\log_{2} n} (\frac{1}{2})^{x} δ x - n \int_{0}^{\log_{2} n} x (\frac{1}{2})^{x} δ x)$

第一个还好，就是 $\int a^{x} δ x = \frac{1}{\ln a} a^{x} + C$ 。

第二个我去查了一下积分表： $\int x a^{x} δ x = \frac{x}{\ln a} a^{x} - \frac{1}{(\ln a)^{2}} a^{x} + C$ 。

然后这个我们就能算了：

$T (n) = Θ (- \frac{1}{\ln \frac{1}{2}} n \log_{2} n - \frac{n}{(\ln \frac{1}{2})^{2}} + \frac{1}{\ln \frac{1}{2}})$

注意 $\ln \frac{1}{2}$ 是负的，于是我们的时间复杂度就是：

$T (n) = Θ (n \log_{2} n)$

代码：

// Squre root
inline void Sqroot(ll *f,ll m) {
  ll n;for(n=1;n<m;n<<=1);static ll b1[N*2+5],b2[N*2+5];b1[0]=1;
  for(ll len=2;len<=n;len<<=1) {
    for(ll i=0;i<(len>>1);i++) b2[i]=(b1[i]<<1)%mo;
    Invp(b2,len);NTT(b1,len,0);Conv(b1,b1,len);NTT(b1,len,1);
    for(ll i=0;i<len;i++) b1[i]=(f[i]+b1[i])%mo;
    Times(b1,b2,len,len);
  }
  Cpy(f,b1,m);Clr(b1,n+n);Clr(b2,n+n);
}

四、多项式带余除法

定义多项式带余除法，对于多项式 $F (x)$ ， $G (x)$ ，存在唯一 $Q (x)$ ， $R (x)$ 使得：

$F (x) = Q (x) G (x) + R (x)$

此时称 $Q (x)$ 为 $F (x)$ 除以 $G (x)$ 的商， $R (x)$ 为 $F (x)$ 除以 $G (x)$ 的余数（若 $Q (x) \neq 0$ ，需要满足 $\deg Q + \deg G = d e g F$ ）。

我们同样可以记作：

$F (x) \equiv R (x) (\mod G (x))$

很容易想到，上面的 $R (x)$ 如果没了，这玩意就是直接多项式求逆。

那么我们就要考虑如何让 $R (x)$ 消失。

我们知道 $R (x)$ 的次数比较低，而我们前面的 $(\mod x^{?})$ 往往只能消去高次的项，留下低次的项。

那么很自然想到翻转系数，原来次数低的系数变成次数高的。

定义 $n$ 次多项式翻转操作 $F^{T} (x) = x^{n} F (x^{- 1})$ （实质上就是把系数翻转了一下）。

我们从 $F (x) = Q (x) G (x) + R (x)$ 开始，换元得到：

$F (x^{- 1}) = Q (x^{- 1}) G (x^{- 1}) + R (x^{- 1})$

两边同时乘上 $x^{n}$ ：

$x^{n} F (x^{- 1}) = x^{n} Q (x^{- 1}) G (x^{- 1}) + x^{n} R (x^{- 1})$

将我们上文定义的翻转操作代入：

$F^{T} (x) = Q^{T} (x) G^{T} (x) + x^{n - m + 1} R (x)$

这个时候我们将其置入 $(\mod x^{n - m + 1})$ 的环境下：

$F^{T} (x) \equiv Q^{T} (x) G^{T} (x) (\mod x^{n - m + 1})$

那么商就是：

$Q^{T} (x) \equiv F^{T} (x) G^{T} (x)^{- 1} (\mod x^{n - m + 1})$

求逆之后，翻转一下系数即可。

余数就是：

$R (x) = F (x) - Q (x) G (x)$

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

代码：

// Division with Remainder. Here f/g->f f%g->g.
// The quotient is the Prev n-m+1 terms of f.
// The remainder is the Prev m-1 terms of g.
inline void Rev(ll *f,ll n) {
  for(ll i=0;(i<<1)<n-1;i++) swap(f[i],f[n-i-1]);
}
inline void Divid(ll *f,ll *g,ll n,ll m) {
  static ll q[N<<1],t[N<<1];ll l=n-m+1;
  Rev(g,m);Cpy(q,g,l);Rev(g,m);Rev(f,n);Cpy(t,f,l);Rev(f,n);
  Invp(q,l);Times(q,t,l,l);Rev(q,l);Times(g,q,n,n);
  for(ll i=0;i<m-1;i++) {g[i]=(f[i]-g[i]+mo)%mo;}
  Clr(g+m-1,l);Cpy(f,q,l);Clr(f+l,n-l);
}

五、多项式 $\ln$ ， $\exp$

两者均由麦克劳林级数定义：

$\ln F (x) = - \sum_{i = 1}^{\infty} \frac{(1 - F (x))^{i}}{i}$

$\exp F (x) = \sum_{i = 0}^{\infty} \frac{F^{i} (x)}{i!}$

这样我们的运算可以满足经典的一些性质。

多项式 $\ln$

这里我们有 $\ln A (x) = B (x)$ 。

两边同时求导：

$\frac{δ}{δ x} \ln A (x) = \frac{δ}{δ x} B (x)$

即（链式法则）：

$\frac{δ A (x)}{δ x} \frac{δ}{δ A (x)} \ln A (x) = B^{'} (x)$

即：

$\frac{A^{'} (x)}{A (x)} = B^{'} (x)$

再两边同时积分：

$B (x) = \int \frac{A^{'} (x)}{A (x)}$

也就是说，一次求导，一次求逆，一次相乘，一次积分，我们就得到了 $\ln A (x)$ 。

时间复杂度 $O (n \log n)$ 。
多项式 $\exp$

这里就讲一个倍增方法。

已知 $e^{A (x)} = B (x)$ ，即 $A (x) = \ln B (x)$ 。

我们设 $G (B (x)) = \ln B (x) - A (x)$ 。

求导可得 $G^{'} (B (x)) = B^{- 1} (x)$ 。

套路牛顿迭代：

$B (x) \equiv B_{*} (x) - \frac{G (B_{*} (x))}{G^{'} (B_{*} (x))} \equiv B_{*} (x) - \frac{\ln B_{*} (x) - A (x)}{B_{*} (x)^{- 1}} (\mod x^{n})$

即：

$B (x) \equiv B_{*} (x) (1 - \ln B_{*} (x) + A (x)) (\mod x^{n})$

根据上式倍增即可。

需要注意的是，必须保证 $a_{0} = 0$ ，此时 $b_{0} = 1$ 。

与上文多项式开根的复杂度分析类似，使用定积分可以得到 $\exp$ 的时间复杂度是 $O (n \log n)$ 的。

代码：

// Ln & Exp.
inline void Lnp(ll *f,ll m) {
  static ll g[N*2+5];
  Cpy(g,f,m);Invp(g,m);Deriv(f,m);Times(f,g,m,m);
  Integr(f,m-1);Clr(g,m);
}
inline void Exp(ll *f,ll m) {
  static ll s[N*2+5],s2[N*2+5];ll n=1;for(;n<m;n<<=1);s2[0]=1;
  for(ll len=2;len<=n;len<<=1) {
    Cpy(s,s2,len>>1);Lnp(s,len);
    for(ll i=0;i<len;i++) {s[i]=(f[i]-s[i]+mo)%mo;}
    s[0]=(s[0]+1)%mo;Times(s2,s,len,len);
  }
  Cpy(f,s2,m);Clr(s,n);Clr(s2,n);
}

六、多项式快速幂

有了上面的操作，这个东西就变得简单了起来：

$A^{k} (x) = \exp (k \ln A (x))$

也就是说，一次 $\ln$ ，一次乘常系数，一次 $\exp$ ，我们就完成了多项式快速幂。

时间复杂度 $O (n \log n)$ （与 $k$ 完全没有关系）。

~~关于加强版，因为巨神的码被 Hack 了，我也懒得管，所以就不做了。~~

代码：

// Qpow.
inline ll Transtonum(char *ch,ll len) {
  ll res=0;
  for(ll i=0;i<len;i++) {res=res*10ll%mo;res=(res+ch[i]-48)%mo;}
  return res;
}

int main() {

  n=read();char ch[N+5];scanf("%s",ch);Init(n);
  ll k=Transtonum(ch,strlen(ch));
  for(ll i=0;i<n;i++) f[i]=read();

  Lnp(f,n);for(ll i=0;i<n;i++) f[i]=f[i]*k%mo;Exp(f,n);

  for(ll i=0;i<n;i++) writes(f[i]);

  return 0;
}

七、任意模数多项式乘法

咕咕咕。