[HEOI2016]求和

Description

给出 $n$,求
$$
\sum _{i = 0} ^n \sum _{j = 0} ^i \begin{Bmatrix} i \\ j \end{Bmatrix} j! 2 ^j
$$
其中 $\begin{Bmatrix} i \\ j \end{Bmatrix}$ 表示第二类斯特林数,也即将 $i$ 划分成 $j$ 个非空集合的方案数。
$$
1 \le n \le 10 ^5 \\
\texttt{Bonus:} n \le 10 ^7
$$

Solution

首先我想吐槽一下,这真的不是随手化式子化到一半出出来的题吗……

$2$ 的次幂是友好的,主要是把这个斯特林数给处理掉。

关于第二类斯特林数,有一个为大家所熟知的公式:
$$
i ^k = \sum _{j = 0} ^k \begin{Bmatrix} k \\ j \end{Bmatrix} j! {i \choose j}
$$
其组合意义相当于 $i$ 个盒子 $k$ 个球任放,左边显然,右边枚举有 $j$ 个盒子非空并将球分到这 $j$ 个盒子里去。

注意右边的上界可以改写成 $i$。考虑若 $k$ 为一定值,可以通过二项式反演得到:
$$
\begin{Bmatrix} k \\ j \end{Bmatrix} j! = \sum _{i = 0} ^j (-1) ^{j - i} {j \choose i} i ^k
$$
把这个式子代入到题目所给的式子中(顺便修改 $j$ 的枚举上界为 $n$,斯特林数确保了改变上界不会出错):
$$
\sum _{i = 0} ^n \sum _{j = 0} ^n 2 ^j \sum _{k = 0} ^j (-1) ^{j - k} {j \choose k} k ^i
$$
看上去式子只是变的更复杂了……其实不然,注意到 $i$ 的枚举可以提到后面去:
$$
\sum _{j = 0} ^n 2 ^j \sum _{k = 0} ^j (-1) ^{j - k} {j \choose k} \sum _{i = 0} ^n k ^i
$$
发现后面这个等比数列求和是非常友好的。令 $a _k = \sum \limits _{i = 0} ^n k ^i$,上式就变成了一个易于卷积的形式,可以做到 $O(n \log n)$。

实际上还能做到更好。再交换一下和式:
$$
\begin{aligned}
& \sum _{k = 0} ^n a _k \sum _{j = k} ^n 2 ^j (-1) ^{j - k} {j \choose k} \\
=& \sum _{k = 0} ^n a _k 2^k \sum _{j = k} ^n (-2) ^{j - k} {j \choose k}
\end{aligned}
$$
看一下后面的那一块怎么算。


$$
b _j = \sum _{i = j} ^n {i \choose j} q ^{i - j}
$$
考虑如何在线性时间内求出 $b$。

$b _0$ 是易于计算的,而考虑 $b _j$:
$$
\begin{aligned}
b _j &= \sum _{i = j} ^n {i \choose j} q ^{i - j} \\
&= \sum _{i = j} ^n {i - 1 \choose j} q ^{i - j} + \sum _{i = j} ^n {i - 1 \choose j - 1} q ^{i - j}
\end{aligned}
$$
两部分分开计算。

左部分:
$$
\begin{aligned}
& \sum _{i = j} ^n {i - 1 \choose j} q ^{i - j} \\
=& \sum _{i = j - 1} ^{n - 1} {i \choose j} q ^{i - j + 1} \\
=& q \sum _{i = j} ^{n - 1} {i \choose j} q ^{i - j} \\
=& q (a _j - {n \choose j} q ^{n - j})
\end{aligned}
$$
右部分:
$$
\begin{aligned}
& \sum _{i = j} ^n {i - 1 \choose j - 1} q ^{i - j} \\
=& \sum _{i = j - 1} ^{n - 1} {i \choose j - 1} q ^{i - j + 1} \\
=& \sum _{i = j - 1} ^{n - 1} {i \choose j - 1} q ^{i - (j - 1)} \\
=& b _{j - 1} - {n \choose j - 1} q ^{n - (j - 1)}
\end{aligned}
$$
所以
$$
b _j = qb _j - {n \choose j} q ^{n - j + 1} + b _{j - 1} - {n \choose j - 1} q ^{n - j + 1}
$$
于是
$$
(1 - q) b _j = b _{j - 1} - q ^{n - j + 1} \left( {n \choose j} +{n \choose j - 1} \right)
$$

预处理好组合数和 $q$ 的幂次即可做到 $O(n)$ 的求出 $b$。

求出 $b$ 之后原式也易于在 $O(n)$ 内求出,故总复杂度 $O(n)$。注意求 $a _k$ 时需要线性筛。

Code

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
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>

#define Dec(x) (x >= mod ? x -= mod : 0)
#define Inc(x) (x < 0 ? x += mod : 0)

using namespace std;
using LL = long long;

const int maxN = 1e7 + 5;
const int mod = 998244353;
const int INV3 = 332748118;

int n;
int pw[maxN], inv[maxN], prop[maxN];
int fac[maxN], ifac[maxN];
int b[maxN];

int FPM(int bas, int ind)
{
int res = 1;
while (ind)
{
if (ind & 1)
res = (LL)res * bas % mod;
bas = (LL)bas * bas % mod;
ind >>= 1;
}
return res;
}

inline int C(int N, int M)
{
if (N < 0 or M < 0 or N < M)
return 0;
return (LL)fac[N] * ifac[M] % mod * ifac[N - M] % mod;
}

void Sieve()
{
static bool vis[maxN];
static vector<int> prim;

for (int i = 2; i <= n; ++i)
{
if (!vis[i])
{
prim.push_back(i);
prop[i] = FPM(i, n + 1);
}
for (int j : prim)
{
if (i * j > n)
break;
vis[i * j] = true;
prop[i * j] = (LL)prop[i] * prop[j] % mod;
if (i % j == 0)
break;
}
}
}

void Initmath()
{
fac[0] = ifac[0] = 1;
for (int i = 1; i <= n; ++i)
fac[i] = (LL)fac[i - 1] * i % mod;
ifac[n] = FPM(fac[n], mod - 2);
for (int i = n - 1; i; --i)
ifac[i] = LL(i + 1) * ifac[i + 1] % mod;

pw[0] = 1;
for (int i = 1; i <= n; ++i)
pw[i] = pw[i - 1] * -2ll % mod, Inc(pw[i]);

inv[1] = 1;
for (int i = 2; i <= n; ++i)
inv[i] = mod - LL(mod / i) * inv[mod % i] % mod;

prop[0] = 1, prop[1] = n + 1;
Sieve();
for (int i = 2; i <= n; ++i)
prop[i] = (LL(prop[i] - 1) * inv[i - 1]) % mod;
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("wib.in", "r", stdin);
freopen("wib.out", "w", stdout);
#endif
ios::sync_with_stdio(false);
cin >> n;
Initmath();

for (int i = 0; i <= n; ++i)
b[0] += pw[i], Dec(b[0]);
for (int i = 1; i <= n; ++i)
{
b[i] = (b[i - 1] - LL(C(n, i) + C(n, i - 1)) * pw[n - i + 1]) % mod * INV3 % mod;
Inc(b[i]);
}

int ans = 0;
for (int i = 0; i <= n; ++i)
{
int t = (i & 1) ? mod - pw[i] : pw[i];
ans = (ans + (LL)t * prop[i] % mod * b[i]) % mod;
}
cout << ans << endl;

return 0;
}