我们把\(S(i, j)j!\)看成是把\(i\)个球每次选择一些球（不能为空）扔掉，选\(j\)次后把所有球都扔掉的情况数（顺序有关）。因此\(S(i, j)j! = i^j\)
为了求出答案，我们需要研究如下的生成函数的性质。
\(P(x) = \sum_{i = 0}^{n}(2e^x - 2)^i = \sum_{i = 0}^{n} 2^i \sum_{j = 0}^{i} (-1)^{i - j}e^{jx} {i \choose j} = \sum_{j = 0}^{n} e^{jx}\sum_{i = j}^{n} 2^i(-1)^{i - j} {i \choose j}\)
令\(a_j = \sum_{i = j}^{n} (-2)^i {i \choose j}\)。在线性时间内计算\(a_j\)是个经典的问题。
则\(a_0\)是很容易计算的。
且\(j \ge 1\)时:
\(a_j\)
\(= \sum_{i = j}^{n} (-2)^i ({i - 1 \choose j} + {i - 1 \choose j - 1})\)
\(= -2\sum_{i = j}^{n - 1} (-2)^i{i \choose j} -2\sum_{i = j - 1}^{n - 1} (-2)^i{i \choose j - 1}\)
\(= -2a_j + 2(-2)^{n} {n \choose j} - 2a_{j - 1} + 2(-2)^{n} {n \choose j - 1}\)
转换为递推式\(a_j = \frac{1}{3} (2(-2)^n {n \choose j} + 2(-2)^n{n \choose j - 1} - 2a_{j - 1})\)
欲求的答案就是\(\sum_{j = 0}^{n} (-1)^ja_j \sum_{i = 0}^{n} i![x^i]e^{jx}\)
我们发现答案就是\(\sum_{i = 0}^{n} i![x^i]e^{jx} = \sum_{i = 0}^{n} j^i\)，可以使用等比数列求和公式计算。
我们需要计算\(j^{n + 1}\)，这可以先计算出\(j\)为素数处的取值，然后再用线性筛算出\(1 \leq j \leq n\)时的取值。复杂度变成了\(O(\frac{n}{\ln n} \cdot log_2{n}) = O(n)\)
于是，我们在\(O(n)\)的时间内做出了本题。顺便获得目前的rk1.
原文：https://www.cnblogs.com/mathematician/p/12693500.html