[数学记录]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$的时候要特判!!!
```cpp
#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;
}
```