牛客多校6 C Stack（数论，第一类斯特林数，铜牌题）

Question

Stack (opens new window)

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

Solution

借鉴了牛课讨论区的一个大佬的做法：链接 (opens new window)

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

这是第一类斯特林数的一个定义，得到 $g(n+1, i)=ng(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+3i^2+3i+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+2i+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)+2S_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$