[HEOI2016/TJOI2016]求和

FFT/NTT 数论

---

题面

求

$$\sum_{i=0}^n\sum_{j=0}^iS(i,j)*2^j*j!$$

• $n\leq10^5$

解析

觉得这道题目与[bzoj5093]图的价值相比，还是小巫见大巫呢。
公式复杂程度和代码细节量少了不止一个级别。。。

首先，要求的时间复杂度是$O(nlogn)$。
则我们需要卷积形式的，第二类斯特林数的，通项公式：（推导过程在链接的那篇博文里）

$$S(i,j)=\sum_{k=0}^j\frac{(-1)^k}{k!}\frac{(j-k)^i}{(j-k)!}$$
然后推推式子：
$$=\sum_{i=0}^n\sum_{j=0}^iS(i,j)*2^j*j!$$
注意到$i<j$时，$S(i,j)=0$，我们可以扩大$j$的范围：
$$=\sum_{j=0}^n2^j*j!\sum_{i=0}^nS(i,j)$$

所以题目实际上要求我们把$\sum_{i=0}^nS(i,j)$化成卷积形式。

$$\sum_{i=0}^nS(i,j)=\sum_{i=0}^n\sum_{k=0}^j\frac{(-1)^k}{k!}\frac{(j-k)^i}{(j-k)!}$$
$$=\sum_{k=0}^j\frac{(-1)^k}{k!(j-k)!}\sum_{i=0}^n(j-k)^i$$
又根据等比数列求和公式 $$\sum_{i=0}^n(j-k)^i=\frac{(j-k)^{n+1}-1}{(j-k)-1}$$
最终式子化为
$$=\sum_{k=0}^n\frac{(-1)^k}{k!}\frac{(j-k)^{n+1}-1}{[(j-k)-1](j-k)!}$$
大功告成。接下来$NTT$轻松解决。

ps:如何快速求阶乘的逆元

显然一般方法是一边求阶乘一边求逆元，复杂度$O(nlogn)$。
然而更好的方法是求完阶乘后，求出最后一个阶乘的逆元，再不断$inv[i]=inv[i+1]*(i+1)$即可。
时间复杂度$O(n)$

#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#define ll long long
#define re register
#define il inline
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=4e5+1,mod=998244353;
int n,m,lim=1,l,r[N],a[N],b[N],jc[N],inv[N],ans;
il int ksm(re int S,re int n)
{
  re int T=S;S=1;
  while(n)
    {
      if(n&1) S=1ll*S*T%mod;
      T=1ll*T*T%mod;
      n>>=1;
    }
  return S;
}
il void NTT(re int *A,re int tp)
{
  fp(i,1,lim-1) if(i<r[i]) swap(A[i],A[r[i]]);
  for(re int mid=1;mid<lim;mid<<=1)
    {
      re int gu=mid<<1,W=ksm(3,(mod-1)/gu);
      if(tp==-1) W=ksm(W,mod-2);
      for(re int j=0;j<lim;j+=gu)
    {
      re int w=1;
      for(re int k=0;k<mid;k++,w=1ll*w*W%mod)
        {
          re ll x=A[j+k],y=1ll*w*A[j+mid+k]%mod;
          A[j+k]=(x+y)%mod;A[j+mid+k]=(x-y+mod)%mod;
        }
    }
    }
}
il int gi()
{
  re int x=0,t=1;
  re char ch=getchar();
  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
int main()
{
  n=m=gi();
  jc[0]=inv[0]=1;fp(i,1,n) jc[i]=1ll*jc[i-1]*i%mod;
  inv[n]=ksm(jc[n],mod-2);
  fq(i,n-1,1) inv[i]=1ll*inv[i+1]*(i+1)%mod;
  b[0]=1;b[1]=n+1;
  fp(i,0,n)
    {
      a[i]=(i&1)?mod-inv[i]:inv[i];
      if(i>1) b[i]=1ll*(ksm(i,n+1)-1+mod)%mod*ksm(i-1,mod-2)%mod*inv[i]%mod;
    }
  while(lim<=n+m) lim<<=1,++l;
  fp(i,1,lim-1) r[i]=(r[i>>1]>>1)|((i&1)<<l-1);
  NTT(a,1);NTT(b,1);
  fp(i,0,lim-1) a[i]=1ll*a[i]*b[i]%mod;
  NTT(a,-1);
  re ll Inv=ksm(lim,mod-2);
  for(re int i=0,j=1;i<=n;++i,j=((ll)j<<1)%mod)
    (ans+=1ll*a[i]*Inv%mod*jc[i]%mod*j%mod)%=mod;
  printf("%d\n",ans);
  return 0;
}