bzoj 4555 求和

Posted on | Views:

第二类斯特林数 + $NTT$ .

  • 第二类斯特林数 $S(n,m)$ 表示将 $n$ 个球放入 $m$ 个相同盒子的方案数.
  • 递推式是 $S(n,m)=S(n-1,m-1)+m\cdot S(n-1,m)$ .即讨论第一个球是否单独占一个盒子.
  • 也可利用容斥原理计算,

$$
S(n,m)=\frac 1 {m!} \sum_{k=0}^m (-1)^k{m\choose k}(m-k)^n
$$

  • 意义是枚举空盒个数为 $k$ ,剩下的球任意放置.因为盒子相同,所以最后要除以 $m!$ .
  • 回到这道题, $j<i$ 时, $S(i,j)=0$ ,所以 $j$ 的枚举范围可以换成 $n$ .将上面的容斥计算式代到要求的式子里面,

  • 仔细观察,发现第二个 $\sum$ 后面那一坨是一个卷积的形式,令 $a_i=\frac {(-1)^i} {i!},b_i=\frac {\sum_{j=0}^n i^j} {i!}$ , $c=a*b$ ,则 $ans=\sum_{j=0}^n 2^j\cdot j!\cdot c_j$ .
  • 预处理 $a,b,2^j,j!$ ( $b_i$ 的分子是等比数列求和 ) ,用 $NTT$ 计算 $c$ .

空间要开够.

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int P=998244353,G=3;
const int MAXN=1e5+10;
inline int add(int a,int b)
{
	return (a + b) % P;
}
inline int mul(int a,int b)
{
	return 1LL * a * b % P;
}
int fpow(int a,int b)
{
	int res=1;
	while(b)
	{
		if(b&1)
			res=mul(res,a);
		a=mul(a,a);
		b>>=1;
	}
	return res;
}
int inv(int x)
{
	return fpow(x,P-2);
}
int rev[MAXN<<2];
void NTT_init(int n,int lim)
{
	for(int i=0;i<n;++i)
	{
		for(int j=0;j<lim;++j)
			if((i>>j)&1)
				rev[i]|=1<<(lim-j-1);
	}
}
void DFT(int *a,int n,bool invflag)
{
	for(int i=0;i<n;++i)
	{
		if(i<rev[i])
			swap(a[i],a[rev[i]]);
	}
	for(int l=2;l<=n;l<<=1)
	{
		int gi=fpow(G,(P-1)/l);
		if(invflag)
			gi=inv(gi);
		int m=l>>1;
		for(int *p=a;p!=a+n;p+=l)
		{
			int g=1;
			for(int i=0;i<m;++i)
			{
				int t=mul(g,p[i+m]);
				p[i+m]=add(p[i],P-t);
				p[i]=add(p[i],t);
				g=mul(g,gi);
			}
		}
	}
	if(invflag)
	{
		int Invn=inv(n);
		for(int i=0;i<n;++i)
			a[i]=mul(a[i],Invn);
	}
}
int n;
int a[MAXN<<2],b[MAXN<<2],c[MAXN<<2];
int fac[MAXN],invfac[MAXN],pw[MAXN];
void init()
{
	pw[0]=1;
	for(int i=1;i<=n;++i)
		pw[i]=mul(pw[i-1],2);
	fac[0]=invfac[0]=1;
	for(int i=1;i<=n;++i)
		fac[i]=mul(fac[i-1],i);
	invfac[n]=inv(fac[n]);
	for(int i=n-1;i>=1;--i)
		invfac[i]=mul(invfac[i+1],i+1);
	for(int i=0;i<=n;++i)
		if(i&1)
			a[i]=add(P,-invfac[i]);
		else
			a[i]=invfac[i];
	b[0]=1;
	b[1]=n+1;
	for(int i=2;i<=n;++i)
	{
		b[i]=add(fpow(i,n+1),P-1);
		b[i]=mul(b[i],inv(i-1));
		b[i]=mul(b[i],invfac[i]);
	}
}
int main()
{
	n=read();
	init();
	int N=1,lim=0;
	while(N<=2*n)
		N<<=1,++lim;
	NTT_init(N,lim);
	DFT(a,N,false);
	DFT(b,N,false);
	for(int i=0;i<N;++i)
		c[i]=mul(a[i],b[i]);
	DFT(c,N,true);
	int ans=0;
	for(int i=0;i<=n;++i)
	{
		int tmp=mul(pw[i],fac[i]);
		ans=add(ans,mul(tmp,c[i]));
	}
	cout<<ans<<endl;
	return 0;
}