题目重述

初始数组为 $[0, 1]$。每一步操作：设当前数组的逆序对数为 $k$，将 $k$ 插入到数组的任意位置（包括开头和结尾）。给定 $n$，问经过若干次操作后，能得到的所有不同的、长度为 $n$ 的数组的数量，结果对 $998244353$ 取模。

---

关键观察

$1$. 初始数组：$[0,1]$ 的逆序对数为 $0$。 $2$. 当逆序对数 $k > \max(a)$ 时，$k$ 大于数组中的所有元素，插入 $k$ 后，新数组的逆序对数会如何变化？

• 若插入到末尾：因为 $k$ 比所有元素大，不会产生新的逆序对，逆序对数仍为 $k$。
• 若插入到其他位置：$k$ 比它前面的所有元素大，但比它后面的所有元素小？等一下——如果 $k$ 大于所有元素，那么它比后面所有元素都大，所以会与后面每个元素形成一个逆序对。因此逆序对数会增加，并且新的逆序对数 > $k$，从而继续保持 $k' > \max(a')$ 的性质。

因此，一旦逆序对数超过数组中的最大值，这个性质就会一直保持下去。

---

状态定义

设 $dp[i]$ 表示：当前数组长度为 $i$，且当前逆序对数 $k$ 严格大于数组所有元素时，最终能得到的长度为 $n$ 的不同数组的数量。

---

转移推导

当前数组长度为 $i$，逆序对数为 $k$（$k > \max(a)$）。

• 如果我们在末尾插入 $k$，逆序对数不变，长度变为 $i+1$，仍然满足 $k > \max(a')$。这样我们可以连续在末尾插入 $k$ 多次，最后再在某个非末尾位置插入一次，从而跳到更大的长度。
• 更系统地说：
  设当前是 $dp[i]$ 的状态。我们考虑第一次在非末尾位置插入 $k$ 的时刻。在此之前，我们可以在末尾插入 $k$ 任意次（包括 $0$ 次）。设我们在末尾插入了 $j$ 次，那么长度变为 $i+j$，然后我们选择一个非末尾位置（有 $i+j$ 种选择）插入 $k$，长度变为 $i+j+1$，此时新的逆序对数 $k' > k$，状态变为 $dp[i+j+1]$。

所以：

$$dp[i] = \sum_{j \ge 0} (i+j) \cdot dp[i+j+1] + 1$$

这里的 $+1$ 是：我们可以一直只在末尾插入 $k$，直到长度达到 $n$，这样得到一种最终数组（不再插入非末尾位置）。也就是说，我们可以在状态 $dp[i]$ 时就停止并直接得到最终数组。

令 $s = \sum_{t > i} dp[t]$，则：

$$dp[i] = i \cdot s + \sum_{j \ge 1} j \cdot dp[i+j+1] + 1 $$

但更简单的推导来自标程：

标程中实际上是：

$$dp[i] = \left( i \cdot \sum_{j>i} dp[j] + 1 \right) \bmod M $$

为什么？因为从 $dp[i]$ 出发，选择一次非末尾插入，位置有 $i$ 种（插入到前 $i$ 个位置，因为末尾单独处理）。插入后长度变成 $i+1$，但这里要注意：插入一次后，逆序对数变为 $> k$，状态变为 $dp[i+1]$，但 $dp[i+1]$ 已经包含了之后的所有可能性。所以 $dp[i]$ 直接依赖于 $dp[i+1]$ 及之后的所有 $dp$ 值。

更严格的推导是：

$$dp[i] = i \cdot dp[i+1] + i \cdot dp[i+2] + \dots + 1 $$

即：第一次非末尾插入的位置有 $i$ 种，然后长度变成 $i+1$ 并进入 $dp[i+1]$ 状态；或者插入后长度变成 $i+2$（如果我们在末尾先插入一次再在非末尾插入）等等。实际上就是：

$$dp[i] = i \cdot \sum_{j=i+1}^n dp[j] + 1$$

这正是标程中的形式。

---

初始状态和最终答案

我们只关心 $dp[i]$ 当 $i \ge 3$ 时，因为 $dp[2]$ 对应初始 $[0,1]$ 但此时 $k=0$ 并不大于 $\max=1$，所以 $dp[2]$ 不能用这个递推。

但我们知道，初始时只有两个元素 $[0,1]$，逆序对数 $k=0$。我们要从 $[0,1]$ 出发，通过操作得到长度为 $n$ 的数组。

有两种情况：

$1$. 整个过程逆序对数一直 $≤ 1$
这意味着我们只插入 $0$ 和 $1$。可以证明，这样得到的数组只能是形如：前面一串 $0$，中间一个 $[0,1,0]$ 模式，后面一串 $1$。更具体地说，这类数组的数量是 $n-1$（因为我们可以选择第一次出现 $1$ 的位置，但最后要满足逆序对数 $≤1$ 的限制）。标程中直接给出 $n-1$ 种。

$2$. 过程中第一次出现逆序对数 $> 1$
设此时数组长度为 $m$（$m \ge 3$），并且这次插入的 $k > 1$。在此之前，数组处于“逆序对数 ≤1”的状态。前面已知，长度为 $m-1$ 的“逆序对数 ≤1”的数组有 $(m-2)(m-1)/2 - 1$ 种（推导略，可参考提示）。然后我们在这个数组上插入一个 $k > 1$，使得新的逆序对数 $> 1$，进入 $dp[m]$ 状态。因此这部分贡献为：

$$\sum_{m=3}^n \left( \frac{(m-2)(m-1)}{2} - 1 \right) \cdot dp[m] $$

所以最终答案：

$$\text{ans} = (n-1) + \sum_{m=3}^n \left( \frac{(m-2)(m-1)}{2} - 1 \right) \cdot dp[m] \quad (\text{mod } 998244353) $$

---

代码实现

#include<bits/stdc++.h>
using namespace std;

const int N = 1e6 + 9, mod = 998244353;
using ll = long long;

int dp[N]; // dp[i] 表示长度 i 且当前逆序对数 > max 时，最终长度为 n 的数组数

void solve() {
    int n; cin >> n;
    int sum = 0;
    // 倒序计算 dp
    for (int i = n; i >= 1; i--) {
        dp[i] = (1LL * i * sum % mod + 1) % mod;
        sum = (sum + dp[i]) % mod;
    }
    int ans = n - 1; // 逆序对数 ≤1 的情况
    for (int k = 3; k <= n; k++) {
        int ways = (1LL * (k - 1) * (k - 2) / 2 - 1 + mod) % mod;
        ans = (ans + 1LL * ways * dp[k]) % mod;
    }
    cout << ans << '\n';
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

---

时间复杂度

预处理 $dp$ 数组 $O(n)$，每个测试用例 $O(n)$，总 $O(\sum n) \le 10^6$，可以通过。

---

总结

• 关键洞察：当逆序对数大于数组最大值时，插入操作有规律，可以 $DP$。
• 分两类讨论：始终 $≤1$ 逆序对，和第一次出现 $>1$ 逆序对。
• 通过后缀和优化 $DP$ 转移。