bzoj 4555 [Tjoi2016&Heoi2016] 求和 —— 第二类斯特林数+NTT

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=4555

关于第二类斯特林数：https://www.cnblogs.com/Wuweizheng/p/8638858.html

关于这道题：https://blog.csdn.net/werkeytom_ftd/article/details/51909966

把 ∑i 移到后面那一步很不错，在后面就是个等比数列求和，就消去一个 O(n) 了；

注意等比数列求和公式当 q=1 时不适用。

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long ll;

int const xn=(<<),mod=;

int n,a[xn],b[xn],lim,rev[xn],jc[xn],jcn[xn];

int upt(int x){while(x>=mod)x-=mod; while(x<)x+=mod; return x;}

ll pw(ll a,int b)

{

  ll ret=; a=upt(a%mod);

  for(;b;b>>=,a=(a*a)%mod)if(b&)ret=(ret*a)%mod;

  return ret;

}

void init()

{

  jc[]=;

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

  jcn[n]=pw(jc[n],mod-);

  for(int i=n-;i>=;i--)jcn[i]=(ll)jcn[i+]*(i+)%mod;

}

void ntt(int *a,int tp)

{

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

    if(i<rev[i])swap(a[i],a[rev[i]]);

  for(int mid=;mid<lim;mid<<=)

    {

      int len=(mid<<),wn=pw(,tp==?(mod-)/len:(mod-)-(mod-)/len);

      for(int j=;j<lim;j+=len)

    for(int k=,w=;k<mid;k++,w=(ll)w*wn%mod)

      {

        int x=a[j+k],y=(ll)w*a[j+mid+k]%mod;

        a[j+k]=upt(x+y); a[j+mid+k]=upt(x-y);

      }

    }

  if(tp==)return; int inv=pw(lim,mod-);

  for(int i=;i<lim;i++)a[i]=(ll)a[i]*inv%mod;

}

int main()

{

  scanf("%d",&n);

  lim=; int l=;

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

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

  init();

  for(int i=,t=;i<=n;i++,t=-t)a[i]=upt(t*jcn[i]);

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

    {

      if(i==)b[i]=(ll)(n+)*jcn[i]%mod;//!!

      else b[i]=upt((ll)(-pw(i,n+))*pw(-i,mod-)%mod*jcn[i]%mod);

    }

  ntt(a,); ntt(b,);

  for(int i=;i<lim;i++)a[i]=(ll)a[i]*b[i]%mod;

  ntt(a,-);

  int ans=;

  for(int i=,bin=,fac=;i<=n;i++,bin=upt(bin<<),fac=(ll)fac*i%mod)

    ans=upt(ans+ (ll)bin*fac%mod*a[i]%mod);

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

  return ;

}

巴特西

bzoj 4555 [Tjoi2016&Heoi2016] 求和 —— 第二类斯特林数+NTT

最新文章

热门文章