约定
\(F[i]\) 表示 \(F(x)\) 的 \(i\) 次项系数。
多项式乘法基础
详情见 多项式乘法入门
多项式求逆
给出 \(n\) 次多项式 \(F(x)\)，求一个多项式 \(G(x)\)，满足 \(F(x)G(x)\equiv 1\pmod {x^n}\)，\(G(x)\) 每个系数对 \(998244353\) 取模。
我们逐一递推，假设已知 \(G[1...i-1]\)，需要求 \(G[i]\) 的值。若 \(i=1\)，显然 \(G[1]=\frac1{F[1]}\)；否则，有
\[\sum_{j=0}^iF[j]G[i-j]=0 \]把带 \(G[i]\) 的提出来
\[F[0]G[i]+\sum_{j=0}^{i-1} F[j]G[i-j]=0 \]\[G[i]=-\frac{\sum_{j=0}^{i-1}F[j]G[i-j]}{F[0]} \]该算法的时间复杂度为 \(O(n^2)\)。
我们尝试使用 倍增法 求解。
若我们已知 \(\lfloor\frac n2\rfloor\) 次多项式 \(G_0(x)\) 满足
\[F(x)G_0(x)\equiv 1\pmod {x^{\lceil\frac n2\rceil}} \]那么由于
\[F(x)G(x)\equiv1\pmod{x^n} \]模数变为 \(\lceil\frac n2\rceil\)
\[F(x)G(x)\equiv1\pmod{x^{\lceil\frac n2\rceil}} \]两式相减得
\[F(x)(G(x)-G_0(x))\equiv 0\pmod{x^{\lceil\frac n2\rceil}} \]\[G(x)-G_0(x)\equiv0\pmod{x^{\lceil\frac n2\rceil}} \]为了把模数变为 \(n\)，两边平方
\[(G(x)-G_0(x))^2\equiv0\pmod{x^n} \]同时乘 \(F(x)\)
\[F(x)(G(x)-G_0(x))^2\equiv0\pmod{x^n} \]展开
\[F(x)G^2(x)-2F(x)G(x)G_0(x)+F(x)G_0^2(x)\equiv0\pmod{x^n} \]带入 \(F(x)G(x)\equiv1\pmod {x^n}\)
得
\[G(x)-2G_0(x)+F(x)G_0^2(x)\equiv0\pmod{x^n} \]移项得
\[G(x)\equiv2G_0(x)-F(x)G_0^2(x)\pmod{x^n} \]其实也可以牛顿迭代。
点击查看代码
ll Q[maxn],P[maxn],o[maxn],t;
void Getinv(ll *a,ll *b,ll n){
for(ll i=0;i<n;i++) Q[i]=0; t=0;
while(n>1) o[++t]=n, n=n+1>>1;
Q[0]=power(a[0]); o[++t]=1;
for(ll i=t-1;i;i--){
for(ll j=0;j<o[i+1];j++) P[j]=Q[j];
mul(P,P,P,o[i+1],o[i+1],o[i]);
mul(a,P,P,o[i],o[i],o[i]);
for(ll j=0;j<o[i];j++) Q[j]=(2*Q[j]-P[j]+mod)%mod;
}
for(ll i=0;i<o[1];i++) b[i]=Q[i];
}
时间复杂度 \(O(n\log n)\)。
多项式求导与积分
求导：\(F'(x)=\sum_{i>0} f[i]\cdot i x^{i-1}\)
积分：\(\sum_{i>0} \frac{f[i-1]}i x^i\)
积分不会书写。
注意 \(F'(x)\not =(F(x))'\)，可以设 \(y=F(x)\)，容易得到 \((F(x))'=y'=0\)
多项式 \(\ln\)
计算 \(\ln F(x)\)，设 \(G(x)=\ln F(x)\)。
两边同时求导
\[G'(x)=(\ln \circ F)'(x) \]链式法则得
\[G'(x)=\ln'F(x)\cdot F'(x) \]\[G'(x)=\frac{F'(x)}{F(x)} \]两边积分一下就行了，\(O(n\log n)\)。
点击查看代码
ll R[maxn];
void ln(ll *a,ll *b,ll n){
dao(a,R,n);
Getinv(a,b,n);
mul(b,R,R,n,n,n);
jifen(R,b,n);
}
多项式 \(\exp\)
设 \(F(G(x))=\ln G(x)-A(x)\)，我们要求的是 \(G(x)\)，满足方程 \(F(G(x))=0\)。
根据牛顿迭代，我们求出了 \(G_0(x)\equiv 0 \pmod x^{\lceil \frac n2 \rceil}\)，由于 \(A(x)\) 是已知的东西，则
\[G(x)\equiv G_0(x)-\frac{F(G_0(x))}{F'(G_0(x))} \pmod {x^n} \]\[G(x)\equiv G_0(x)-\frac{\ln G_0(x)-A(x)}{\ln 'G_0(x)} \pmod {x^n} \]\[G(x)\equiv G_0(x)-\frac{\ln G_0(x)-A(x)}{\frac 1{G_0(x)}} \pmod {x^n} \]\[G(x)\equiv G_0(x)-G_0(x)\cdot (\ln G_0(x)-A(x)) \pmod {x^n} \]\[G(x)\equiv G_0(x)\cdot (1-\ln G_0(x)+A(x)) \pmod {x^n} \]分治即可，\(O(n\log n)\)
点击查看代码
ll z[maxn],zlt,F[maxn],G[maxn];
void Exp(ll *a,ll *b,ll n){
zlt=0;
for(ll i=0;i<n;i++) F[i]=0;
while(n>1) z[++zlt]=n, n=n+1>>1;
z[++zlt]=1; F[0]=1;
for(ll i=zlt-1;i;i--){
ln(F,G,z[i]);
for(ll j=0;j<z[i];j++) G[j]=(a[j]<G[j]? a[j]+mod-G[j]:a[j]-G[j]);
G[0]=(G[0]==mod-1? 0:G[0]+1);
mul(F,G,F,z[i+1],z[i],z[i]);
}
for(ll i=0;i<z[1];i++) b[i]=F[i];
}
多项式开根
设 \(F(G(x))=G^2(x)-A(x)\)，求 \(F(G(x))=0\) 的解。
和 \(\exp\) 基本一模一样
\[G(x)\equiv G_0-\frac{F(G_0(x))}{F'(G_0(x))} \pmod {x^n} \]\[G(x)\equiv G_0-\frac{G_0^2(x)-A(x)}{2G_0(x)} \pmod {x^n} \]\[G(x)\equiv \frac{A(x)+G_0^2(x)}{2G_0(x)} \pmod {x^n} \]点击查看代码
void Sqrt(ll *a,ll *b,ll n){
zlt=0;
for(ll i=0;i<n;i++) F[i]=0;
while(n>1) z[++zlt]=n, n=n+1>>1;
z[++zlt]=1; F[0]=1;
for(ll i=zlt-1;i;i--){
mul(F,F,G,z[i+1],z[i+1],z[i]);
for(ll j=0;j<z[i];j++) G[j]=(G[j]+a[j]>=mod? G[j]+a[j]-mod:G[j]+a[j]);
for(ll j=0;j<z[i+1];j++) F[j]=((F[j]<<1)>=mod? (F[j]<<1)-mod:F[j]<<1);
Getinv(F,F,z[i]);
mul(G,F,F,z[i],z[i],z[i]);
}
for(ll i=0;i<z[1];i++) b[i]=F[i];
}
多项式除法
已知 \(F(x),G(x)\)，解方程 \(F(x)=P(x)G(x)+Q(x)\)，其中 \(\deg Q(x)<\deg G(x)\)。
若 \(\deg F(x)=n,\space \deg G(x)=m\)，
推导：
\[F(\frac1x)=P(\frac1x)G(\frac1x)+Q(\frac1x) \]\[x^nF(\frac1x)=x^nP(\frac1x)G(\frac1x)+x^nQ(\frac1x) \]\[x^nF(\frac1x)=x^{n-m}P(\frac1x)*x^mG(\frac1x)+x^nQ(\frac1x) \]\[F_R(x)=P_R(x)G_R(x)+x^{n-m+1}Q_R(x) \]上式中形如 \(D_R(x)\) 的多项式表示 \(D(x)\) 所有系数 reverse 后的多项式。
注意到右边有一项 \(x^{n-m+1}Q_R(x)\)，当上式在模 \(x^{n-m+1}\)
意义下：
注意到 \(P_R(x)\) 的次数为 \(n-m\)，于是一个求逆一个乘法可得 \(P_R(x)\)，进而得到 \(P(x)\)。
带入 \(F(x)=P(x)G(x)+Q(x)\) 即可得到 \(Q(x)\)。
多项式快速幂
给出多项式 \(F(x)\) 和正整数 \(n,k\)，求 \(F^k(x)\pmod n\)
考虑到 \(x^k=\exp(k\ln x)\)，于是 \(F^k(x)=\exp(k\ln F(x))\)，直接一个 \(\ln\) 一个 \(\exp\) 即可。
但是 \([x^0]F(x)\) 不一定为 \(1\)，不能直接 \(\ln\)，把多项式转换成 \(F(x)=x^ab*G(x)\) 的形式，于是 \(F^k(x)=x^{ak}b^kG^k(x)\)，注意 \(k\) 在 \(b^k\) 中对 \(\varphi(mod)\) 取模。
常系数齐次线性递推
已知对于 \(n\ge k\)，有 \(a_n=\sum\limits_{i=1}^k f_ia_{n-i}\)，给出 \(f_{1...k},a_{0...k-1}\)，求 \(a_n\)。
\(n\le10^9\)。
设 \(F(\sum\limits f_ix^i)=\sum f_ia_i\)，答案即为 \(F(x^n)\)。
构造多项式 \(G(x)=x^k-\sum\limits_{i=0}^{k-1}f_{k-i}x^i\)。
显然，\(F(G(x))=F(x^k-\sum\limits_{i=0}^{k-1}f_{k-i}x^i)=a_k-\sum\limits_{i=0}^{k-1}f_{k-i}a_i=0\)
那么若 \(x^n=P(x)G(x)+Q(x)\)，那么 \(F(x^n)=F(Q(x))\)。
这相当于多项式取模。但是 \(n\) 太大，我们可以用快速幂，把普通乘换成 \(\text{ntt}\)，把普通取模换成多项式取模。
部分代码合集
点击查看代码
ll power(ll a,ll b=mod-2){
ll s=1;
while(b){
if(b&1) s=s*a%mod;
a=a*a%mod; b>>=1;
} return s;
}
struct POLY{
ll rev[maxn<<2], tr, inv[maxn<<2];
void Getrev(ll n){
if(tr==n) return; tr=n;
for(ll i=1;i<n;i++)
rev[i]=(rev[i>>1]>>1)|(i&1? n>>1:0);
}
void ntt(ll *a,ll n){
Getrev(n);
for(ll i=1;i<n;i++)
if(i<rev[i]) swap(a[i],a[rev[i]]);
for(ll i=1;i<n;i<<=1){
ll g=power(3,(mod-1)/(i<<1));
for(ll j=0;j<n;j+=(i<<1))
for(ll k=0,g0=1;k<i;k++,g0=g0*g%mod){
ll x=a[j|k], y=a[i|j|k]*g0%mod;
a[j|k]=(x+y>=mod? x+y-mod:x+y), a[i|j|k]=(x<y? x+mod-y:x-y);
}
}
}
ll A[maxn<<2], B[maxn<<2];
void mul(ll *a,ll *b,ll *c,ll n,ll m,ll k){
for(ll i=0;i<n;i++) A[i]=a[i];
for(ll i=0;i<m;i++) B[i]=b[i];
ll l=1;
while(l<n+m-1) l<<=1;
ntt(A,l), ntt(B,l);
for(ll i=0;i<l;i++) A[i]=A[i]*B[i]%mod;
ntt(A,l), reverse(A+1,A+l);
ll Inv=power(l);
for(ll i=0;i<l;i++){
if(i<k) c[i]=A[i]*Inv%mod;
A[i]=B[i]=0;
}
for(ll i=l;i<k;i++) c[i]=0;
}
ll Q[maxn],P[maxn],o[maxn],t;
void Getinv(ll *a,ll *b,ll n){
for(ll i=0;i<n;i++) Q[i]=0; t=0;
while(n>1) o[++t]=n, n=n+1>>1;
Q[0]=power(a[0]); o[++t]=1;
for(ll i=t-1;i;i--){
for(ll j=0;j<o[i+1];j++) P[j]=Q[j];
mul(P,P,P,o[i+1],o[i+1],o[i]);
mul(a,P,P,o[i],o[i],o[i]);
for(ll j=0;j<o[i];j++) Q[j]=(2*Q[j]-P[j]+mod)%mod;
}
for(ll i=0;i<o[1];i++) b[i]=Q[i];
}
void dao(ll *a,ll *b,ll n){
for(ll i=1;i<n;i++) b[i-1]=a[i]*i%mod;
}
ll r=0;
void jifen(ll *a,ll *b,ll n){
while(r<n){
++r;
if(r>1) inv[r]=(mod-mod/r)*inv[mod%r]%mod;
else inv[r]=1;
}
for(ll i=n-1;i>0;i--) b[i]=a[i-1]*inv[i]%mod;
b[0]=0;
}
ll R[maxn];
void ln(ll *a,ll *b,ll n){
dao(a,R,n);
Getinv(a,b,n);
mul(b,R,R,n,n,n);
jifen(R,b,n);
}
ll z[maxn],zlt,F[maxn],G[maxn];
void Exp(ll *a,ll *b,ll n){
zlt=0;
for(ll i=0;i<n;i++) F[i]=0;
while(n>1) z[++zlt]=n, n=n+1>>1;
z[++zlt]=1; F[0]=1;
for(ll i=zlt-1;i;i--){
ln(F,G,z[i]);
for(ll j=0;j<z[i];j++) G[j]=(a[j]<G[j]? a[j]+mod-G[j]:a[j]-G[j]);
G[0]=(G[0]==mod-1? 0:G[0]+1);
mul(F,G,F,z[i+1],z[i],z[i]);
}
for(ll i=0;i<z[1];i++) b[i]=F[i];
}
void Sqrt(ll *a,ll *b,ll n){
zlt=0;
for(ll i=0;i<n;i++) F[i]=0;
while(n>1) z[++zlt]=n, n=n+1>>1;
z[++zlt]=1; F[0]=1;
for(ll i=zlt-1;i;i--){
mul(F,F,G,z[i+1],z[i+1],z[i]);
for(ll j=0;j<z[i];j++) G[j]=(G[j]+a[j]>=mod? G[j]+a[j]-mod:G[j]+a[j]);
for(ll j=0;j<z[i+1];j++) F[j]=((F[j]<<1)>=mod? (F[j]<<1)-mod:F[j]<<1);
Getinv(F,F,z[i]);
mul(G,F,F,z[i],z[i],z[i]);
}
for(ll i=0;i<z[1];i++) b[i]=F[i];
}
}D;