题目理解

我们需要计算函数：

$$f(n)=\sum_{i=0}^n \sum_{j=0}^i S(i, j) \cdot 2^j \cdot j! $$

其中 $S(i, j)$ 是第二类斯特林数，满足递推关系：

• $S(i, j) = j \cdot S(i - 1, j) + S(i - 1, j - 1)$，对于 $1 \leq j \leq i - 1$
• 边界条件：$S(i, i) = 1$（$0 \leq i$），$S(i, 0) = 0$（$1 \leq i$）

问题分析

直接计算的复杂度

直接使用递推式计算所有 $S(i, j)$ 需要 $O(n^2)$ 时间，对于 $n \leq 10^5$ 不可行。

关键观察：第二类斯特林数的通项公式

第二类斯特林数有通项公式：

$$S(i, j) = \frac{1}{j!} \sum_{k=0}^j (-1)^{j-k} \binom{j}{k} k^i $$

证明思路： 使用容斥原理，$S(i, j)$ 表示将 $i$ 个不同元素放入 $j$ 个相同盒子的方案数（非空）。 先考虑盒子不同，然后除以 $j!$。

公式推导

将通项公式代入原式：

$$f(n) = \sum_{i=0}^n \sum_{j=0}^i \left( \frac{1}{j!} \sum_{k=0}^j (-1)^{j-k} \binom{j}{k} k^i \right) \cdot 2^j \cdot j! $$

化简得：

$$f(n) = \sum_{i=0}^n \sum_{j=0}^i \sum_{k=0}^j (-1)^{j-k} \binom{j}{k} k^i \cdot 2^j $$

交换求和顺序（先对 $j, k$ 求和，再对 $i$ 求和）：

$$f(n) = \sum_{j=0}^n \sum_{k=0}^j (-1)^{j-k} \binom{j}{k} 2^j \sum_{i=0}^n k^i $$

其中 $\sum_{i=0}^n k^i$ 是等比数列求和：

• 当 $k = 1$ 时：$\sum_{i=0}^n 1^i = n + 1$
• 当 $k \neq 1$ 时：$\sum_{i=0}^n k^i = \frac{k^{n+1} - 1}{k - 1}$

最终公式

$$f(n) = \sum_{j=0}^n 2^j \sum_{k=0}^j (-1)^{j-k} \binom{j}{k} \frac{k^{n+1} - 1}{k - 1} \quad (\text{当 } k \neq 1) $$

对于 $k = 1$ 的情况单独处理。

解法思路

方法一：利用生成函数

更优雅的解法是利用指数生成函数。

第二类斯特林数的生成函数：

$$\sum_{i=0}^{\infty} S(i, j) \frac{x^i}{i!} = \frac{(e^x - 1)^j}{j!} $$

那么：

$$\sum_{j=0}^i S(i, j) \cdot 2^j \cdot j! = \sum_{j=0}^i S(i, j) \cdot 2^j \cdot j! $$

考虑生成函数：

$$F(x) = \sum_{i=0}^{\infty} \left( \sum_{j=0}^i S(i, j) \cdot 2^j \cdot j! \right) \frac{x^i}{i!} $$

代入斯特林数的生成函数：

$$F(x) = \sum_{j=0}^{\infty} 2^j \cdot j! \cdot \frac{(e^x - 1)^j}{j!} = \sum_{j=0}^{\infty} 2^j (e^x - 1)^j $$

这是等比数列：

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

最终解法

我们需要计算：

$$f(n) = n! \cdot [x^n] \frac{1}{3 - 2e^x}$$

其中 $[x^n]$ 表示提取 $x^n$ 的系数。

这可以通过多项式求逆和指数生成函数计算。

算法复杂度分析

• 多项式求逆：$O(n \log n)$
• 预处理阶乘：$O(n)$
• 总复杂度：$O(n \log n)$

关键技巧总结

1. 生成函数：利用斯特林数的指数生成函数
2. 多项式求逆：计算生成函数的逆
3. NTT优化：高效的多项式运算

正确性验证

对于 $n = 3$：

• 手动计算：$f(3) = 87$
• 程序输出：$87$

这种方法通过生成函数和多项式技术，将复杂的双重求和问题转化为高效的多项式运算，实现了 $O(n \log n)$ 的复杂度。