Stack

Question

定义 $f (p)$ 为对排列 $p$ 跑一次单调栈之后栈中剩余元素的个数，求长度为 $n$ 的所有排列的 $(f (p))^{3}$ 的和，一共有 $T$ 组询问

Solution

借鉴了牛课讨论区的一个大佬的做法：链接

定义了 $g (n, i)$ 表示长度为 $n$ 的所有排列中 $f (p) = i$ 的个数，我们要求的答案就是 $S (n) = \sum_{i = 1}^{n} g (n, i) \times i^{3}$

这是第一类斯特林数的一个定义，得到 $g (n + 1, i) = n g (n, i) + g (n, i - 1)$

试着计算 $S (n + 1)$ 的递推式

\begin{aligned} S (n + 1) & = \sum_{i = 1}^{n + 1} g (n, i) \times i^{3} \\ = n \sum_{i = 1}^{n + 1} i^{3} \times g (n, i) + \sum_{i = 0}^{n} g (n, i) \times (i + 1)^{3} \\ = n \sum_{i = 1}^{n} i^{3} \times g (n, i) + \sum_{i = 1}^{n} g (n, i) \times (i^{3} + 3 i^{2} + 3 i + 1) \\ = (n + 1) \sum_{i = 1}^{n} g (n, i) \times i^{3} + 3 \sum_{i = 1}^{n} g (n, i) \times i^{2} + 3 \sum_{i = 1}^{n} g (n, i) \times i + \sum_{i = 1}^{n} g (n, i) \end{aligned}

已知 $\sum_{i = 1}^{n} g (n, i)$ 表示所有排列方案，即 $n!$

然后观察到， $\sum_{i = 1}^{n} g (n, i) \times i^{3}$ 就是 $S (n)$ ，但是 $\sum_{i = 1}^{n} g (n, i) \times i^{2}$ 和 $\sum_{i = 1}^{n} g (n, i) \times i$ 未知，我们分别把他们定义为 $S_{2} (n)$ 和 $S_{1} (n)$ 寻找他们的递推式

\begin{aligned} S_{2} (n + 1) & = \sum_{i = 1}^{n + 1} g (n, i) \times i^{2} \\ = n \sum_{i = 1}^{n + 1} i^{2} \times g (n, i) + \sum_{i = 0}^{n} g (n, i) \times (i + 1)^{2} \\ = n \sum_{i = 1}^{n} i^{2} \times g (n, i) + \sum_{i = 1}^{n} g (n, i) \times (i^{2} + 2 i + 1) \\ = (n + 1) \sum_{i = 1}^{n} g (n, i) \times i^{2} + 2 \sum_{i = 1}^{n} g (n, i) \times i + \sum_{i = 1}^{n} g (n, i) \\ = (n + 1) S_{2} (n) + 2 S_{1} (n) + n! \end{aligned}

\begin{aligned} S_{1} (n + 1) & = \sum_{i = 1}^{n + 1} g (n, i) \times i \\ = n \sum_{i = 1}^{n + 1} i^{2} \times g (n, i) + \sum_{i = 0}^{n} g (n, i) \times (i + 1) \\ = (n + 1) \sum_{i = 1}^{n} g (n, i) \times i + n! \\ = (n + 1) S_{1} (n) + n! \end{aligned}

于是我们得到了递推式

\begin{aligned} S (n) & = n S (n - 1) + 3 S_{2} (n - 1) + 3 S_{1} (n - 1) + (n - 1)! \\ S_{2} (n) & = n S_{2} (n - 1) + 2 S_{1} (n - 1) + (n - 1)! \\ S_{1} (n) & = n S_{1} (n - 1) + (n - 1)! \end{aligned}

其中 $S (0) = S_{1} (0) = S_{2} (0) = 0$