words...

嗚嗚嗚，怎么大家都會
覺得題解還行就點個贊吧

題面

對于一個排列\(P\)，定義\(f(P)\)如下：

def f(P:permutation) -> int:
    ans = 0
    st: 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. 情況1：將元素 \(n\) 放在排列的最后一位。

   • 若在排列最后放入 \(n\)，由于排列最后的元素必定為右側極小值，所以新得到的排列中，\(n\) 會額外貢獻一個右側極小值。
   • 因此，原來 \(n-1\) 個元素的排列中的右側極小值數必須為 \(k-1\)
   • 故有 \(s(n-1,k-1)\) 種方式。

2. 情況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\) 處的各階導數

因此有

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). \]

2. 計算 \(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). \]

3. 計算 \(G'''(t)\)：

   對 \(G''(t)\) 再求導，有

   \[G'''(t)=\fracw0obha2h00{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;
}