[数学记录]P4091 [HEOI2016/TJOI2016]求和

command_block · 2019-07-12 15:42:13 · 个人记录

题意:

\sum_{i=0}^n\sum_{j=0}^i \begin{Bmatrix} i\\j \end{Bmatrix}* 2^j * j!

先来化式子:

=\sum_{j=0}^n 2^j * j!\sum_{i=j}^n\begin{Bmatrix} i\\j \end{Bmatrix}

考虑到\begin{Bmatrix} i\\j \end{Bmatrix}在j>i的时候为0,所以第二个\sum的边界可以改为0:

=\sum_{j=0}^n 2^j * j!\sum_{i=0}^n\begin{Bmatrix} i\\j \end{Bmatrix}

回顾 : 我们知道m^n=\sum\limits_{i=0}^n\dbinom{n}{i}\begin{Bmatrix} m\\i \end{Bmatrix}i!

那么二项式反演可以得到:
\begin{Bmatrix} n\\m \end{Bmatrix}m!=\sum\limits_{i=0}^m(-1)^{m-i}\dbinom{m}{i}i^n
这就是第二类斯特林数的"通项公式"。

我们都知道二项式反演是可以卷积优化的,那么其衍生式子也应该有比较好的性质。

那么代入可得:

{\rm Ans}=\sum_{j=0}^n 2^j * j!\sum_{i=0}^n\dfrac{1}{j!}\sum\limits_{k=0}^j(-1)^{j-k}\dbinom{j}{k}k^i

三个\sum非常讨厌(关键是无法卷积),我们发现整个式子和i有关的东西就只有末尾的k^i,那么把\sum\limits_{i}丢到后面去

=\sum_{j=0}^n 2^j * j!*\dfrac{1}{j!}\sum\limits_{k=0}^j(-1)^{j-k}\dbinom{j}{k}\sum_{i=0}^nk^i

使用等比数列求和公式,这样就没了一个\sum,顺手把把j!和\dfrac{1}{j!}乘掉

=\sum_{j=0}^n 2^j \sum\limits_{k=0}^j(-1)^{j-k}\dbinom{j}{k}\dfrac{1-k^{n+1}}{1-k}

拆开组合数

=\sum_{j=0}^n 2^j \sum\limits_{k=0}^j(-1)^{j-k}\dfrac{j!}{(j-k)!k!}\dfrac{1-k^{n+1}}{1-k}

分类移动一下

=\sum_{j=0}^n 2^j*j! \sum\limits_{k=0}^j\dfrac{(-1)^{j-k}}{(j-k)!}\dfrac{1-k^{n+1}}{(1-k)k!}

这里已经是卷积了:

下面我们把题目中的n称作N

设F[j]=\sum\limits_{k=0}^j\dfrac{(-1)^{j-k}}{(j-k)!}\dfrac{1-k^{n+1}}{(1-k)k!}

再设H[n]=\dfrac{(-1)^n}{n!};\ G[n]=\dfrac{1-n^{N+1}}{(1-n)n!}

那么F[j]=\sum\limits_{k=0}^jH[j-k]G[k],卷一卷就好。

注意等比数列通项公式在n=0的时候要特判!!!

#include<algorithm>
#include<cstdio>
#define mod 998244353
#define G 3
#define Maxn 100500
using namespace std;
int n,r[Maxn<<2];
long long invn,invG,fac[Maxn],inv[Maxn];
long long powM(long long a,long long t=mod-2)
{
  long long ans=1,buf=a;
  while(t){
    if(t&1)ans=(ans*buf)%mod;
    buf=(buf*buf)%mod;
    t>>=1;
  }return ans;
}
void NTT(long long *f,bool op,int n)
{
  for (int i=0;i<n;i++)
    if (r[i]<i)swap(f[r[i]],f[i]);
  for (int len=1;len<n;len<<=1){
    int w=powM(op==1 ? G:invG,(mod-1)/len/2);
    for (int p=0;p<n;p+=len+len){
      long long buf=1;
      for (int i=p;i<p+len;i++){
        int sav=f[i+len]*buf%mod;
        f[i+len]=f[i]-sav;
        if (f[i+len]<0)f[i+len]+=mod;
        f[i]=f[i]+sav;
        if (f[i]>=mod)f[i]-=mod;
        buf=buf*w%mod;
        }//F(x)=FL(x^2)+x*FR(x^2)
         //F(W^k)=FL(w^k)+W^k*FR(w^k)
         //F(W^{k+n/2})=FL(w^k)-W^k*FR(w^k)
    }
  }
}
void Init(int lim)
{
  inv[1]=inv[0]=fac[0]=1;
  for (int i=1;i<=lim;i++)fac[i]=fac[i-1]*i%mod;
  for (int i=2;i<=lim;i++)
    inv[i]=inv[mod%i]*(mod-mod/i)%mod;
  for (int i=2;i<=lim;i++)inv[i]=inv[i-1]*inv[i]%mod;
}
long long f[Maxn<<2],g[Maxn<<2];
int main()
{
  scanf("%d",&n);invG=powM(G);
  Init(n);
  long long buf=1,sav=mod-1;
  for (int i=0;i<n+1;i++){
    f[i]=inv[i]*buf%mod;
    buf=buf*sav%mod;
  }
  for (int i=0;i<n+1;i++)
    g[i]=(powM(i,n+1)-1+mod)%mod
         *powM((i-1+mod)%mod)%mod*inv[i]%mod;
  g[1]=n+1;
  int len=1;for (;len<=n+n+2;len<<=1);
  for (int i=0;i<len;i++)
    r[i]=(r[i>>1]>>1)|(i&1?len>>1:0);
  NTT(f,1,len);NTT(g,1,len);
  for (int i=0;i<len;i++)f[i]=f[i]*g[i]%mod;
  NTT(f,0,len);invn=powM(len);
  long long sum=0;
  buf=1;sav=2;
  for (int i=0;i<n+1;i++){
    sum=(sum+f[i]*buf%mod*fac[i])%mod;
    buf=buf*sav%mod;
  }printf("%lld",sum*invn%mod);
  return 0;
}