xinbanzi
中国剩余定理
//中国剩余定理模板
¡™™£Any module NTT
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=1e5+5;
const int P[3]={998244353,1004535809,469762049};
const LL M=1ll*P[0]*P[1];
const int G[3][2]={{3,(P[0]+1)/3},{3,(P[1]+1)/3},{3,(P[2]+1)/3}};
int n,m,_P,a[N],b[N],A[N<<2],B[N<<2],t=1,p,r[N<<2],f[3][N<<1],ans[N<<1];
int K(int x,int y,int u){
int z=1;
for (;y;y>>=1,x=1ll*x*x%u)
if (y&1) z=1ll*z*x%u;
return z;
}
LL by(LL x,LL y){
LL z=0;
for (;y;y>>=1,(x+=x)%=M)
if (y&1ll) (z+=x)%=M;
return z;
}
void Ntt(int u,int *g,int o){
for (int i=0;i<t;i++)
if (i<r[i]) swap(g[i],g[r[i]]);
for (int i=1,wn;i<t;i<<=1){
wn=K(G[u][o],(P[u]-1)/(i<<1),P[u]);
for (int j=0,x,y;j<t;j+=(i<<1))
for (int k=0,w=1;k<i;k++,w=1ll*w*wn%P[u])
x=g[j+k],y=1ll*w*g[i+j+k]%P[u],
g[j+k]=(x+y)%P[u],g[i+j+k]=(x-y+P[u])%P[u];
}
if (o)
for (int i=0,v=K(t,P[u]-2,P[u]);i<t;i++)
g[i]=1ll*g[i]*v%P[u];
}
void work(int u){
for (int i=0;i<t;i++) A[i]=B[i]=0;
for (int i=0;i<=n;i++) A[i]=a[i];
for (int i=0;i<=m;i++) B[i]=b[i];
Ntt(u,A,0);Ntt(u,B,0);
for (int i=0;i<t;i++) A[i]=1ll*A[i]*B[i]%P[u];
Ntt(u,A,1);
for (int i=0;i<=n+m;i++) f[u][i]=A[i];
}
void crt(){
for (int i=0;i<=n;i++){
LL v=by(1ll*f[0][i]*P[1]%M,K(P[1],P[0]-2,P[0]));
(v+=by(1ll*f[1][i]*P[0]%M,K(P[0],P[1]-2,P[1])))%=M;
int u=(1ll*(-v+f[2][i])%P[2]*K(M%P[2],P[2]-2,P[2])%P[2]+P[2])%P[2];
ans[i]=(M%_P*u%_P+v%_P)%_P;
}
}
int main(){
scanf("%d%d%d",&n,&m,&_P);
for (int i=0;i<=n;i++) scanf("%d",&a[i]);
for (int i=0;i<=m;i++) scanf("%d",&b[i]);
for (;t<n+m+2;t<<=1,p++);
for (int i=0;i<t;i++)
r[i]=(r[i>>1]>>1)|((i&1)<<(p-1));
work(0);work(1);work(2);n+=m;crt();
for (int i=0;i<=n;i++) printf("%d ",ans[i]);
return 0;
}duo xiang shi cao zuo
#include <bits/stdc++.h>
#define I inline
using namespace std;
const int P=998244353,N=5e5+5;
int n,m,a[N],b[N],r[N],t,p,G[2]={3,332748118};
int A[N],B[N],C[N],D[N],E[N],F[N],jc[N],ny[N];
I int X(int x){if (x>=P) x-=P;return x;}
I int inv(int x){return 1ll*jc[x-1]*ny[x]%P;}
I int K(int x,int y){
int A=1;
for (;y;y>>=1,x=1ll*x*x%P)
if (y&1) A=1ll*A*x%P;
return A;
}
I void Ntt(int *g,bool o){
for (int i=0;i<t;i++)
if (i<r[i]) swap(g[i],g[r[i]]);
for (int wn,i=1;i<t;i<<=1){
wn=K(G[o],(P-1)/(i<<1));
for (int x,y,j=0;j<t;j+=(i<<1))
for (int w=1,k=0;k<i;k++,w=1ll*w*wn%P)
x=g[j+k],y=1ll*w*g[i+j+k]%P,
g[j+k]=X(x+y),g[i+j+k]=X(x-y+P);
}
if (o)
for (int i=0,v=K(t,P-2);i<t;i++)
g[i]=1ll*v*g[i]%P;
}
I void dao(int *a,int *b,int l){
for (int i=1;i<l;i++)
b[i-1]=1ll*i*a[i]%P;
b[l]=b[l-1]=0;
}
I void jifen(int *a,int *b,int l){
for (int i=1;i<l;i++)
b[i]=1ll*a[i-1]*inv(i)%P;
b[0]=0;
}
I void pre(int l){
for (t=1,p=0;t<l+l;t<<=1,p++);
for (int i=0;i<t;i++)
r[i]=(r[i>>1]>>1)|((i&1)<<(p-1));
}
void getinv(int *a,int *b,int l){
if (l==1){
b[0]=K(a[0],P-2);return;
}
getinv(a,b,(l+1)>>1);
for (int i=0;i<l;i++)
A[i]=a[i],B[i]=b[i];
pre(l);Ntt(A,0);Ntt(B,0);
for (int i=0;i<t;i++)
A[i]=1ll*A[i]*B[i]%P*B[i]%P;
Ntt(A,1);for (int i=0;i<l;i++)
b[i]=X(X(b[i]+b[i])-A[i]+P);
for (int i=0;i<t;i++) A[i]=B[i]=0;
}
I void getln(int *a,int *b,int l){
dao(a,C,l);getinv(a,D,l);
pre(l);Ntt(C,0);Ntt(D,0);
for (int i=0;i<t;i++)
C[i]=1ll*C[i]*D[i]%P;
Ntt(C,1);jifen(C,b,l);
for (int i=0;i<t;i++) C[i]=D[i]=0;
}
void getexp(int *a,int *b,int l){
if (l==1){b[0]=1;return;}
getexp(a,b,(l+1)>>1);
for (int i=0;i<l;i++) E[i]=b[i];
getln(b,F,l);
for (int i=0;i<l;i++)
F[i]=X(a[i]-F[i]+P);
F[0]=X(F[0]+1);pre(l);
Ntt(F,0);Ntt(E,0);
for (int i=0;i<t;i++)
E[i]=1ll*E[i]*F[i]%P;
Ntt(E,1);
for (int i=0;i<l;i++) b[i]=E[i];
for (int i=0;i<t;i++) E[i]=F[i]=0;
}
int main(){
scanf("%d%d",&n,&m);
for (int x,y,i=1;i<=m;i++){
scanf("%d%d",&x,&y);
if (x<=n) a[x]++;
if (y && 1ll*x*(y+1)<=1ll*n)
a[x*(y+1)]--;
}
jc[0]=1;
for (int i=1;i<=n;i++)
jc[i]=1ll*i*jc[i-1]%P;
ny[n]=K(jc[n],P-2);
for (int i=n;i;i--)
ny[i-1]=1ll*i*ny[i]%P;
for (int i=1;i<=n;i++){
if (!a[i]) continue;
if (a[i]<0) a[i]+=P;
for (int j=1;j*i<=n;j++)
b[i*j]=X(b[i*j]+1ll*a[i]*inv(j)%P);
a[i]=0;
}
getexp(b,a,n+1);
for (int i=1;i<=n;i++)
printf("%d\n",a[i]);
return 0;
}