题解 P4091 【[HEOI2016/TJOI2016]求和】
EndSaH
·
·
题解
欢迎光临博客
比较简单易懂的线性做法。
下面用 \begin{Bmatrix} i \\ j \end{Bmatrix} 表示第二类斯特林数，也即将 i 划分成 j 个非空集合的方案数。
首先我想吐槽一下，这真的不是随手化式子化到一半出出来的题吗……
关于第二类斯特林数，有一个为大家所熟知的公式：
$$
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$ 时需要线性筛。
为了避免占用过大版块，代码就不放了……要看去 loj 搜或者去博客看吧。