一些约定：下面 \(f^i(x)\) 表示 \(i\) 阶导数。\(f(x)^i\) 表示幂次。若不说明绝大部分除一个多项式时都是代表乘上它的逆。
多项式加减，求导积分
过于简单不讲。\((x^a)'=ax^{a-1},\displaystyle\int x^a {\rm d}x=\dfrac{x^{a+1}}{a+1}+C\)。实际操作时 \(C=0\)，正确性是好证的。（如果你实在闲可以每次证一下）
多项式乘法，任意模数多项式乘法
NTT;
多项式牛顿迭代
给定多项式 \(g(x)\)，已知 \(g(f(x))\equiv 0\pmod{x^n}\)，要解出 \(f(x)\)。其中 \(g(x)\) 的形式较为简单（具体看下面求逆）。（注：这没有模板，只是一个前置知识，会应用到各个模板）
考虑倍增。
若已经求出 \(f_0(x)\) 满足：\(g(f_0(x))\equiv 0\pmod{x^{\lceil n/2\rceil}}\)，下面考虑求出 \(f(x)\)。
把 \(g(f(x))\) 在 \(f_0(x)\) 出泰勒展开：
\(0\equiv g(f(x))=\sum\limits_{i\ge 0} \dfrac{1}{i!}g^i(f_0(x))(f(x)-f_0(x))^i\pmod {x^n}\)。
注意到 \(f(x)-f_0(x)\) 的最低次项次数 \(\ge \lceil n/2\rceil\)，于是 \(\forall i\ge 2,(f(x)-f_0(x))^i\equiv 0\pmod {x^n}\)。
于是 \(g'(f_0(x))(f(x)-f_0(x))+g(f_0(x))\equiv 0\pmod {x^n}\Rightarrow f(x)\equiv f_0(x)-\dfrac{g(f_0(x))}{g'(f_0(x))}\pmod {x^n}\)。
你可能觉得这不是还要求逆吗？你为啥不先讲求逆？你先别急。
多项式求逆
给定一个多项式 \(f(x)\)，请求出一个多项式 \(g(x)\)，满足 \(f(x)\times g(x)\equiv1\pmod{x^n}\)。系数对 \(998244353\) 取模。
考虑牛顿迭代。
\(G(X)=f(x)-\dfrac{1}{X}\)，则 \(G(g(x))\equiv0 \pmod {x^n}\)。
假设求出了 \(g_0(x)\) 使得 \(G(g_0(x))\equiv 0\pmod{x^{\lceil n/2\rceil}}\)，则：
\(g(x)\equiv g_0(x)-\dfrac{G(g_0(x))}{G'(g_0(x))}=g_0(x)-\dfrac{f(x)-\dfrac{1}{g_0(x)}}{\dfrac{1}{g_0(x)^2}}\equiv 2g_0(x)-f(x)g_0(x)^2\pmod {x^n}\)。
用两次多项式乘法即可，但是可以通过点值进行特殊变换做到一次多项式乘法。
即一般的多项式乘法设两个对应的点值为 \(x,y\)，则变换 \(f(x,y)=xy\)，这里 \(f(x,y)=2y-xy^2\) 即可。
复杂度 \(T(n)=T(n/2)+O(n\log n)=O(n\log n)\)。
$\texttt{code}$
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int mod=998244353,N=4e5+5;
int n,m,a[N],b[N],w[N],mmax;
inline int rd()
{
int x=0,zf=1;
char ch=getchar();
while(ch<'0'||ch>'9') (ch=='-')and(zf=-1),ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return x*zf;
}
inline void wr(int x)
{
if(x==0) return putchar('0'),putchar(' '),void();
int num[35],len=0;
while(x) num[++len]=x%10,x/=10;
for(int i=len;i>=1;i--) putchar(num[i]+'0');
putchar(' ');
}
inline int bger(int x){return x|=x>>1,x|=x>>2,x|=x>>4,x|=x>>8,x|=x>>16,x+1;}
inline int md(int x){return x>=mod?x-mod:x;}
inline int ksm(int x,int p){int s=1;for(;p;(p&1)&&(s=1ll*s*x%mod),x=1ll*x*x%mod,p>>=1);return s;}
inline void init(int mmax)
{
for(int i=1,j,k;i<mmax;i<<=1)
for(w[j=i]=1,k=ksm(3,(mod-1)/(i<<1)),j++;j<(i<<1);j++)
w[j]=1ll*w[j-1]*k%mod;
}
inline void DNT(int *a,int mmax)
{
for(int i,j,k=mmax>>1,L,*W,*x,*y,z;k;k>>=1)
for(L=k<<1,i=0;i<mmax;i+=L)
for(j=0,W=w+k,x=a+i,y=x+k;j<k;j++,W++,x++,y++)
*y=1ll*(*x+mod-(z=*y))* *W%mod,*x=md(*x+z);
}
inline void IDNT(int *a,int mmax)
{
for(int i,j,k=1,L,*W,*x,*y,z;k<mmax;k<<=1)
for(L=k<<1,i=0;i<mmax;i+=L)
for(j=0,W=w+k,x=a+i,y=x+k;j<k;j++,W++,x++,y++)
z=1ll* *W* *y%mod,*y=md(*x+mod-z),*x=md(*x+z);
reverse(a+1,a+mmax);
for(int inv=ksm(mmax,mod-2),i=0;i<mmax;i++) a[i]=1ll*a[i]*inv%mod;
}
void INV(int num,int *a,int *b)
{
if(num==1) return b[0]=ksm(a[0],mod-2),void();
INV((num+1)>>1,a,b);
int mmax=bger(num<<1);init(mmax);
static int c[N];
for(int i=0;i<num;i++) c[i]=a[i];for(int i=num;i<mmax;i++) c[i]=0;
DNT(c,mmax);DNT(b,mmax);
for(int i=0;i<mmax;i++) b[i]=1ll*(2-1ll*c[i]*b[i]%mod+mod)%mod*b[i]%mod;
IDNT(b,mmax);
for(int i=num;i<mmax;i++) b[i]=0;
}
signed main()
{
n=rd();
for(int i=0;i<n;i++) a[i]=rd();
INV(n,a,b);
for(int i=0;i<n;i++) wr(b[i]);
return 0;
}
分治 FFT
给定序列 \(g_{1,2\dots n - 1}\)，求序列 \(f_{0,1\dots n - 1}\)。
其中 \(f_i=\sum\limits_{j=1}^if_{i-j}g_j\)，边界为 \(f_0=1\)。答案对 \(998244353\) 取模。
设 \(F(x)=\sum\limits_{i\ge 0}f_ix^i,G(x)=\sum\limits_{i\ge 0}g_ix^i\)，其中令 \(g_0=0\)。
则 \(F(x)\times G(x)=\sum\limits_{i\ge 0}x^i\sum\limits_{j=0}^i f_{i-j}g_j=\sum\limits_{i\ge 0}x^i\sum\limits_{j=0}^i f_{i-j}g_j=\sum\limits_{i\ge 1}x^if_i=F(x)-f_0=F(x)-1\)。
于是 \(G(x)=\dfrac{1}{1-F(x)}\)。多项式求逆即可，复杂度 \(O(n\log n)\)。
$\texttt{code}$
#include<bits/stdc++.h>
#define fr(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using namespace std;
const int mod=998244353,N=4e5+5;
int n,m,a[N],b[N],w[N],mmax;
inline int rd()
{
int x=0,zf=1;
char ch=getchar();
while(ch<'0'||ch>'9') (ch=='-')and(zf=-1),ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return x*zf;
}
inline void wr(int x)
{
if(x==0) return putchar('0'),putchar(' '),void();
int num[35],len=0;
while(x) num[++len]=x%10,x/=10;
for(int i=len;i>=1;i--) putchar(num[i]+'0');
putchar(' ');
}
inline int bger(int x){return x|=x>>1,x|=x>>2,x|=x>>4,x|=x>>8,x|=x>>16,x+1;}
inline int md(int x){return x>=mod?x-mod:x;}
inline int ksm(int x,int p){int s=1;for(;p;(p&1)&&(s=1ll*s*x%mod),x=1ll*x*x%mod,p>>=1);return s;}
inline void init(int mmax)
{
for(int i=1,j,k;i<mmax;i<<=1)
for(w[j=i]=1,k=ksm(3,(mod-1)/(i<<1)),j++;j<(i<<1);j++)
w[j]=1ll*w[j-1]*k%mod;
}
inline void DNT(int *a,int mmax)
{
for(int i,j,k=mmax>>1,L,*W,*x,*y,z;k;k>>=1)
for(L=k<<1,i=0;i<mmax;i+=L)
for(j=0,W=w+k,x=a+i,y=x+k;j<k;j++,W++,x++,y++)
*y=1ll*(*x+mod-(z=*y))* *W%mod,*x=md(*x+z);
}
inline void IDNT(int *a,int mmax)
{
for(int i,j,k=1,L,*W,*x,*y,z;k<mmax;k<<=1)
for(L=k<<1,i=0;i<mmax;i+=L)
for(j=0,W=w+k,x=a+i,y=x+k;j<k;j++,W++,x++,y++)
z=1ll* *W* *y%mod,*y=md(*x+mod-z),*x=md(*x+z);
reverse(a+1,a+mmax);
for(int inv=ksm(mmax,mod-2),i=0;i<mmax;i++) a[i]=1ll*a[i]*inv%mod;
}
void dfs(int num,int *a,int *b)
{
if(num==1) return b[0]=ksm(a[0],mod-2),void();
dfs((num+1)>>1,a,b);
int mmax=bger(num<<1);init(mmax);
static int c[N];
for(int i=0;i<num;i++) c[i]=a[i];for(int i=num;i<mmax;i++) c[i]=0;
DNT(c,mmax);DNT(b,mmax);
for(int i=0;i<mmax;i++) b[i]=1ll*(2-1ll*c[i]*b[i]%mod+mod)%mod*b[i]%mod;
IDNT(b,mmax);
for(int i=num;i<mmax;i++) b[i]=0;
}
signed main()
{
n=rd();
for(int i=1;i<n;i++) a[i]=(mod-rd())%mod;a[0]=1;
dfs(n,a,b);
for(int i=0;i<n;i++) wr(b[i]);
return 0;
}
多项式除法
给定一个 \(n\) 次多项式 \(F(x)\) 和一个 \(m\) 次多项式 \(G(x)\) ，请求出多项式 \(Q(x)\), \(R(x)\)，满足以下条件：
- \(Q(x)\) 次数为 \(n-m\)，\(R(x)\) 次数小于 \(m\)
- \(F(x) = Q(x) \times G(x) + R(x)\)
所有的运算在模 \(998244353\) 意义下进行。保证 \(m<n\)。
这种 trick 基本不会用第二次了。注意到我们只需求出 \(Q(x)\) 即可一次多项式乘法解决。
设 \(F_R(x)\) 表示 \(F(x)\) 翻转系数形成的多项式，即 \(F_R(x)=x^{\deg f}F(\frac{1}{x})\)。而 \(\deg F_R(x)=F(x)\)。
\(F(x) = Q(x) \times G(x) + R(x)\Rightarrow x^nF(\frac{1}{x})=(x^mG(\frac{1}{x})(x^{n-m}Q(\frac{1}{x}))+R(x)\Rightarrow F_R(x)=G_R(x)Q_R(x)+x^{n-m+1}R_R(x)\)。
我们消去 \(R_R(x)\) 的影响：\(F_R(x)\equiv G_R(x)Q_R(x)\pmod {x^{n-m+1}}\)。
于是多项式求逆即可，注意细节。复杂度 \(O(n\log n)\)。
$\texttt{code}$
#include<bits/stdc++.h>
#define fr(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
#define LL long long
using namespace std;
const int mod=998244353,N=4e5+5;
int n,m,a[N],b[N],c[N],d[N],e[N],w[N],mmax;
inline int rd()
{
int x=0,zf=1;
char ch=getchar();
while(ch<'0'||ch>'9') (ch=='-')and(zf=-1),ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return x*zf;
}
inline void wr(int x)
{
if(x==0) return putchar('0'),putchar(' '),void();
int num[35],len=0;
while(x) num[++len]=x%10,x/=10;
for(int i=len;i>=1;i--) putchar(num[i]+'0');
putchar(' ');
}
inline int bger(int x){return x|=x>>1,x|=x>>2,x|=x>>4,x|=x>>8,x|=x>>16,x+1;}
inline int md(int x){return x>=mod?x-mod:x;}
inline int ksm(int x,int p){int s=1;for(;p;(p&1)&&(s=1ll*s*x%mod),x=1ll*x*x%mod,p>>=1);return s;}
inline void init(int mmax)
{
for(int i=1,j,k;i<mmax;i<<=1)
for(w[j=i]=1,k=ksm(3,(mod-1)/(i<<1)),j++;j<(i<<1);j++)
w[j]=1ll*w[j-1]*k%mod;
}
inline void DNT(int *a,int mmax)
{
for(int i,j,k=mmax>>1,L,*W,*x,*y,z;k;k>>=1)
for(L=k<<1,i=0;i<mmax;i+=L)
for(j=0,W=w+k,x=a+i,y=x+k;j<k;j++,W++,x++,y++)
*y=1ll*(*x+mod-(z=*y))* *W%mod,*x=md(*x+z);
}
inline void IDNT(int *a,int mmax)
{
for(int i,j,k=1,L,*W,*x,*y,z;k<mmax;k<<=1)
for(L=k<<1,i=0;i<mmax;i+=L)
for(j=0,W=w+k,x=a+i,y=x+k;j<k;j++,W++,x++,y++)
z=1ll* *W* *y%mod,*y=md(*x+mod-z),*x=md(*x+z);
reverse(a+1,a+mmax);
for(int inv=ksm(mmax,mod-2),i=0;i<mmax;i++) a[i]=1ll*a[i]*inv%mod;
}
inline void NTT(int *a,int *b,int n,int m)
{
mmax=bger(n+m);init(mmax);
DNT(a,mmax);DNT(b,mmax);
for(int i=0;i<mmax;i++) a[i]=1ll*a[i]*b[i]%mod;
IDNT(a,mmax);
}
void INV(int num,int *a,int *b)
{
if(num==1) return b[0]=ksm(a[0],mod-2),void();
INV((num+1)>>1,a,b);
int mmax=bger(num<<1);init(mmax);
static int c[N];
for(int i=0;i<num;i++) c[i]=a[i];for(int i=num;i<mmax;i++) c[i]=0;
DNT(c,mmax);DNT(b,mmax);
for(int i=0;i<mmax;i++) b[i]=1ll*(2-1ll*c[i]*b[i]%mod+mod)%mod*b[i]%mod;
IDNT(b,mmax);
for(int i=num;i<mmax;i++) b[i]=0;
}
inline void div(int *a,int *b,int n,int m,int *d)//余式是a
{
reverse(a,a+1+n);reverse(b,b+1+m);INV(n-m+1,b,c);
int mmax=bger(2*n-m+1);static int e[N];init(mmax);
for(int i=0;i<=n;i++) d[i]=a[i];
DNT(d,mmax);DNT(c,mmax);
for(int i=0;i<mmax;i++) d[i]=1ll*d[i]*c[i]%mod;
IDNT(d,mmax);reverse(d,d+1+n-m);for(int i=n-m+1;i<=n;i++) d[i]=0;
for(int i=0;i<n-m+1;i++) e[i]=d[i];
mmax=bger(n<<1);init(mmax);
reverse(a,a+1+n);reverse(b,b+1+m);
DNT(b,mmax);DNT(e,mmax);
for(int i=0;i<mmax;i++) b[i]=1ll*b[i]*e[i]%mod;
IDNT(b,mmax);
for(int i=0;i<m;i++) a[i]=(mod+a[i]-b[i])%mod;
}
signed main()
{
n=rd();m=rd();
for(int i=0;i<=n;i++) a[i]=rd();
for(int i=0;i<=m;i++) b[i]=rd();
div(a,b,n,m,d);
for(int i=0;i<n-m+1;i++) wr(d[i]);puts("");
for(int i=0;i<m;i++) wr(a[i]);
return 0;
}
多项式 ln/exp
多项式 ln
给出 \(n-1\) 次多项式 \(A(x)\)，求一个 \(\bmod{\:x^n}\) 下的多项式 \(B(x)\)，满足 \(B(x) \equiv \ln A(x)\)
在 \(\text{mod } 998244353\) 下进行，且 \(a_i \in [0, 998244353) \cap \mathbb{Z}\)
注意到 \((\ln f(x))'=\dfrac{f'(x)}{f(x)}\)，于是 \(\ln(A(x))=\displaystyle\int \dfrac{A'(x)}{A(x)} {\rm d}x\)。
只需一次求导，一次求逆，一次积分即可。复杂度 \(O(n\log n)\)。
$\texttt{code}$
//洛谷 P4725
//https://www.luogu.com.cn/problem/P4725
#include<bits/stdc++.h>
#define fr(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using namespace std;
const int mod=998244353,N=4e5+5;
int n,a[N],w[N],mmax;
inline int rd()
{
int x=0,zf=1;
char ch=getchar();
while(ch<'0'||ch>'9') (ch=='-')and(zf=-1),ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return x*zf;
}
inline void wr(int x)
{
if(x==0) return putchar('0'),putchar(' '),void();
int num[35],len=0;
while(x) num[++len]=x%10,x/=10;
for(int i=len;i>=1;i--) putchar(num[i]+'0');
putchar(' ');
}
inline int bger(int x){return x|=x>>1,x|=x>>2,x|=x>>4,x|=x>>8,x|=x>>16,x+1;}
inline int md(int x){return x>=mod?x-mod:x;}
inline int ksm(int x,int p){int s=1;for(;p;(p&1)&&(s=1ll*s*x%mod),x=1ll*x*x%mod,p>>=1);return s;}
inline void dao(int *a,int n){for(int i=1;i<n;i++) a[i-1]=1ll*i*a[i]%mod;a[n-1]=0;}
inline void ji(int *a,int n){for(int i=n-1;i>=1;i--) a[i]=1ll*ksm(i,mod-2)*a[i-1]%mod;a[0]=0;}
inline void init(int mmax)
{
for(int i=1,j,k;i<mmax;i<<=1)
for(w[j=i]=1,k=ksm(3,(mod-1)/(i<<1)),j++;j<(i<<1);j++)
w[j]=1ll*w[j-1]*k%mod;
}
inline void DNT(int *a,int mmax)
{
for(int i,j,k=mmax>>1,L,*W,*x,*y,z;k;k>>=1)
for(L=k<<1,i=0;i<mmax;i+=L)
for(j=0,W=w+k,x=a+i,y=x+k;j<k;j++,W++,x++,y++)
*y=1ll*(*x+mod-(z=*y))* *W%mod,*x=md(*x+z);
}
inline void IDNT(int *a,int mmax)
{
for(int i,j,k=1,L,*W,*x,*y,z;k<mmax;k<<=1)
for(L=k<<1,i=0;i<mmax;i+=L)
for(j=0,W=w+k,x=a+i,y=x+k;j<k;j++,W++,x++,y++)
z=1ll* *W* *y%mod,*y=md(*x+mod-z),*x=md(*x+z);
reverse(a+1,a+mmax);
for(int inv=ksm(mmax,mod-2),i=0;i<mmax;i++) a[i]=1ll*a[i]*inv%mod;
}
inline void NTT(int *a,int *b,int n,int m)
{
mmax=bger(n+m);init(mmax);
DNT(a,mmax);DNT(b,mmax);
for(int i=0;i<mmax;i++) a[i]=1ll*a[i]*b[i]%mod;
IDNT(a,mmax);
}
void INV(int num,int *a,int *b)
{
if(num==1) return b[0]=ksm(a[0],mod-2),void();
INV((num+1)>>1,a,b);
int mmax=bger(num<<1);init(mmax);
static int c[N];
for(int i=0;i<num;i++) c[i]=a[i];for(int i=num;i<mmax;i++) c[i]=0;
DNT(c,mmax);DNT(b,mmax);
for(int i=0;i<mmax;i++) b[i]=1ll*(2-1ll*c[i]*b[i]%mod+mod)%mod*b[i]%mod;
IDNT(b,mmax);
for(int i=num;i<mmax;i++) b[i]=0;
}
inline void Ln(int *a,int n){static int b[N];for(int i=0;i<bger(n<<1);i++) b[i]=0;INV(n,a,b);dao(a,n);NTT(a,b,n,n);ji(a,n);for(int i=n;i<bger(n<<1);i++) a[i]=0;}
int main()
{
n=rd();for(int i=0;i<n;i++) a[i]=rd();
Ln(a,n);for(int i=0;i<n;i++) wr(a[i]);
return 0;
}
多项式 exp
给出 \(n-1\) 次多项式 \(A(x)\)，求一个 \(\bmod{\:x^n}\) 下的多项式 \(B(x)\)，满足 \(B(x) \equiv \text e^{A(x)}\)。系数对 \(998244353\) 取模。
考虑牛顿迭代。
构造 \(g(X)=\ln(X)-A(x)\)，则 \(g(B(x))\equiv 0\pmod {x^n}\)。
设 \(B_0(x)\) 满足 \(g(B_0(x))\equiv 0\pmod {x^{\lceil x/2\rceil}}\)
则 \(B(x)\equiv B_0(x)-\dfrac{g(B_0(x))}{g'(B_0(x))}=B_0(x)-\dfrac{\ln(B_0(x))-A(x)}{\dfrac{1}{B_0(x)}}=B_0(x)(1-\ln(B_0(x))+ A(x))\pmod {x^n}\)
这其中需要一次多项式乘法，一次多项式 \(\ln\)，于是复杂度 \(T(n)=T(n/2)+O(n\log n)=O(n\log n)\)。
$\texttt{code}$
//落谷 P4726
//https://www.luogu.com.cn/problem/P4726
#include<bits/stdc++.h>
#define fr(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using namespace std;
const int mod=998244353,N=4e5+5;
int n,a[N],b[N],w[N],mmax;
inline int rd()
{
int x=0,zf=1;
char ch=getchar();
while(ch<'0'||ch>'9') (ch=='-')and(zf=-1),ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return x*zf;
}
inline void wr(int x)
{
if(x==0) return putchar('0'),putchar(' '),void();
int num[35],len=0;
while(x) num[++len]=x%10,x/=10;
for(int i=len;i>=1;i--) putchar(num[i]+'0');
putchar(' ');
}
inline int bger(int x){return x|=x>>1,x|=x>>2,x|=x>>4,x|=x>>8,x|=x>>16,x+1;}
inline int md(int x){return x>=mod?x-mod:x;}
inline int ksm(int x,int p){int s=1;for(;p;(p&1)&&(s=1ll*s*x%mod),x=1ll*x*x%mod,p>>=1);return s;}
inline void dao(int *a,int n){for(int i=1;i<n;i++) a[i-1]=1ll*i*a[i]%mod;a[n-1]=0;}
inline void ji(int *a,int n){for(int i=n-1;i>=1;i--) a[i]=1ll*ksm(i,mod-2)*a[i-1]%mod;a[0]=0;}
inline void init(int mmax)
{
for(int i=1,j,k;i<mmax;i<<=1)
for(w[j=i]=1,k=ksm(3,(mod-1)/(i<<1)),j++;j<(i<<1);j++)
w[j]=1ll*w[j-1]*k%mod;
}
inline void DNT(int *a,int mmax)
{
for(int i,j,k=mmax>>1,L,*W,*x,*y,z;k;k>>=1)
for(L=k<<1,i=0;i<mmax;i+=L)
for(j=0,W=w+k,x=a+i,y=x+k;j<k;j++,W++,x++,y++)
*y=1ll*(*x+mod-(z=*y))* *W%mod,*x=md(*x+z);
}
inline void IDNT(int *a,int mmax)
{
for(int i,j,k=1,L,*W,*x,*y,z;k<mmax;k<<=1)
for(L=k<<1,i=0;i<mmax;i+=L)
for(j=0,W=w+k,x=a+i,y=x+k;j<k;j++,W++,x++,y++)
z=1ll* *W* *y%mod,*y=md(*x+mod-z),*x=md(*x+z);
reverse(a+1,a+mmax);
for(int inv=ksm(mmax,mod-2),i=0;i<mmax;i++) a[i]=1ll*a[i]*inv%mod;
}
inline void NTT(int *a,int *b,int n,int m)
{
mmax=bger(n+m);init(mmax);
DNT(a,mmax);DNT(b,mmax);
for(int i=0;i<mmax;i++) a[i]=1ll*a[i]*b[i]%mod;
IDNT(a,mmax);
}
void INV(int num,int *a,int *b)
{
if(num==1) return b[0]=ksm(a[0],mod-2),void();
INV((num+1)>>1,a,b);
int mmax=bger(num<<1);init(mmax);
static int c[N];
for(int i=0;i<num;i++) c[i]=a[i];for(int i=num;i<mmax;i++) c[i]=0;
DNT(c,mmax);DNT(b,mmax);
for(int i=0;i<mmax;i++) b[i]=1ll*(2-1ll*c[i]*b[i]%mod+mod)%mod*b[i]%mod;
IDNT(b,mmax);
for(int i=num;i<mmax;i++) b[i]=0;
}
inline void Ln(int *a,int n){static int b[N];for(int i=0;i<bger(n<<1);i++) b[i]=0;INV(n,a,b);dao(a,n);NTT(a,b,n,n);ji(a,n);for(int i=n;i<bger(n<<1);i++) a[i]=0;}
inline void Exp(int *a,int *b,int n)
{
if(n==1) return b[0]=1,void();
Exp(a,b,(n+1)>>1);static int c[N];for(int i=0;i<bger(n<<1);i++) c[i]=0;
for(int i=0;i<n;i++) c[i]=b[i];Ln(c,n);
for(int i=0;i<n;i++) c[i]=md(mod-c[i]+a[i]);c[0]=md(c[0]+1);
NTT(b,c,n,n);for(int i=n;i<bger(n<<1);i++) b[i]=0;
}
int main()
{
n=rd();for(int i=0;i<n;i++) a[i]=rd();
Exp(a,b,n);for(int i=0;i<n;i++) wr(b[i]);
return 0;
}
多项式快速幂/加强版
给定一个 \(n-1\) 次多项式 \(A(x)\)，求一个在 \(\bmod\ x^n\) 意义下的多项式 \(B(x)\)，使得 \(B(x) \equiv (A(x))^k \ (\bmod\ x^n)\)。
多项式的系数在 \(\bmod\ 998244353\) 的意义下进行运算。
普通版保证 \(a_0=1\)，加强版则不保证。
注意到 \((A(x))^k=\exp(k\ln(A(x)))\)，于是一次 exp 一次 ln 即可，复杂度 \(O(n\log n)\)。
$\texttt{code}$
//洛谷 P4726
//https://www.luogu.com.cn/problem/P4726
#include<bits/stdc++.h>
#define fr(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using namespace std;
const int mod=998244353,N=4e6+5;
int n,m,a[N],b[N],w[N],mmax;
inline int rd()
{
int x=0,zf=1;
char ch=getchar();
while(ch<'0'||ch>'9') (ch=='-')and(zf=-1),ch=getchar();
while(ch>='0'&&ch<='9') x=(10ll*x%mod+ch-'0')%mod,ch=getchar();
return x*zf;
}
inline void wr(int x)
{
if(x==0) return putchar('0'),putchar(' '),void();
int num[35],len=0;
while(x) num[++len]=x%10,x/=10;
for(int i=len;i>=1;i--) putchar(num[i]+'0');
putchar(' ');
}
inline int bger(int x){return x|=x>>1,x|=x>>2,x|=x>>4,x|=x>>8,x|=x>>16,x+1;}
inline int md(int x){return x>=mod?x-mod:x;}
inline int ksm(int x,int p){int s=1;for(;p;(p&1)&&(s=1ll*s*x%mod),x=1ll*x*x%mod,p>>=1);return s;}
inline void dao(int *a,int n){for(int i=1;i<n;i++) a[i-1]=1ll*i*a[i]%mod;a[n-1]=0;}
inline void ji(int *a,int n){for(int i=n-1;i>=1;i--) a[i]=1ll*ksm(i,mod-2)*a[i-1]%mod;a[0]=0;}
inline void init(int mmax)
{
for(int i=1,j,k;i<mmax;i<<=1)
for(w[j=i]=1,k=ksm(3,(mod-1)/(i<<1)),j++;j<(i<<1);j++)
w[j]=1ll*w[j-1]*k%mod;
}
inline void DNT(int *a,int mmax)
{
for(int i,j,k=mmax>>1,L,*W,*x,*y,z;k;k>>=1)
for(L=k<<1,i=0;i<mmax;i+=L)
for(j=0,W=w+k,x=a+i,y=x+k;j<k;j++,W++,x++,y++)
*y=1ll*(*x+mod-(z=*y))* *W%mod,*x=md(*x+z);
}
inline void IDNT(int *a,int mmax)
{
for(int i,j,k=1,L,*W,*x,*y,z;k<mmax;k<<=1)
for(L=k<<1,i=0;i<mmax;i+=L)
for(j=0,W=w+k,x=a+i,y=x+k;j<k;j++,W++,x++,y++)
z=1ll* *W* *y%mod,*y=md(*x+mod-z),*x=md(*x+z);
reverse(a+1,a+mmax);
for(int inv=ksm(mmax,mod-2),i=0;i<mmax;i++) a[i]=1ll*a[i]*inv%mod;
}
inline void NTT(int *a,int *b,int n,int m)
{
mmax=bger(n+m);init(mmax);
DNT(a,mmax);DNT(b,mmax);
for(int i=0;i<mmax;i++) a[i]=1ll*a[i]*b[i]%mod;
IDNT(a,mmax);
}
void INV(int num,int *a,int *b)
{
if(num==1) return b[0]=ksm(a[0],mod-2),void();
INV((num+1)>>1,a,b);
int mmax=bger(num<<1);init(mmax);
static int c[N];
for(int i=0;i<num;i++) c[i]=a[i];for(int i=num;i<mmax;i++) c[i]=0;
DNT(c,mmax);DNT(b,mmax);
for(int i=0;i<mmax;i++) b[i]=1ll*(2-1ll*c[i]*b[i]%mod+mod)%mod*b[i]%mod;
IDNT(b,mmax);
for(int i=num;i<mmax;i++) b[i]=0;
}
inline void Ln(int *a,int n){static int b[N];for(int i=0;i<bger(n<<1);i++) b[i]=0;INV(n,a,b);dao(a,n);NTT(a,b,n,n);ji(a,n);for(int i=n;i<bger(n<<1);i++) a[i]=0;}
inline void Exp(int *a,int *b,int n)
{
if(n==1) return b[0]=1,void();
Exp(a,b,(n+1)>>1);static int c[N];for(int i=0;i<bger(n<<1);i++) c[i]=0;
for(int i=0;i<n;i++) c[i]=b[i];Ln(c,n);
for(int i=0;i<n;i++) c[i]=md(mod-c[i]+a[i]);c[0]=md(c[0]+1);
NTT(b,c,n,n);for(int i=n;i<bger(n<<1);i++) b[i]=0;
}
int main()
{
n=rd();m=rd();for(int i=0;i<n;i++) a[i]=rd();
Ln(a,n);for(int i=0;i<n;i++) a[i]=1ll*a[i]*m%mod;
Exp(a,b,n);for(int i=0;i<n;i++) wr(b[i]);
return 0;
}
加强版只需注意到：
由于费马小定理，幂次可以对 \(998244352\) 取模。
\(A(x)^k=c^k\left(\dfrac{A(x)}{c}\right)^k\)，而后求后面的幂次。
设 \(A(x)=\sum\limits_{i=0}^{n-1} a_ix^i\)，第一个非零次为 \(x^t\)，则 \(A(x)^k=x^{tk}\left(\sum\limits_{i=t}^{n-1}a_ix^{i-t}\right)^k\)，而后求后面的幂次。
于是就能转化为 \(a_0=1\) 的情况啦。复杂度不变。当然加强版基本 useless 啦！
$\texttt{code}$
//落谷 P4726
//https://www.luogu.com.cn/problem/P4726
#include<bits/stdc++.h>
#define fr(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using namespace std;
const int mod=998244353,N=4e5+5;
int n,m,a[N],b[N],w[N],mmax;
char str[N];
inline int rd()
{
int x=0,zf=1;
char ch=getchar();
while(ch<'0'||ch>'9') (ch=='-')and(zf=-1),ch=getchar();
while(ch>='0'&&ch<='9') x=(10*x+ch-'0'),ch=getchar();
return x*zf;
}
inline void wr(int x)
{
if(x==0) return putchar('0'),putchar(' '),void();
int num[35],len=0;
while(x) num[++len]=x%10,x/=10;
for(int i=len;i>=1;i--) putchar(num[i]+'0');
putchar(' ');
}
inline int bger(int x){return x|=x>>1,x|=x>>2,x|=x>>4,x|=x>>8,x|=x>>16,x+1;}
inline int md(int x){return x>=mod?x-mod:x;}
inline int ksm(int x,int p){int s=1;for(;p;(p&1)&&(s=1ll*s*x%mod),x=1ll*x*x%mod,p>>=1);return s;}
inline void dao(int *a,int n){for(int i=1;i<n;i++) a[i-1]=1ll*i*a[i]%mod;a[n-1]=0;}
inline void ji(int *a,int n){for(int i=n-1;i>=1;i--) a[i]=1ll*ksm(i,mod-2)*a[i-1]%mod;a[0]=0;}
inline void init(int mmax)
{
for(int i=1,j,k;i<mmax;i<<=1)
for(w[j=i]=1,k=ksm(3,(mod-1)/(i<<1)),j++;j<(i<<1);j++)
w[j]=1ll*w[j-1]*k%mod;
}
inline void DNT(int *a,int mmax)
{
for(int i,j,k=mmax>>1,L,*W,*x,*y,z;k;k>>=1)
for(L=k<<1,i=0;i<mmax;i+=L)
for(j=0,W=w+k,x=a+i,y=x+k;j<k;j++,W++,x++,y++)
*y=1ll*(*x+mod-(z=*y))* *W%mod,*x=md(*x+z);
}
inline void IDNT(int *a,int mmax)
{
for(int i,j,k=1,L,*W,*x,*y,z;k<mmax;k<<=1)
for(L=k<<1,i=0;i<mmax;i+=L)
for(j=0,W=w+k,x=a+i,y=x+k;j<k;j++,W++,x++,y++)
z=1ll* *W* *y%mod,*y=md(*x+mod-z),*x=md(*x+z);
reverse(a+1,a+mmax);
for(int inv=ksm(mmax,mod-2),i=0;i<mmax;i++) a[i]=1ll*a[i]*inv%mod;
}
inline void NTT(int *a,int *b,int n,int m)
{
mmax=bger(n+m);init(mmax);
DNT(a,mmax);DNT(b,mmax);
for(int i=0;i<mmax;i++) a[i]=1ll*a[i]*b[i]%mod;
IDNT(a,mmax);
}
void INV(int num,int *a,int *b)
{
if(num==1) return b[0]=ksm(a[0],mod-2),void();
INV((num+1)>>1,a,b);
int mmax=bger(num<<1);init(mmax);
static int c[N];
for(int i=0;i<num;i++) c[i]=a[i];for(int i=num;i<mmax;i++) c[i]=0;
DNT(c,mmax);DNT(b,mmax);
for(int i=0;i<mmax;i++) b[i]=1ll*(2-1ll*c[i]*b[i]%mod+mod)%mod*b[i]%mod;
IDNT(b,mmax);
for(int i=num;i<mmax;i++) b[i]=0;
}
inline void Ln(int *a,int n){static int b[N];for(int i=0;i<bger(n<<1);i++) b[i]=0;INV(n,a,b);dao(a,n);NTT(a,b,n,n);ji(a,n);for(int i=n;i<bger(n<<1);i++) a[i]=0;}
inline void Exp(int *a,int *b,int n)
{
if(n==1) return b[0]=1,void();
Exp(a,b,(n+1)>>1);static int c[N];for(int i=0;i<bger(n<<1);i++) c[i]=0;
for(int i=0;i<n;i++) c[i]=b[i];Ln(c,n);
for(int i=0;i<n;i++) c[i]=md(mod-c[i]+a[i]);c[0]=md(c[0]+1);
NTT(b,c,n,n);for(int i=n;i<bger(n<<1);i++) b[i]=0;
}
inline void ksm(int *a,char *str,int n)
{
int t=n,t1,t2,t3,L=strlen(str),X=0,XX=0;
static int A[N],b[N];for(int i=0;i<n;i++) A[i]=b[i]=0;
for(int i=0;i<L;i++) m=(10ll*m%mod+str[i]-'0')%mod;
for(int i=0;i<L;i++) X=(10ll*X%(mod-1)+str[i]-'0')%(mod-1);
for(int i=0;i<min(L,7);i++) XX=(10*XX+str[i]-'0');
if(a[0]==0&&XX>=n){for(int i=0;i<n;i++) a[i]=0;return;}
for(int i=0;i<n;i++) if(a[i]!=0){t=i;break;}
for(int i=t;i<n;i++) A[i-t]=a[i];t1=ksm(A[0],mod-2),t2=ksm(A[0],X);
for(int i=0;i<n-t;i++) A[i]=1ll*A[i]*t1%mod;
Ln(A,n-t);for(int i=0;i<n-t;i++) A[i]=1ll*A[i]*m%mod;t3=min(1ll*t*m,1ll*n);
Exp(A,b,n-t);for(int i=0;i<t3;i++) A[i]=0;for(int i=t3;i<n;i++) A[i]=1ll*b[i-t3]*t2%mod;
for(int i=0;i<n;i++) a[i]=A[i];
}
int main()
{
n=rd();scanf("%s",str);
for(int i=0;i<n;i++) a[i]=rd();
ksm(a,str,n);for(int i=0;i<n;i++) wr(a[i]);
return 0;
}
多项式开根/加强版
给定一个 \(n-1\) 次多项式 \(A(x)\) ，求一个在 \(\bmod\ {x^n}\) 意义下的多项式 \(B(x)\) ，使得 \(B^2(x)\equiv A(x)\pmod {x^n}\)。
多项式的系数在 \(\bmod\ 998244353\) 的意义下进行运算。
普通版保证 \(a_0=1\)，加强版仅保证 \(a_0\) 是 \(\bmod\ 998244353\) 的二次剩余。
直接讲加强版，设我们求出 \(a_0\) 的二次剩余为 \(r\)。
考虑牛顿迭代。\(g(X)=X^2-A(x)\)，则 \(g(B(x))\equiv 0\pmod {x^n}\)。
设 \(B_0(x)\) 满足 \(g(B_0(x))\equiv 0\pmod {x^{\lceil x/2\rceil}}\)
则 \(B(x)\equiv B_0(x)-\dfrac{g(B_0(x))}{g'(B_0(x))}=B_0(x)-\dfrac{B_0(x)^2-A(x)}{2B_0(x)}=\dfrac{B_0(x)}{2}+\dfrac{A(x)}{2B_0(x)}\pmod {x^n}\)。
于是这里一次多项式求逆即可，边界时 \(n=1\)，\(B(x)=r\)。
复杂度 \(T(n)=T(n/2)+O(n\log n)=O(n\log n)\)。
加强版 $\texttt{code}$
//洛谷 P5277
//https://www.luogu.com.cn/problem/P5277
#include<bits/stdc++.h>
#define fr(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
#define LL long long
using namespace std;
const int mod=998244353,N=4e6+5;
int n,m,a[N],b[N],c,w[N],jc[N],inv[N],mmax;
inline int rd()
{
int x=0,zf=1;char ch=getchar();
while(ch<'0'||ch>'9') (ch=='-')and(zf=-1),ch=getchar();
while(ch>='0'&&ch<='9') x=((x<<3)+(x<<1)+ch-'0')%mod,ch=getchar();
return x*zf;
}
inline void wr(int x)
{
if(x==0) return putchar('0'),putchar(' '),void();
int num[35],len=0;
while(x) num[++len]=x%10,x/=10;
for(int i=len;i>=1;i--) putchar(num[i]+'0');
putchar(' ');
}
inline int bger(int x){return x|=x>>1,x|=x>>2,x|=x>>4,x|=x>>8,x|=x>>16,x+1;}
inline int md(int x){return x>=mod?x-mod:x;}
inline int yy(int x){if(x&1) return (x+mod)>>1;return x>>1;}
inline int ksm(int x,int p){int s=1;for(;p;(p&1)&&(s=1ll*s*x%mod),x=1ll*x*x%mod,p>>=1);return s;}
inline void dao(int *a,int n){for(int i=1;i<n;i++) a[i-1]=1ll*i*a[i]%mod;a[n-1]=0;}
inline void ji(int *a,int n){for(int i=n-1;i>=1;i--) a[i]=1ll*ksm(i,mod-2)*a[i-1]%mod;a[0]=0;}
namespace er
{
int n,w;
struct comp
{
int x,y;
inline comp operator *(comp X){return {(1ll*x*X.x+1ll*y*X.y%mod*w)%mod,(1ll*x*X.y+1ll*y*X.x)%mod};}
};
inline comp ksm1(comp x,int p){comp s={1,0};for(;p;(p&1)&&(s=s*x,1),x=x*x,p>>=1);return s;}
inline int Find()
{
int x;
while(1)
{
x=rand()%mod;w=((LL)x*x%mod-n+mod)%mod;
if(ksm(w,(mod-1)>>1)==mod-1) break;
}
return ksm1({x,1},(mod+1)>>1).x;
}
}using er::Find;
inline void init(int mmax)
{
for(int i=1,j,k;i<mmax;i<<=1)
for(w[j=i]=1,k=ksm(3,(mod-1)/(i<<1)),j++;j<(i<<1);j++)
w[j]=1ll*w[j-1]*k%mod;
}
inline void DNT(int *a,int mmax)
{
for(int i,j,k=mmax>>1,L,*W,*x,*y,z;k;k>>=1)
for(L=k<<1,i=0;i<mmax;i+=L)
for(j=0,W=w+k,x=a+i,y=x+k;j<k;j++,W++,x++,y++)
*y=1ll*(*x+mod-(z=*y))* *W%mod,*x=md(*x+z);
}
inline void IDNT(int *a,int mmax)
{
for(int i,j,k=1,L,*W,*x,*y,z;k<mmax;k<<=1)
for(L=k<<1,i=0;i<mmax;i+=L)
for(j=0,W=w+k,x=a+i,y=x+k;j<k;j++,W++,x++,y++)
z=1ll* *W* *y%mod,*y=md(*x+mod-z),*x=md(*x+z);
reverse(a+1,a+mmax);
for(int inv=ksm(mmax,mod-2),i=0;i<mmax;i++) a[i]=1ll*a[i]*inv%mod;
}
inline void NTT(int *a,int *b,int n,int m)
{
mmax=bger(n+m);init(mmax);
DNT(a,mmax);DNT(b,mmax);
for(int i=0;i<mmax;i++) a[i]=1ll*a[i]*b[i]%mod;
IDNT(a,mmax);
}
void INV(int num,int *a,int *b)
{
if(num==1) return b[0]=ksm(a[0],mod-2),void();INV((num+1)>>1,a,b);
int mmax=bger(num<<1);init(mmax);static int c[N];
for(int i=0;i<num;i++) c[i]=a[i];for(int i=num;i<mmax;i++) c[i]=0;DNT(c,mmax);DNT(b,mmax);
for(int i=0;i<mmax;i++) b[i]=1ll*(2-1ll*c[i]*b[i]%mod+mod)%mod*b[i]%mod;IDNT(b,mmax);
for(int i=num;i<mmax;i++) b[i]=0;
}
void SQ(int n,int *a,int *b)
{
if(n==1) return b[0]=c,void();SQ((n+1)>>1,a,b);static int c[N],d[N];
for(int i=0;i<n;i++) c[i]=b[i];INV(n,c,d);for(int i=n;i<mmax;i++) c[i]=d[i]=0;
for(int i=0;i<n;i++) c[i]=a[i];NTT(c,d,n-1,n-1);
for(int i=0;i<n;i++) b[i]=yy(md(c[i]+b[i]));
for(int i=0;i<mmax;i++) c[i]=d[i]=0;
}
int main()
{
srand(time(NULL));n=rd();for(int i=0;i<n;i++) a[i]=rd();
er::n=a[0];c=Find();SQ(n,a,b);
for(int i=0;i<n;i++) wr((b[0]<=mod-b[0])?b[i]:mod-b[i]);
return 0;
}
挑战多项式
按照惯例需要给出挑战多项式的代码作为小全家桶。代码。