题目链接

题解

f(n)=∑i=0n∑j=0iS(i,j)×2j×j!=∑i=0n∑j=0nS(i,j)×2j×j!=∑i=0n∑j=0n2j∑k=0j(−1)k(jk)(j−k)i=∑i=0n∑j=0n2j×j!∑k=0j(−1)kk!×(j−k)i(j−k)!=∑j=0n2j×j!∑k=0j(−1)kk!×∑ni=0(j−k)i(j−k)!(1)(2)(1)(3)(2)(1)f(n)=∑i=0n∑j=0iS(i,j)×2j×j!(2)=∑i=0n∑j=0nS(i,j)×2j×j!(1)=∑i=0n∑j=0n2j∑k=0j(−1)k(jk)(j−k)i(3)=∑i=0n∑j=0n2j×j!∑k=0j(−1)kk!×(j−k)i(j−k)!(2)=∑j=0n2j×j!∑k=0j(−1)kk!×∑i=0n(j−k)i(j−k)!

其中(1)(1)步骤使用了第二类斯特林数的展开式S(i,j)=1j!∑jk=0(−1)k(jk)(j−k)iS(i,j)=1j!∑k=0j(−1)k(jk)(j−k)i，(2)(2)步骤是一个卷积形式，模数比较特殊可以用NTT优化，∑ni=0(j−k)i∑i=0n(j−k)i很明显是一个等比数列求和。

代码

#include 
    
     #include 
     
      int read(){  int x=0,f=1;  char ch=getchar();  while((ch<'0')||(ch>'9'))    {      if(ch=='-')        {          f=-f;        }      ch=getchar();    }  while((ch>='0')&&(ch<='9'))    {      x=x*10+ch-'0';      ch=getchar();    }  return x*f;}const int maxn=200000;const int maxm=340000;const int mod=998244353;const int G=3;int quickpow(int a,int b,int m){  int res=1;  while(b)    {      if(b&1)        {          res=1ll*res*a%m;        }      a=1ll*a*a%m;      b>>=1;    }  return res;}int add(int x,int y,int m){  int res=x+y;  if(res>=m)    {      res-=m;    }  return res;}int minus(int x,int y,int m){  int res=x-y;  if(res<0)    {      res+=m;    }  return res;}int rev[maxm+10],a[maxm+10],b[maxm+10],ans[maxm+10];int getrev(int n){  int m=1,len=0;  while(m<=n)    {      m<<=1;      ++len;    }  for(int i=1; i
      
       >1]>>1)+((i&1)<<(len-1));    }  return m;}int fft(int *s,int len){  for(int i=0; i
       
        >1); ++k)            {              int x=s[j+k],y=1ll*g*s[j+k+(i>>1)]%mod;              s[j+k]=add(x,y,mod);              s[j+k+(i>>1)]=minus(x,y,mod);              g=1ll*g*gn%mod;            }        }    }  return 0;}int main(){  int n=read();  a[0]=1;  int v=1;  for(int i=1; i<=n; ++i)    {      v=1ll*minus(0,v,mod)*quickpow(i,mod-2,mod)%mod;      a[i]=v;    }  b[0]=1;  v=1;  for(int i=1; i<=n; ++i)    {      v=1ll*v*quickpow(i,mod-2,mod)%mod;      b[i]=1ll*minus(1,quickpow(i,n+1,mod),mod)*quickpow(minus(1,i,mod),mod-2,mod)%mod*v%mod;    }  b[1]=n+1;  int m=getrev(n<<1);  fft(a,m);  fft(b,m);  for(int i=0; i