「TJOI / HEOI2016」求和

题目大意：

求$\displaystyle \sum_{i=0}^n\sum_{j=0}^i \begin{Bmatrix}i\\ j\end{Bmatrix}2^j\cdot j!$

由于第二类斯特林数的生成函数$S_m(x)=\cfrac{1} {m!}(e^x-1)^m$

所以求的东西就是$\displaystyle F(x)=\sum_{i=0} (2e^x-2)^i=\frac{1} {3-2e^x}$前$n$项系数

可以暴力求逆

线性解法：思路

要求$\displaystyle \frac{1} {3-2e^x}$的前$n$项$[x^i]$乘$i!$的和

设$\displaystyle G(x)=e^x,F(x)=\frac{1} {3-2x}$

那么我们需要求得$\mathscr F(x+1)=F(x+1) \mod x^{n+1}$

$\displaystyle F(x+1)=\frac{1} {1-2x}=\sum_{i=0} (2x)^i$

$\displaystyle F’(x+1)=\sum_{i=0} 2(i+1) (2x)^i$

$F(x+1)=\cfrac{1-2x} {2}F’(x+1)$

$\displaystyle \mathscr F(x+1)=\cfrac{1-2x} {2}\mathscr F’(x+1)+(n+1)(2x)^n$

$\displaystyle \mathscr F(x)=\cfrac{3-2x} {2}\mathscr F’(x)+(n+1)(2x-2)^n$

那么得到

$\displaystyle [x^k]\mathscr F(x)=\frac{3} {2}(k+1)[x^{k+1}]\mathscr F(x)-k[x^k]\mathscr F(x)+(n+1)2^{n}\binom{n} {k}(-1)^{n-k}$

$\displaystyle \frac{3} {2}(k+1)[x^{k+1}]\mathscr F(x)=(k+1)[x^k]\mathscr F(x)-(n+1)2^{n}\binom{n} {k}(-1)^{n-k}$

$\displaystyle \frac{3} {2} [x^{k+1}]\mathscr F(x)=[x^k]\mathscr F(x)-2^{n}\binom{n+1} {k+1}(-1)^{n-k}$

最后$\displaystyle \sum_{i=0}^n [x^i]F(G(x))=\sum_{i=0}^n [x^i]\mathscr F(G(x))=\sum \mathscr F_i \sum_{j=0}^n j! [x^j]G^k(x)$

$\displaystyle [x^0]\mathscr F(x)=[x^0]\sum_{i=0}^n(2x-2)^i=\sum_{i=0}^n (-2)^i=\frac{1-(-2)^{n+1} } {3}$

$\sum_{j=0}^n j! [x^j]G^k(x)$就是一个等比数列求和，可以用线性筛$i^k$轻 松线性求得

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)

const int N=1e5+10,P=998244353;

int n;
int I[N],J[N],Inv[N],Pow[N],q[N],F[N];
ll qpow(ll x,ll k=P-2){
	ll res=1;
	for(;k;k>>=1,x=x*x%P) if(k&1) res=res*x%P;
	return res;
}

void Sieve_Pow(int n){
	static int notpri[N],pri[N],pc;
	rep(i,2,n) {
		if(!notpri[i]) pri[++pc]=i,Pow[i]=qpow(i,n);
		for(int j=1;j<=pc && 1ll*i*pri[j]<=n;++j) {
			notpri[i*pri[j]]=1,Pow[i*pri[j]]=1ll*Pow[i]*Pow[pri[j]]%P;
			if(i%pri[j]==0) break;
		}
	}
}
int C(int n,int m){ return 1ll*J[n]*I[m]%P*I[n-m]%P; }

int main(){
	scanf("%d",&n),Inv[0]=Inv[1]=1;
	rep(i,2,n+1) Inv[i]=1ll*(P-P/i)*Inv[P%i]%P;
	rep(i,*I=*J=1,n+1) I[i]=1ll*I[i-1]*Inv[i]%P,J[i]=1ll*J[i-1]*i%P;
	Sieve_Pow(n+1);
	ll p=qpow(2,n);
	q[0]=1,q[1]=n+1;
	rep(i,2,n) q[i]=1ll*(Pow[i]-1)*Inv[i-1]%P;
	F[0]=(((n&1)?P-p*2%P:p*2%P)+1)*(P+1)/3%P;
	rep(i,0,n-1) {
		int t=p%P*C(n+1,i+1)%P;
		if((n-i+1)&1) t=P-t;
		F[i+1]=(F[i]+t)*2ll%P*(P+1)/3%P;
	}
	int ans=0;
	rep(i,0,n) ans=(ans+1ll*F[i]*q[i])%P;
	printf("%d\n",ans);
}