很多证明需要用到积分知识，所以只有结论和代码
一、多项式求导
$F'(x)=\sum_{i=0}a_{i+1}\times (i+1)x $
点击查看代码
inline void dao(int *g,int *f){
for(int i=0;i<n;++i) g[i]=f[i+1]*(i+1)%mod;
}
二、多项式求积分
求导逆运算
$F'(x)=\sum_{i=1}a_{i-1}\times \frac{1}{i}x $
点击查看代码
inline void jifen(int *g,int *f){
for(int i=1;i<=n;++i) g[i]=f[i-1]*power(i,mod-2)%mod;
}
三、多项式求逆
不取模
点击查看代码
void ni(int len){
if(len==1){g[0]=power(f[0],mod-2);return;}
solve(len>>1);work(len);
for(int i=0;i<len;i++) a[i]=f[i],b[i]=g[i];
for(int i=len;i<bl;i++) a[i]=b[i]=0; NTT(a,bl,1);NTT(b,bl,1);
for(int i=0;i<bl;i++) a[i]=1ll*a[i]*b[i]%mod*b[i]%mod; NTT(a,bl,-1);
for(int i=0;i<len;i++) g[i]=((2ll*g[i]%mod-a[i])%mod+mod)%mod;
}
四、多项式求ln
求导后积分
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int MAX=6e5+10;
#define int long long
const int mod=998244353,G=3;
int n,m=1,bl,bc,rev[MAX],a[MAX],b[MAX],f[MAX],g[MAX],g2[MAX];
inline int read(){
int x=0,f=1;char c=getchar();
while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^'0');c=getchar();}
return x*f;
}
inline int power(int a,int b){
int res=1;
while(b){
if(b&1) res=res*a%mod;
a=a*a%mod;b>>=1;
}return res;
}inline void NTT(int*,int,int);
void solve(int);
inline void work(int len){
bl=1;bc=0;
while(bl<=len) bl<<=1,++bc;
for(int i=0;i<bl;++i)
rev[i]=(rev[i>>1]>>1)|((i&1)<<bc-1);
}
inline void dao(int *g,int *f){
for(int i=0;i<n;++i) g[i]=f[i+1]*(i+1)%mod;
}inline void jifen(int *g,int n){
for(int i=n;i;--i) g[i]=g[i-1]*power(i,mod-2)%mod;
g[0]=0;
}
signed main(){
n=read();
for(int i=0;i<n;++i) f[i]=read();
while(m<=n) m<<=1;
solve(m);work(n<<1);dao(g2,f);
//g=invf g2=f'
NTT(g,bl,1);NTT(g2,bl,1);
for(int i=0;i<bl;++i) g[i]=g[i]*g2[i]%mod;
NTT(g,bl,-1);
//g=lnf'
jifen(g,bl);
for(int i=0;i<n;++i) printf("%lld ",g[i]);
}
void solve(int len){
if(len==1){g[0]=power(f[0],mod-2);return;}
solve(len>>1);work(len);
for(int i=0;i<len;i++) a[i]=f[i],b[i]=g[i];
for(int i=len;i<bl;i++) a[i]=b[i]=0; NTT(a,bl,1);NTT(b,bl,1);
for(int i=0;i<bl;i++) a[i]=1ll*a[i]*b[i]%mod*b[i]%mod; NTT(a,bl,-1);
for(int i=0;i<len;i++) g[i]=((2ll*g[i]%mod-a[i])%mod+mod)%mod;
}inline void NTT(int *a,int n,int op){
for(int i=0;i<n;++i)
if(i<rev[i]) swap(a[i],a[rev[i]]);
for(int i=1;i<n;i<<=1){
int wn=power(G,(op*(mod-1)/(i<<1)+mod-1)%(mod-1));
for(int j=0;j<n;j+=i<<1){
int w=1;
for(int k=0;k<i;++k){
int x=a[j+k],y=a[j+k+i]*w%mod;
a[j+k]=(x+y)%mod;a[j+k+i]=(x-y+mod)%mod;
w=w*wn%mod;
}
}
}if(op==-1){
int inv=power(n,mod-2);
for(int i=0;i<n;++i) a[i]=a[i]*inv%mod;
}
}