【BZOJ 4555】[Tjoi2016&Heoi2016]求和 多项式求逆/NTT+第二类斯特林数

时间：2023-03-09 03:43:35
【BZOJ 4555】[Tjoi2016&Heoi2016]求和 多项式求逆/NTT+第二类斯特林数

出处0.0
用到第二类斯特林数的性质,做法好像很多,我打的是直接ntt,由第二类斯特林数的容斥公式可以推出,我们可以对于每一个i,来一次ntt求出他与所有j组成的第二类斯特林数的值,这个时候我们是O(n^2logn)的,还不如暴力,但是我们发现,对于刚刚提到的容斥的式子,将其化为卷积形式后,其一边的每一项对于每一个i都相同,另一边的每一项是对于所有的i形成一个n项的等比数列,这样我们可以把成等比数列的一边求和,用固定的一边去卷他们的和,这时候的答案的每一项就是所有的i的这一项的和,然后我们再O(n)乘上阶乘和2的次幂就可以了.
(一开始代码打错了,还以为那个公式在S(i,j)不存在的时候是错的……后来手玩了一下才发现他是对的……)
补充:
又用多项式求逆打了一遍,比上面那个做法慢了一倍……
这道题求逆的具体做法参见http://blog.****.net/lych_cys/article/details/51512278
感觉好神奇啊,把多项式当成数来推式子……
这个东西感觉有点像CDQ+ntt……

#include <cstdio>

#include <cstring>

#include <algorithm>

const int N=;

const int P=;

typedef long long LL;

inline int Pow(int x,int y){

  int ret=;

  while(y){

    if(y&)ret=(LL)ret*x%P;

    x=(LL)x*x%P,y>>=;

  }return ret;

}

int A[N],B[N],rev[N],len;

int ai[N],bi[N],ci[N];

int jie[N],ni[N],inv[N],n;

inline void ntt(int *C,int opt){

  register int i,j,k,w;int wn,temp;

  for(i=;i<len;++i)if(i<rev[i])std::swap(C[i],C[rev[i]]);

  for(k=;k<=len;k<<=){

    wn=Pow(,(P-)/k);

    if(opt==-)wn=Pow(wn,P-);

    for(i=;i<len;i+=k){

      w=;

      for(j=;j<(k>>);++j,w=(LL)w*wn%P){

        temp=(LL)w*C[i+j+(k>>)]%P;

        C[i+j+(k>>)]=(C[i+j]-temp+P)%P;

        C[i+j]=(C[i+j]+temp)%P;

      }

    }

  }

}

inline void mul(int *a,int *b,int *c,int n){

  len=;while(len<n)len<<=;int i;

  for(i=;i<len;++i)rev[i]=(rev[i>>]>>)|((i&)?(len>>):);

  for(i=;i<len;++i)A[i]=a[i],B[i]=b[i];

  ntt(A,),ntt(B,);

  for(i=;i<len;++i)A[i]=(LL)A[i]*B[i]%P;

  ntt(A,-);

  int Inv=Pow(len,P-);

  for(i=;i<len;++i)c[i]=(LL)A[i]*Inv%P;

}

int main(){

  scanf("%d",&n);int i,ans=,temp=;

  jie[]=ni[]=,inv[]=;

  for(i=;i<=n;++i)inv[i]=((-(LL)(P/i)*inv[P%i])%P+P)%P;

  for(i=;i<=n;++i)jie[i]=(LL)jie[i-]*i%P,ni[i]=(LL)ni[i-]*inv[i]%P;

  bi[]=,bi[]=n,ai[]=,ai[]=P-;

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

    bi[i]=(LL)i*(Pow(i,n)-+P)%P*ni[i]%P*inv[i-]%P,ai[i]=(i&)?(P-ni[i]):ni[i];

  mul(ai,bi,ci,n+n+);

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

    temp=(((LL)temp)<<1LL)%P,ans=(ans+(LL)ci[i]*temp%P*jie[i])%P;

  printf("%d\n",ans);

  return ;

}

直接ntt

#include <cstdio>

#include <cstring>

#include <algorithm>

typedef long long LL;

const int N=;

const int P=;

inline int Pow(int x,int y){

  int ret=;

  while(y){

    if(y&)ret=(LL)ret*x%P;

    x=(LL)x*x%P,y>>=;

  }return ret;

}

int len,n,A[N<<],rev[N<<];

int g[N<<],f[N<<],jie[N],ni[N];

inline void ntt(int *C,int opt){

  register int i,j,k,w;int wn,temp;

  for(i=;i<len;++i)if(rev[i]>i)std::swap(C[i],C[rev[i]]);

  for(k=;k<=len;k<<=){

    wn=Pow(,(P-)/k);

    if(opt==-)wn=Pow(wn,P-);

    for(i=;i<len;i+=k){

      w=;

      for(j=;j<(k>>);++j,w=(LL)w*wn%P){

        temp=(LL)w*C[i+j+(k>>)]%P;

        C[i+j+(k>>)]=(C[i+j]-temp+P)%P;

        C[i+j]=(C[i+j]+temp)%P;

      }

    }

  }

}

inline void Inv(int *a,int *b,int cd){

  if(cd==){b[]=Pow(a[],P-);return;}

  Inv(a,b,cd>>);

  int i,inv;len=cd<<;

  for(i=;i<len;++i)rev[i]=(rev[i>>]>>)|((i&)?(len>>):);

  memcpy(A,a,cd<<),memset(A+cd,,cd<<);

  ntt(A,),ntt(b,);

  for(i=;i<len;++i)b[i]=(-(LL)A[i]*b[i]%P+P)*b[i]%P;

  ntt(b,-),inv=Pow(len,P-);

  for(i=;i<cd;++i)b[i]=(LL)b[i]*inv%P;

  memset(b+cd,,cd<<);

}

int main(){

  scanf("%d",&n);int i,cd,ans=;

  jie[]=ni[]=;

  for(i=;i<=n;++i)jie[i]=(LL)jie[i-]*i%P;

  ni[n]=Pow(jie[n],P-);

  for(i=n-;i>;--i)ni[i]=(LL)ni[i+]*(i+)%P;

  g[]=;

  for(i=;i<=n;++i)g[i]=(-*ni[i]+P+P)%P;

  cd=;

  while(cd<=n)cd<<=;

  Inv(g,f,cd);

  for(i=;i<=n;++i)ans=(ans+(LL)f[i]*jie[i])%P;

  printf("%d\n",ans);

  return ;

}

多项式求逆

相关文章