NTT+多项式求逆

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<cmath>

 #define ll long long

 #define N 300005

 using namespace std;

 const int ni = ;

 const int p = ;

 ll pw(ll x,int y)

 {

     ll lst=;

     while(y)

     {

         if(y&)lst=(lst*x)%p;

         y>>=;

         x=(x*x)%p;

     }

     return lst;

 }

 int n,m;

 int c[N],a[N],b[N],R[N];

 int invb[N];

 int ji[N],jie[N],nini[N];

 int tmp[N];

 void fft(int *a,int n,int f)

 {

     for(int i=;i<n;i++)if(R[i]>i)swap(a[i],a[R[i]]);

     for(int i=;i<n;i<<=)

     {

         int wn=pw(ni,((p-)/(i<<)*f+p-)%(p-));

         for(int j=;j<n;j+=(i<<))

         {

             int w=;

             for(int k=;k<i;k++,w=((ll)w*wn)%p)

             {

                 int x=a[j+k];int y=((ll)a[j+i+k]*w)%p;

                 a[j+k]=(x+y)%p;a[j+k+i]=(x-y+p)%p;

             }

         }

     }

     if(f==-)

     {

         ll nii=pw(n,p-);

         for(int i=;i<n;i++)a[i]=(ll)a[i]*nii%p;

     }

     return ;

 }

 void get_inv(int *a,int *b,int n)

 {

     if(n==)

     {

         b[]=pw(a[],p-);

         return ;

     }

     get_inv(a,b,n>>);

     for(int i=;i<n;i++)tmp[i]=a[i];

     int l=;int nn=;

     while(nn<n<<)nn<<=,l++;

     for(int i=;i<nn;i++)R[i]=(R[i>>]>>)|((i&)<<(l-));

     fft(tmp,nn,);fft(b,nn,);

     for(int i=;i<nn;i++)

     b[i]=((ll)b[i]*(-(ll)tmp[i]*b[i]%p+p))%p;

     fft(b,nn,-);

     memset(b+n,,sizeof(int)*n);

 }

 int main()

 {

     scanf("%d",&n);

     int l=;

     for(m=n,n=;n<=m;n<<=)l++;

     nini[]=jie[]=ji[]=;

     for(int i=;i<n;i++)jie[i]=((ll)jie[i-]*i)%p;

     for(int i=;i<n;i++)

         b[i]=pw(,((ll)i*(i-)>>)%(p-))*pw(jie[i],p-)%p;

     for(int i=;i<n;i++)

         c[i]=pw(,((ll)i*(i-)>>)%(p-))*pw(jie[i-],p-)%p;

     get_inv(b,invb,n);

     l++;int tp=n<<;

     for(int i=;i<tp;i++)R[i]=(R[i>>]>>)|((i&)<<(l-));

     fft(invb,tp,);

     fft(c,tp,);

     for(int i=;i<tp;i++)a[i]=(ll)invb[i]*c[i]%p;

     fft(a,tp,-);

     printf("%d\n",(ll)a[m]*jie[m-]%p);

     return ;

 }