博主太菜惹。。。只放模板。。。
(FFT)
#include<bits/stdc++.h>
#define IL inline
#define LF double
using namespace std;
const int N=4e6+3;
const LF Pi=acos(-1.0);
int n,m,lim=1,cnt,r[N],tp;
struct comp{
LF x,y;
comp(LF xx=0,LF yy=0){x=xx,y=yy;}
IL comp operator+(const comp &a) const{return comp(x+a.x,y+a.y);}
IL comp operator-(const comp &a) const{return comp(x-a.x,y-a.y);}
IL comp operator*(const comp &a) const{return comp(x*a.x-y*a.y,x*a.y+y*a.x);}
}a[N],b[N];
IL int in(){
char c;int f=1;
while((c=getchar())<'0'||c>'9')
if(c=='-') f-1;
int x=c-'0';
while((c=getchar())>='0'&&c<='9')
x=x*10+c-'0';
return x*f;
}
void FFT(comp *a,int op){
for(int i=0;i<lim;++i) if(i<r[i]) swap(a[i],a[r[i]]);
for(int i=1;i<lim;i<<=1){
comp wn(cos(Pi/i),op*sin(Pi/i));
for(int j=0;j<lim;j+=i<<1){
comp w(1,0);
for(int k=0;k<i;++k,w=w*wn){
comp x=a[j+k],y=w*a[j+i+k];
a[j+k]=x+y,a[j+i+k]=x-y;
}
}
}
if(op==-1) for(int i=0;i<lim;++i) a[i].x=a[i].x/lim;
}
int main()
{
n=in()+1,m=in()+1;
while(lim<n+m) lim<<=1,++cnt;
for(int i=0;i<lim;++i) r[i]=(r[i>>1]>>1)|((i&1)<<cnt-1);
for(int i=0;i<n;++i) a[i].x=in();
for(int i=0;i<m;++i) b[i].x=in();
FFT(a,1),FFT(b,1);
for(int i=0;i<lim;++i) a[i]=a[i]*b[i];
FFT(a,-1);
for(int i=0;i<n+m-1;++i) printf("%d ",(int)(a[i].x/lim+0.5));
return 0;
}
(NTT)
#include<bits/stdc++.h>
#define IL inline
#define LL long long
using namespace std;
const int N=4e6+3,p=998244353,G=3,Gi=332748118;
int n,m,a[N],b[N],r[N],lim=1,cnt,inv;
IL int in(){
char c;int f=1;
while((c=getchar())<'0'||c>'9')
if(c=='-') f=-1;
int x=c-'0';
while((c=getchar())>='0'&&c<='9')
x=x*10+c-'0';
return x*f;
}
IL int ksm(int a,int b){
int c=1;
while(b){
if(b&1) c=1ll*c*a%p;
a=1ll*a*a%p,b>>=1;
}
return c;
}
void NTT(int *a,int op){
for(int i=0;i<lim;++i) if(i<r[i]) swap(a[i],a[r[i]]);
for(int i=1;i<lim;i<<=1){
int wn=ksm(op?G:Gi,(p-1)/(i<<1));
for(int j=0;j<lim;j+=(i<<1)){
int w=1;
for(int k=0;k<i;++k,w=1ll*w*wn%p){
int x=a[j+k],y=1ll*w*a[j+i+k]%p;
a[j+k]=(x+y)%p,a[j+i+k]=(x-y+p)%p;
}
}
}
}
int main()
{
n=in()+1,m=in()+1;
for(int i=0;i<n;++i) a[i]=in();
for(int i=0;i<m;++i) b[i]=in();
while(lim<n+m) lim<<=1,++cnt;
for(int i=0;i<lim;++i) r[i]=(r[i>>1]>>1)|((i&1)<<cnt-1);
NTT(a,1),NTT(b,1);
for(int i=0;i<lim;++i) a[i]=1ll*a[i]*b[i]%p;
NTT(a,0),inv=ksm(lim,p-2);
for(int i=0;i<n+m-1;++i) printf("%lld ",1ll*a[i]*inv%p);
return 0;
}
多项式求逆
#include<bits/stdc++.h>
#define IL inline
#define LL long long
#define re register
using namespace std;
const int N=4e5+3,p=998244353,G=3,Gi=332748118;
int n,r[N],lim=1,op,cnt,bas;
LL a[N],b[N],c[N],d[N];
IL int in(){
char c;int f=1;
while((c=getchar())<'0'||c>'9')
if(c=='-') f=-1;
re int x=c-'0';
while((c=getchar())>='0'&&c<='9')
x=x*10+c-'0';
return x*f;
}
IL LL ksm(re LL a,re LL b){
re LL c=1;
while(b){
if(b&1) c=c*a%p;
a=a*a%p,b>>=1;
}
return c;
}
IL LL mod(LL x){return x>=p?x-p:x;}
IL void calc(int lim){
for(re int i=0;i<lim;++i) r[i]=(r[i>>1]>>1)|((i&1)*(lim>>1));
}
IL void NTT(LL *a,int op){
for(re int i=0;i<lim;++i) if(i<r[i]) swap(a[i],a[r[i]]);
for(re int i=1;i<lim;i<<=1){
LL wn=ksm(~op?G:Gi,(p-1)/(i<<1));
for(re int j=0;j<lim;j+=(i<<1)){
LL w=1;
for(re int k=0;k<i;++k,w=w*wn%p){
LL x=a[j+k],y=w*a[j+i+k]%p;
a[j+k]=mod(x+y),a[j+i+k]=mod(x-y+p);
}
}
}
if(op==-1){
LL inv=ksm(lim,p-2);
for(re int i=0;i<lim;++i) a[i]=a[i]*inv%p;
}
}
void solve(LL *a,LL *b,int n){
if(n==1){b[0]=ksm(a[0],p-2);return;}
solve(a,b,n+1>>1);lim=1;
while(lim<(n<<1)) lim<<=1;calc(lim);
memcpy(c,a,8*n),memset(c+n,0,8*(lim-n));
NTT(c,1),NTT(b,1);
for(re int i=0;i<lim;++i) b[i]=mod(2+p-b[i]*c[i]%p)*b[i]%p;
NTT(b,-1),memset(b+n,0,8*(lim-n));
}
int main()
{
n=in();
for(re int i=0;i<n;++i) a[i]=in();
solve(a,b,n);
for(re int i=0;i<n;++i) printf("%lld ",b[i]);
return 0;
}
多项式除法
#include<bits/stdc++.h>
#define IL inline
#define LL long long
#define re register
using namespace std;
const int N=4e5+3,p=998244353,G=3,Gi=332748118;
int n,m,K,lim,r[N];
LL f[N],fr[N],g[N],gr[N],gv[N],q[N],R[N],a[N],b[N],c[N];
IL int in(){
char c;int f=1;
while((c=getchar())<'0'||c>'9')
if(c=='-') f=-1;
re int x=c-'0';
while((c=getchar())>='0'&&c<='9')
x=x*10+c-'0';
return x*f;
}
IL LL ksm(re LL a,re LL b){
re LL c=1;
while(b){
if(b&1) c=c*a%p;
a=a*a%p,b>>=1;
}
return c;
}
IL LL mod(LL x){return x>=p?x-p:x;}
IL void calcrev(int lim){
for(re int i=0;i<lim;++i) r[i]=(r[i>>1]>>1)|((i&1)*(lim>>1));
}
void init(){
n=in()+1,m=in()+1,K=n-m+1;
for(re int i=0;i<n;++i) f[i]=fr[i]=in();
for(re int i=0;i<m;++i) g[i]=gr[i]=in();
reverse(fr,fr+n),reverse(gr,gr+m);
}
IL void NTT(LL *a,int lim,int op){
for(re int i=0;i<lim;++i) if(i<r[i]) swap(a[i],a[r[i]]);
for(re int i=1;i<lim;i<<=1){
re LL wn=ksm(~op?G:Gi,(p-1)/(i<<1));
for(re int j=0;j<lim;j+=(i<<1)){
re LL w=1;
for(re int k=0;k<i;++k,w=w*wn%p){
LL x=a[j+k],y=w*a[j+i+k]%p;
a[j+k]=mod(x+y),a[j+i+k]=mod(x-y+p);
}
}
}
if(op==-1){
LL inv=ksm(lim,p-2);
for(re int i=0;i<lim;++i) a[i]=a[i]*inv%p;
}
}
void get_inv(LL *a,LL *b,int n){
if(n==1){b[0]=ksm(a[0],p-2);return;}
get_inv(a,b,n+1>>1);
lim=1;while(lim<(n<<1)) lim<<=1;calcrev(lim);
memcpy(c,a,8*n),memset(c+n,0,8*(lim-n));
NTT(c,lim,1),NTT(b,lim,1);
for(re int i=0;i<lim;++i) b[i]=mod(2-b[i]*c[i]%p+p)*b[i]%p;
NTT(b,lim,-1),memset(b+n,0,8*(lim-n));
}
IL void mul(LL *a,LL *b,int n,int m){
lim=1;while(lim<n+m) lim<<=1;calcrev(lim);
memcpy(c,b,8*m),memset(c+m,0,8*(lim-m)),memset(a+n,0,8*(lim-n));
NTT(a,lim,1),NTT(c,lim,1);
for(int i=0;i<lim;++i) a[i]=c[i]*a[i]%p;
NTT(a,lim,-1);
}
void divid(){
get_inv(gr,gv,K);
memcpy(q,fr,8*n);
mul(q,gv,n,K);
reverse(q,q+K);
mul(g,q,m,K);
for(re int i=0;i<m-1;++i) R[i]=mod(f[i]-g[i]+p);
for(re int i=0;i<K;++i) printf("%lld ",q[i]);printf("
");
for(re int i=0;i<m-1;++i) printf("%lld ",R[i]);
}
int main()
{
init();
divid();
return 0;
}
多项式对数函数
#include<bits/stdc++.h>
#define IL inline
#define LL long long
using namespace std;
const int N=4e5+3,p=998244353,G=3,Gi=332748118;
int n,lim=1,r[N];
LL a[N],b[N],c[N],f[N],g[N];
IL int in(){
char c;int f=1;
while((c=getchar())<'0'||c>'9')
if(c=='-') f-1;
int x=c-'0';
while((c=getchar())>='0'&&c<='9')
x=x*10+c-'0';
return x*f;
}
IL LL mod(LL x){return x>=p?x-p:x;}
IL LL ksm(LL a,LL b){
LL c=1;
while(b){
if(b&1) c=c*a%p;
a=a*a%p,b>>=1;
}
return c;
}
IL void calc(int lim){
for(int i=0;i<lim;++i) r[i]=(r[i>>1]>>1)|((i&1)*(lim>>1));
}
void NTT(LL *a,int lim,int op){
for(int i=0;i<lim;++i) if(i<r[i]) swap(a[i],a[r[i]]);
for(int i=1;i<lim;i<<=1){
LL wn=ksm(~op?G:Gi,(p-1)/(i<<1));
for(int j=0;j<lim;j+=i<<1){
LL w=1;
for(int k=0;k<i;++k,w=w*wn%p){
LL x=a[j+k],y=w*a[j+i+k]%p;
a[j+k]=mod(x+y),a[j+i+k]=mod(x-y+p);
}
}
}
if(op==-1){
LL inv=ksm(lim,p-2);
for(int i=0;i<lim;++i) a[i]=a[i]*inv%p;
}
}
void get_inv(LL *a,LL *b,int n){
if(n==1){b[0]=ksm(a[0],p-2);return;}
get_inv(a,b,n+1>>1);
lim=1;while(lim<2*n) lim<<=1;calc(lim);
memcpy(c,a,8*n),memset(c+n,0,8*(lim-n));
NTT(c,lim,1),NTT(b,lim,1);
for(int i=0;i<lim;++i) b[i]=mod(2-c[i]*b[i]%p+p)*b[i]%p;
NTT(b,lim,-1),memset(b+n,0,8*(lim-n));
}
IL void get_dao(LL *a,LL *b,int n){for(int i=0;i<n-1;++i) b[i]=(i+1)*a[i+1]%p;b[n-1]=0;}
IL void jifen(LL *a,LL *b,int n){for(int i=1;i<n;++i) b[i]=a[i-1]*ksm(i,p-2)%p;b[0]=0;}
IL void get_ln(LL *f,LL *g,int n){
get_dao(f,a,n),get_inv(f,b,n);
lim=1;while(lim<2*n) lim<<=1;calc(lim);
NTT(a,lim,1),NTT(b,lim,1);
for(int i=0;i<lim;++i) a[i]=a[i]*b[i]%p;
NTT(a,lim,-1),jifen(a,g,n);
}
int main()
{
n=in();
for(int i=0;i<n;++i) f[i]=in();
get_ln(f,g,n);
for(int i=0;i<n;++i) printf("%lld ",g[i]);
return 0;
}
多项式 (exp)
#include<bits/stdc++.h>
#define IL inline
using namespace std;
const int N=4e5+3,p=998244353,G=3,Gi=332748118;
int n,m,a[N],b[N],r[N],inv[N];
IL int in(){
char c;int f=1;
while((c=getchar())<'0'||c>'9')
if(c=='-') f=-1;
int x=c-'0';
while((c=getchar())>='0'&&c<='9')
x=x*10+c-'0';
return x*f;
}
IL int mod(int x){return x>=p?x-p:x;}
IL void calc(int lim){
for(int i=0;i<lim;++i) r[i]=(r[i>>1]>>1)|((i&1)*(lim>>1));
}
IL int ksm(int a,int b){
int c=1;
while(b){
if(b&1) c=1ll*c*a%p;
b>>=1,a=1ll*a*a%p;
}
return c;
}
void NTT(int *a,int lim,int op){
calc(lim);
for(int i=0;i<lim;++i) if(i<r[i]) swap(a[i],a[r[i]]);
for(int i=1;i<lim;i<<=1){
int wn=ksm(op>0?G:Gi,(p-1)/(i<<1));
for(int j=0;j<lim;j+=i<<1){
int w=1;
for(int k=0;k<i;++k,w=1ll*w*wn%p){
int x=a[j+k],y=1ll*w*a[j+i+k]%p;
a[j+k]=mod(x+y),a[j+i+k]=mod(x-y+p);
}
}
}
if(op==-1){
int inv=ksm(lim,p-2);
for(int i=0;i<lim;++i) a[i]=1ll*a[i]*inv%p;
}
}
void get_inv(int *a,int *b,int n){
if(n==1){b[0]=ksm(a[0],p-2);b[1]=0;return;}
get_inv(a,b,n+1>>1);
int c[N],lim=1;
while(lim<n+n) lim<<=1;
memcpy(c,a,4*n),memset(c+n,0,4*(lim-n)),
memset(b+n,0,4*(lim-n));
NTT(b,lim,1),NTT(c,lim,1);
for(int i=0;i<lim;++i) b[i]=1ll*mod(2-1ll*c[i]*b[i]%p+p)*b[i]%p;
NTT(b,lim,-1);memset(b+n,0,4*(lim-n));
}
void mul(int *a,int *b,int *c,int n,int m){
int _a[N],_b[N],lim=1;
while(lim<n+m) lim<<=1;
memcpy(_a,a,4*n),memcpy(_b,b,4*m),
memset(_a+n,0,4*(lim-n)),memset(_b+m,0,4*(lim-m));
NTT(_a,lim,1),NTT(_b,lim,1);
for(int i=0;i<lim;++i) c[i]=1ll*_a[i]*_b[i]%p;
NTT(c,lim,-1);
}
void dao(int *a,int *b,int n){for(int i=0;i<n-1;++i) b[i]=1ll*a[i+1]*(i+1)%p;b[n-1]=0;}
void jifen(int *a,int *b,int n){for(int i=n-1;i;--i) b[i]=1ll*a[i-1]*inv[i]%p;b[0]=0;}
IL void get_ln(int *a,int *b,int n){
int c[N],d[N];
dao(a,c,n),get_inv(a,d,n),
mul(c,d,c,n,n),jifen(c,b,n);
}
void get_exp(int *a,int *b,int n){
if(n==1){b[0]=1;b[1]=0;return;}
get_exp(a,b,n+1>>1);
int c[N],d[N],lim=1;
while(lim<n+n) lim<<=1;
get_ln(b,c,n),memset(c+n,0,4*(lim-n));
d[0]=(a[0]+1-c[0])%p;
for(int i=1;i<n;++i) d[i]=mod(a[i]-c[i]+p);
memset(d+n,0,4*(lim-n));
mul(b,d,b,n,n),memset(b+n,0,4*(lim-n));
}
void pre(int n){
inv[0]=inv[1]=1;
for(int i=2;i<=n;++i)
inv[i]=1ll*(p-p/i)*inv[p%i]%p;
}
int main()
{
n=in();pre(n+n);
for(int i=0;i<n;++i) a[i]=in();
get_exp(a,b,n);
for(int i=0;i<n;++i) printf("%d ",b[i]);
putchar('
');
return 0;
}
多项式开根
#include<bits/stdc++.h>
#define IL inline
#define LL long long
using namespace std;
const int N=4e5+3,p=998244353,G=3,Gi=332748118;
int n,m,a[N],b[N],r[N];
IL int in(){
char c;int f=1;
while((c=getchar())<'0'||c>'9')
if(c=='-') f=-1;
int x=c-'0';
while((c=getchar())>='0'&&c<='9')
x=x*10+c-'0';
return x*f;
}
IL int ksm(int a,int b){
int c=1;
while(b){
if(b&1) c=1ll*c*a%p;
a=1ll*a*a%p,b>>=1;
}
return c;
}
IL int mod(int x){return x>=p?x-p:x;}
IL void calc(int lim){
for(int i=0;i<lim;++i) r[i]=(r[i>>1]>>1)|((i&1)*(lim>>1));
}
void NTT(int *a,int lim,int op){
calc(lim);
for(int i=0;i<lim;++i) if(i<r[i]) swap(a[i],a[r[i]]);
for(int i=1;i<lim;i<<=1){
int wn=ksm(op>0?G:Gi,(p-1)/(i<<1));
for(int j=0;j<lim;j+=i<<1){
int w=1;
for(int k=0;k<i;++k,w=1ll*w*wn%p){
int x=a[j+k],y=1ll*w*a[j+i+k]%p;
a[j+k]=mod(x+y),a[j+i+k]=mod(x-y+p);
}
}
}
if(op==-1){
int inv=ksm(lim,p-2);
for(int i=0;i<lim;++i) a[i]=1ll*a[i]*inv%p;
}
}
void get_inv(int *a,int *b,int n){
if(n==1){b[0]=ksm(a[0],p-2);b[1]=0;return;}
get_inv(a,b,n+1>>1);
int lim=1,c[N];
while(lim<2*n) lim<<=1;
memcpy(c,a,4*n),memset(c+n,0,4*(lim-n));
memset(b+n,0,4*(lim-n));
NTT(c,lim,1),NTT(b,lim,1);
for(int i=0;i<lim;++i) b[i]=1ll*mod(2-1ll*c[i]*b[i]%p+p)*b[i]%p;
NTT(b,lim,-1);memset(b+n,0,4*(lim-n));
}
void mul(int *a,int *b,int *c,int n,int m){
int lim=1,_a[N],_b[N];
while(lim<n+m) lim<<=1;
memcpy(_a,a,4*n),memcpy(_b,b,4*m),
memset(_a+n,0,4*(lim-n)),memset(_b+m,0,4*(lim-m));
NTT(_a,lim,1),NTT(_b,lim,1);
for(int i=0;i<lim;++i) _a[i]=1ll*_a[i]*_b[i]%p;
NTT(_a,lim,-1);memcpy(c,_a,4*lim);
}
void get_sqrt(int *a,int *b,int n){
if(n==1){b[0]=1;return;}
get_sqrt(a,b,n+1>>1);
int lim=1,c[N],d[N],e[N];
while(lim<2*n) lim<<=1;
for(int i=0;i<n;++i) d[i]=mod(2*b[i]);
get_inv(d,e,n),memset(e+n,0,4*(lim-n));
mul(b,b,c,n,n),memset(c+n,0,4*(lim-n));
for(int i=0;i<n;++i) c[i]=mod(c[i]+a[i]);
mul(c,e,b,n,n),memset(b+n,0,4*(lim-n));
}
int main()
{
n=in();
for(int i=0;i<n;++i) a[i]=in();
get_sqrt(a,b,n);
for(int i=0;i<n;++i) printf("%d ",b[i]);puts("");
return 0;
}
多项式快速幂
#include<bits/stdc++.h>
#define IL inline
using namespace std;
const int N=4e5+4,p=998244353,G=3,Gi=332748118;
int n,m,k,a[N],b[N],d[N],r[N],inv[N];
IL int in(){
char c;int f=1;
while((c=getchar())<'0'||c>'9')
if(c=='-') f=-1;
int x=c-'0';
while((c=getchar())>='0'&&c<='9')
x=x*10+c-'0';
return x*f;
}
IL int mod(int x){return x>=p?x-p:x;}
IL int ksm(int a,int b){
int c=1;
while(b){
if(b&1) c=1ll*c*a%p;
a=1ll*a*a%p,b>>=1;
}
return c;
}
IL void calc(int lim){
for(int i=0;i<lim;++i) r[i]=(r[i>>1]>>1)|((i&1)*(lim>>1));
}
void pre(int n){
inv[0]=inv[1]=1;
for(int i=2;i<n;++i)
inv[i]=1ll*(p-p/i)*inv[p%i]%p;
}
void NTT(int *a,int lim,int op){
calc(lim);
for(int i=0;i<lim;++i) if(i<r[i]) swap(a[i],a[r[i]]);
for(int i=1;i<lim;i<<=1){
int wn=ksm(op>0?G:Gi,(p-1)/(i<<1));
for(int j=0;j<lim;j+=i<<1){
int w=1;
for(int k=0;k<i;++k,w=1ll*w*wn%p){
int x=a[j+k],y=1ll*w*a[j+i+k]%p;
a[j+k]=mod(x+y),a[j+i+k]=mod(x-y+p);
}
}
}
if(op==-1){
int inv=ksm(lim,p-2);
for(int i=0;i<lim;++i) a[i]=1ll*a[i]*inv%p;
}
}
void get_inv(int *a,int *b,int n){
if(n==1){b[0]=ksm(a[0],p-2),b[1]=0;return;}
get_inv(a,b,n+1>>1);int lim=1,c[N];
while(lim<2*n) lim<<=1;
memcpy(c,a,4*n),memset(c+n,0,4*(lim-n)),
memset(b+n,0,4*(lim-n));
NTT(b,lim,1),NTT(c,lim,1);
for(int i=0;i<lim;++i) b[i]=1ll*mod(2-1ll*b[i]*c[i]%p+p)*b[i]%p;
NTT(b,lim,-1),memset(b+n,0,4*(lim-n));
}
void dao(int *a,int *b,int n){for(int i=0;i<n-1;++i) b[i]=1ll*(i+1)*a[i+1]%p;b[n-1]=0;}
void jifen(int *a,int *b,int n){for(int i=n-1;i;--i) b[i]=1ll*a[i-1]*inv[i]%p;b[0]=0;}
void get_ln(int *a,int *b,int n){
int c[N],d[N],lim=1;
while(lim<2*n) lim<<=1;
get_inv(a,c,n),dao(a,d,n);
memset(c+n,0,4*(lim-n)),memset(d+n,0,4*(lim-n));
NTT(c,lim,1),NTT(d,lim,1);
for(int i=0;i<lim;++i) c[i]=1ll*c[i]*d[i]%p;
NTT(c,lim,-1),jifen(c,b,n);
}
void get_exp(int *a,int *b,int n){
if(n==1){b[0]=1;return;}
get_exp(a,b,n+1>>1);
int c[N],d[N],lim=1;
while(lim<2*n) lim<<=1;
get_ln(b,c,n),get_ln(a,d,n);
for(int i=0;i<n;++i) d[i]=1ll*k*d[i]%p;
d[0]=(1-c[0]+d[0]+p)%p;
for(int i=1;i<n;++i) d[i]=mod(d[i]-c[i]+p);
memset(d+n,0,4*(lim-n));
NTT(d,lim,1),NTT(b,lim,1);
for(int i=0;i<lim;++i) b[i]=1ll*b[i]*d[i]%p;
NTT(b,lim,-1);memset(b+n,0,4*(lim-n));
}
int main()
{
char c;
n=in();
while((c=getchar())<'0'||c>'9');
k=c-'0';
while((c=getchar())>='0'&&c<='9')
k=(10ll*k+c-'0')%p;
for(int i=0;i<n;++i) a[i]=in();
pre(n);
get_exp(a,b,n);
for(int i=0;i<n;++i) printf("%d ",b[i]);putchar('
');
return 0;
}
(MTT)
#include<bits/stdc++.h>
#define IL inline
#define LF long double
#define LL long long
using namespace std;
const LF Pi=acos(-1.0);
const int N=5e5+3,mod=32000;
int n,m,p,r[N];
LL ans[N];
struct com{
LF x,y;
com operator+(const com a) const{
return (com){x+a.x,y+a.y};}
com operator-(const com a) const{
return (com){x-a.x,y-a.y};}
com operator*(const com a) const{
return (com){x*a.x-y*a.y,x*a.y+y*a.x};}
com operator/(const LF a) const{
return (com){x/a,y/a};}
}t1[N],t2[N],q[N];
IL int in(){
char c;int f=1;
while((c=getchar())<'0'||c>'9')
if(c=='-') f=-1;
int x=c-'0';
while((c=getchar())>='0'&&c<='9')
x=x*10+c-'0';
return x*f;
}
IL void calc(int lim){
for(int i=0;i<lim;++i) r[i]=(r[i>>1]>>1)|((i&1)*(lim>>1));
}
IL LL get(LF x){return floor(x+0.5);}
void FFT(com *a,int lim,int op){
calc(lim);
for(int i=0;i<lim;++i) if(i<r[i]) swap(a[i],a[r[i]]);
for(int i=1;i<lim;i<<=1){
com wn=(com){cos(Pi/i),op*sin(Pi/i)};
for(int j=0;j<lim;j+=i<<1){
com w=(com){1,0};
for(int k=0;k<i;++k,w=w*wn){
com x=a[j+k],y=w*a[j+i+k];
a[j+k]=x+y,a[j+i+k]=x-y;
}
}
}
}
int main()
{
int x,lim=1;
n=in()+1,m=in()+1,p=in();
while(lim<n+m) lim<<=1;
for(int i=0;i<n;++i){
x=in();
t1[i]=(com){x/mod,x%mod},
t2[i]=(com){x/mod,-x%mod};
}
for(int i=0;i<m;++i){
x=in();
q[i]=(com){x/mod,x%mod};
}
FFT(t1,lim,1),FFT(t2,lim,1),FFT(q,lim,1);
for(int i=0;i<lim;++i) q[i]=q[i]/lim;
for(int i=0;i<lim;++i) t1[i]=t1[i]*q[i];
for(int i=0;i<lim;++i) t2[i]=t2[i]*q[i];
FFT(t1,lim,-1),FFT(t2,lim,-1);
for(int i=0;i<n+m-1;++i){
LL a1b1,a2b2,a1b2,a2b1;
a1b1=get((t1[i].x+t2[i].x)/2)%p;
a1b2=get((t1[i].y+t2[i].y)/2)%p;
a2b1=get(t1[i].y-a1b2)%p;
a2b2=get(t2[i].x-a1b1)%p;
ans[i]=((a1b1*mod%p+(a1b2+a2b1)%p)*mod%p+a2b2)%p;
}
for(int i=0;i<n+m-1;++i) printf("%lld ",ans[i]);puts("");
return 0;
}
常系数齐次线性递推
#include<bits/stdc++.h>
#define IL inline
using namespace std;
const int N=15e4+3,p=998244353,G=3,Gi=332748118;
int n,m,a[N],b[N],c[N],f[N],v[N],r[N],Inv[N],Id[N],lim=1,ans,Wn[3][N];
IL int in(){
char c;int f=1;
while((c=getchar())<'0'||c>'9')
if(c=='-') f=-1;
int x=c-'0';
while((c=getchar())>='0'&&c<='9')
x=x*10+c-'0';
return x*f;
}
IL int mod(int x){return x>=p?x-p:x;}
IL int ksm(int a,int b){
int c=1;
while(b){
if(b&1) c=1ll*c*a%p;
a=1ll*a*a%p,b>>=1;
}
return c;
}
IL void calc(int lim){
for(int i=0;i<lim;++i)
r[i]=(r[i>>1]>>1)|((i&1)*(lim>>1));
}
void NTT(int *a,int lim,int op){
for(int i=0;i<lim;++i) if(i<r[i]) swap(a[i],a[r[i]]);
for(int i=1;i<lim;i<<=1){
int wn=Wn[op+1][i];
for(int j=0;j<lim;j+=i<<1){
int w=1;
for(int k=0;k<i;++k,w=1ll*w*wn%p){
int x=a[j+k],y=1ll*w*a[j+i+k]%p;
a[j+k]=mod(x+y),a[j+i+k]=mod(x-y+p);
}
}
}
if(op==-1){
int inv=ksm(lim,p-2);
for(int i=0;i<lim;++i) a[i]=1ll*a[i]*inv%p;
}
}
void get_inv(int *a,int *b,int n){
if(n==1){b[0]=ksm(a[0],p-2);b[1]=0;return;}
get_inv(a,b,n+1>>1);
int c[N],lim=1;
while(lim<n+n) lim<<=1;calc(lim);
memcpy(c,a,4*n),memset(c+n,0,4*(lim-n)),
memset(b+n,0,4*(lim-n));
NTT(c,lim,1),NTT(b,lim,1);
for(int i=0;i<lim;++i) b[i]=1ll*mod(2-1ll*c[i]*b[i]%p+p)*b[i]%p;
NTT(b,lim,-1);memset(b+n,0,4*(lim-n));
}
void mul(int *a,int *b,int *c,int n,int m){
int _a[N],_b[N],lim=1;
while(lim<n+m) lim<<=1;calc(lim);
memcpy(_a,a,4*n),memcpy(_b,b,4*m),
memset(_a+n,0,4*(lim-n)),memset(_b+m,0,4*(lim-m));
NTT(_a,lim,1),NTT(_b,lim,1);
for(int i=0;i<lim;++i) _a[i]=1ll*_a[i]*_b[i]%p;
NTT(_a,lim,-1);memcpy(c,_a,4*lim);
}
void Mod(int *a,int n){
int k=n-m,b[N],c[N];
memcpy(c,a,4*n);
reverse(c,c+n);
mul(c,Inv,b,n,m+1);
reverse(b,b+k);
mul(b,Id,c,k,m+1);
for(int i=0;i<n;++i) a[i]=mod(a[i]-c[i]+p);
}
int main()
{
while(lim<7e4)
Wn[2][lim]=ksm(G,(p-1)/(lim<<1)),
Wn[0][lim]=ksm(Gi,(p-1)/(lim<<1)),
lim<<=1;
n=in(),m=in();
for(int i=0;i<m;++i) f[i]=mod(p-in());
reverse(f,f+m),f[m]=1;
memcpy(Id,f,4*(m+1));
reverse(Id,Id+m+1);
get_inv(Id,Inv,m+1);
reverse(Id,Id+m+1);
for(int i=0;i<m;++i) v[i]=mod(in()+p);
a[1]=1,c[0]=1;
lim=1;
while(lim<2*m) lim<<=1;
while(n){
if(n&1) mul(c,a,c,m,m),Mod(c,lim);
n>>=1,mul(a,a,a,m,m),Mod(a,lim);
}
for(int i=0;i<m;++i) ans=mod(ans+1ll*c[i]*v[i]%p);
printf("%d
",ans);
return 0;
}