首页 > 代码库 > BZOJ 3625 多项式求逆+多项式开根

BZOJ 3625 多项式求逆+多项式开根

思路:

RT

//By SiriusRen#include <bits/stdc++.h>using namespace std;const int N=1<<18,mod=998244353;int A[N],C[N],invC[N],c[N],d[N],R[N],tmp[N],xx,len,sqrA[N],F[N];typedef long long ll;int power(ll x,int y){    ll res=1;    while(y){        if(y&1)res=res*x%mod;        x=x*x%mod,y>>=1;    }return res;}void NTT(int *a,int n,int f){    int m=1,L=0;    for(;m<n;m<<=1)L++;    for(int i=0;i<n;i++)R[i]=(R[i>>1]>>1)|((i&1)<<(L-1));    for(int i=0;i<n;i++)if(i<R[i])swap(a[i],a[R[i]]);    for(int l=1;l<n;l<<=1){        int wn=power(5,((mod-1)/(l<<1)*f+mod-1)%(mod-1));        for(int j=0;j<n;j+=(l<<1)){            int w=1;            for(int k=0;k<l;k++,w=1ll*w*wn%mod){                int x=a[j+k],y=1ll*a[j+k+l]*w%mod;                a[j+k]=(x+y)%mod,a[j+k+l]=(x-y+mod)%mod;             }        }    }    if(f==-1){        int ni=power(n,mod-2);        for(int i=0;i<n;i++)a[i]=1ll*a[i]*ni%mod;    }}void get_inv(int *a,int *b,int n){    if(n==1){b[0]=power(a[0],mod-2);return;}    get_inv(a,b,n>>1);    memcpy(tmp,a,sizeof(int)*n),memset(tmp+n,0,sizeof(int)*n);    NTT(tmp,n<<1,1),NTT(b,n<<1,1);    for(int i=0;i<n<<1;i++)b[i]=(1ll*b[i]*(2-1ll*b[i]*tmp[i]%mod)%mod+mod)%mod;    NTT(b,n<<1,-1),memset(b+n,0,sizeof(int)*n);}void get_root(int *a,int *b,int n){    if(n==1){b[0]=1;return;}    get_root(a,b,n>>1),memset(d,0,sizeof(int)*2*n);    get_inv(b,d,n);    memcpy(c,a,sizeof(int)*n),memset(c+n,0,sizeof(int)*n);    NTT(c,n<<1,1),NTT(b,n<<1,1),NTT(d,n<<1,1);    for(int i=0;i<n<<1;i++)b[i]=(1ll*c[i]*d[i]%mod+b[i])%mod*499122177%mod;    NTT(b,n<<1,-1),memset(b+n,0,sizeof(int)*n);}signed main(){    int n,m;    scanf("%d%d",&n,&m);    for(len=1;len<=m;len<<=1);A[0]=1;    for(int i=1;i<=n;i++)scanf("%d",&xx),C[xx]=1,A[xx]=mod-4;    get_root(A,sqrA,len),sqrA[0]++,get_inv(sqrA,F,len);    for(int i=1;i<=m;i++)printf("%d\n",(F[i]<<1)%mod);}

 

BZOJ 3625 多项式求逆+多项式开根