words...
怎么大家都会，呜呜呜
题面
对于一个排列\(P\)，定义\(f(P)\)如下：
def f(P:permutation) -> int:ans = 0st: Stack[int] = Stack()for i in P:while st is not empty and st.top() > i:st.pop()st.push(i)return st.size()
给定一个整数 \(n\)，求所有长度为 \(n\)的排列\(P\)的\(f(P)\)的立方和，结果对\(998244353\)取模。
形式化地：
\(S_n\)表示所有长度为 \(n\)的排列的集合。
- 输入
- 第一行包含一个正整数\(T\)，表示测试用例的数量。
- 接下来\(T\)行，每行包含一个正整数 \(n\)，表示排列的长度。
- 输出
- 对于每个测试用例，输出一行一个整数，表示答案。
思路
转化
每次询问理应做到 \(O(1)\) ,需要预处理，可以把询问离线。
先分析对于某一个排列 \(P\) , \(f(P)\) 如何算：
需要一点点观察的是：
- \(f(P)\) 在 \([1,n]\) 之间
- \(f(P)\) 等价于“排列 \(P\) 中从右往左极小值的个数”,这个个数记为 \(k\) 。
于是可以有如下转化
其中 \(s(n,k)\) 表示对于长度为 \(n\) 的排列，极小值个数为 \(k\) 的排列个数。
现在来看看怎么求解 \(s(n,k)\) 。
尝试能不能递推求解：
递推公式
考虑如何利用 \(n-1\) 个元素的排列来构造 \(n\) 个元素的排列，并分析新元素 \(n\) 对右侧极小值个数的影响。这里 \(n\) 是这 \(n\) 个数中最大的一个。
设\(s(n,k)\) 表示长度为 \(n\) 的排列中右侧极小值个数为 \(k\) 的排列数。
我们有两种情况：
-
情况1：将元素 \(n\) 放在排列的最后一位。
- 若在排列最后放入 \(n\)，由于排列最后的元素必定为右侧极小值，所以新得到的排列中，\(n\) 会额外贡献一个右侧极小值。
- 因此，原来 \(n-1\) 个元素的排列中的右侧极小值数必须为 \(k-1\)
- 故有 \(s(n-1,k-1)\) 种方式。
-
情况2：将元素 \(n\) 插入到排列的末尾之外的任意位置。
- 如果 \(n\) 不放在最后，显然 \(n\) 不会成为右侧极小值，因为它右边至少还有一个元素（且这些元素都比 \(n\) 小，因为 \(n\) 最大）。
- 但是插入 \(n\) 会“破坏”原排列中某个右侧极小值的位置，使得右侧极小值的个数不增加。
- 对于一个固定的 \(n-1\) 个元素的排列，保持右侧极小值数仍为 \(k\) 的排列有 \(s(n-1,k)\) 种，而插入 \(n\) 的位置有 \(n-1\) 个选择（排除最后一位）。
- 故有 \((n-1) \cdot s(n-1,k)\) 种方式。
将两种情况相加，即可得到递推公式：
觉得眼熟？
这正是第一类无符号斯特林数的递推公式
处理边界条件
- 当 \(n = 0\) 时，我们定义 \(s(0,0)= 1\)（空排列记作 1 种方式）。
- 当 \(k = 0\) 且 \(n \ge 1\) 时，无论如何排列至少有 1 个右侧极小值（最后的那个数），所以 \(s(n,0)=0\)。
- 当 \(k = n\) 时，只有一种排列，即排列为严格递增的顺序，这时每个元素都是一个右侧极小值，所以 \(s(n,n)=1\)。
第一类斯特林数的定义是：将 n 个两两不同的元素，划分为 k 个互不区分的非空轮换的方案数。
于是现在我们有：
-
\[ G(n)=\sum_{P \in S_n} f(P)^3 = \sum_{k=1}^{n} k^3 \cdot s(n,k) \]
-
\[n 为排列长度 \]
- 知道了\(s(n,k)\) 是第一类斯特林数。
但是计算还是比较麻烦。
构造
接下来的操作可能会有点人类智慧，而且不是很显然。
思考要是式子能去掉求和就好了，这样比较容易算。
可以构造一个新函数
这里详细介绍如何想到利用生成函数来计算
以及这一方法背后的动机和思路。
这里求的是带权和,于是可以想到生成函数
在组合计数问题中，当遇到这样的带权求和（即求 \((\sum_k (\text{计数数目}) \times w(k))\)），生成函数是一种非常自然和高效的工具，因为生成函数可以将序列的性质和依赖关系转化为函数形式，而系数的多项式求导与加权求和（如 \((\sum k \cdot a_k) 、(\sum k^2 \cdot a_k)\) 等）之间存在密切联系。
对于第一类无符号斯特林数，有一个经典的生成函数
我们对生成函数进行求导，可以得到关于 \(k\) 的加权和：
若令\(t=1\)，则
求到三阶导就有\(k^3\) 了，考虑将\(F'''(1)\),\(F''(1)\),\(F'(1)\)结合起来，利用组合恒等式来分解 \(k^3\) 的求和。
解方程
对应项系数相等，解得：
因此，我们可以将 \(S(n)\) 表示为：
OK，现在开始计算F(t)的表达式
已知的是：
令
取自然对数，得到对数生成函数
设
利用链式法则可以写出 \(F(t)\) 的导数与 \(G(t)\)的关系：
接着计算 \(G(t)\) 及其在 \(t=1\) 处的各阶导数
因此有
-
计算 \(G'(t)\)：
由于
\[G(t)=\sum_{i=0}^{n-1}\ln(t+i), \]对 \(t\) 求导得
\[G'(t)=\sum_{i=0}^{n-1}\frac{1}{t+i}. \]在 \(t=1\) 处，
\[G'(1)=\sum_{i=0}^{n-1}\frac{1}{1+i}=\sum_{j=1}^{n}\frac{1}{j}=H(n). \]应用链式法则，
\[F'(1)=F(1)\,G'(1)=n!\cdot H(n). \] -
计算 \(G''(t)\)：
继续对 \(G'(t)\) 求导：
\[G''(t)=-\sum_{i=0}^{n-1}\frac{1}{(t+i)^2}. \]令 \(t=1\)，则
\[G''(1)=-\sum_{i=0}^{n-1}\frac{1}{(1+i)^2}=-\sum_{j=1}^{n}\frac{1}{j^2}=-H_{2}(n). \]因此，
\[F''(1)=F(1)\Bigl[G''(1)+\bigl(G'(1)\bigr)^2\Bigr] =n!\Bigl[-H_{2}(n)+H(n)^2\Bigr] =n!\cdot\Bigl(H(n)^2-H_{2}(n)\Bigr). \] -
计算 \(G'''(t)\)：
对 \(G''(t)\) 再求导，有
\[G'''(t)=\frac{d}{dt}\Bigl(-\sum_{i=0}^{n-1}\frac{1}{(t+i)^2}\Bigr) =2\sum_{i=0}^{n-1}\frac{1}{(t+i)^3}. \]在 \(t=1\) 时，
\[G'''(1)=2\sum_{i=0}^{n-1}\frac{1}{(1+i)^3} =2\sum_{j=1}^{n}\frac{1}{j^3}=2H_{3}(n). \]再利用已知公式：
\[F'''(1)=F(1)\Bigl[G'''(1)+3G'(1)G''(1)+\bigl(G'(1)\bigr)^3\Bigr], \]
- \(F(1)=n!\)
- \(F'(1)=n!\cdot H(n)\)
- \(F''(1)=n!\cdot\Bigl(H(n)^2- H_{2}(n)\Bigr)\)
- \(F'''(1)=n!\cdot\Bigl(H(n)^3-3H(n)H_{2}(n)+2H_{3}(n)\Bigr)\)
其中
所以：
\(H(n)\),\(H_{2}(n)\),\(H_{3}(n)\) 都可以通过前缀和来计算。
还需要预处理阶乘
和逆元。
时间复杂度\(O(n \log n)\)
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
using ll = long long;constexpr ll MOD = 998244353;
int main()
{ios::sync_with_stdio(0);cin.tie(0);int T;cin >> T;int mxn = 0;vector<int> ask(T);for (int i = 0; i < T; i++){cin >> ask[i];mxn = max(mxn, ask[i]);}vector<ll> fact(mxn + 1, 1);for (int i = 1; i <= mxn; i++)fact[i] = fact[i - 1] * i % MOD;vector<ll> inv(mxn + 1, 1);for (int i = 2; i <= mxn; i++)inv[i] = MOD - MOD / i * inv[MOD % i] % MOD;vector<ll> H(mxn + 1, 0),H2(mxn + 1, 0), H3(mxn + 1, 0);for (int i = 1; i <= mxn; i++){H[i] = (H[i - 1] + inv[i]) % MOD;H2[i] = (H2[i - 1] + inv[i] * inv[i] % MOD) % MOD;H3[i] = (H3[i - 1] + inv[i] * inv[i] % MOD * inv[i] % MOD) % MOD;}for (int i = 0; i < T; i++){int n = ask[i];ll h = H[n], h2 = H2[n], h3 = H3[n];ll res = (h * h % MOD * h % MOD + 3 * h * h % MOD % MOD + h) % MOD;res = (res - 3 * h * h2 % MOD + MOD) % MOD;res = (res - 3 * h2 % MOD + MOD) % MOD;res = (res + 2 * h3 % MOD) % MOD;ll ans = fact[n] * res % MOD;cout << ans << "\n";}return 0;
}