题目描述

对于一个 $1$ 到 $n$ 的排列 $A = (a_1, a_2, \dots, a_n)$，我们定义其价值如下：
1. 对于排列中的第 $i$ 个元素 $a_i$，计算它前面（即下标 $j < i$）有多少个元素 $a_j$ 满足 $a_j < a_i$。将这个计数记为 $c_i$。
2. 排列 $A$ 的总价值定义为所有 $c_i$ 的和：$\text{Value}(A) = \sum_{i=1}^{n} c_i$。

给定一个整数 $n$，需要计算所有 $1$ 到 $n$ 的不同排列的总价值之和。由于结果可能很大，需要将答案对 $998244353$ 取模。

样例

输入:

3

输出:

9

样例解释

$n=3$ 时，有 $3! = 6$ 个排列：
$(1, 2, 3)$: $c_1=0, c_2=|\{1\}|=1, c_3=|\{1, 2\}|=2$. 价值 $= 0+1+2 = 3$.
$(1, 3, 2)$: $c_1=0, c_2=|\{1\}|=1, c_3=|\{1\}|=1$. 价值 $= 0+1+1 = 2$.
$(2, 1, 3)$: $c_1=0, c_2=|\emptyset|=0, c_3=|\{2, 1\}|=2$. 价值 $= 0+0+2 = 2$.
$(2, 3, 1)$: $c_1=0, c_2=|\{2\}|=1, c_3=|\emptyset|=0$. 价值 $= 0+1+0 = 1$.
$(3, 1, 2)$: $c_1=0, c_2=|\emptyset|=0, c_3=|\{1\}|=1$. 价值 $= 0+0+1 = 1$.
$(3, 2, 1)$: $c_1=0, c_2=|\emptyset|=0, c_3=|\emptyset|=0$. 价值 $= 0+0+0 = 0$.
所有排列的价值总和为 $3 + 2 + 2 + 1 + 1 + 0 = 9$。

算法 (组合计数 / 线性期望)

$O(N)$

思路分析

我们要计算的是所有 $n!$ 个排列的价值之和：
$$\text{Total Sum} = \sum_{A \in \text{Permutations}(n)} \text{Value}(A) = \sum_{A \in \text{Permutations}(n)} \left( \sum_{i=1}^{n} c_i(A) \right)$$
其中 $c_i(A) = |\{a_j \mid j < i, a_j < a_i\}|$。

我们可以交换求和的顺序：
$$\text{Total Sum} = \sum_{i=1}^{n} \left( \sum_{A \in \text{Permutations}(n)} c_i(A) \right)$$
现在，我们专注于计算内层的和 $\sum_{A \in \text{Permutations}(n)} c_i(A)$。这表示对于固定的位置 $i$，它对所有排列的总价值贡献之和。
$c_i(A)$ 计算的是在位置 $i$ 之前的 $i-1$ 个位置中，有多少个元素的值小于 $a_i$。我们可以进一步分解 $c_i(A)$：
$$c_i(A) = \sum_{j=1}^{i-1} [a_j < a_i]$$
其中 $[P]$ 是艾弗森括号，如果条件 $P$ 为真，则值为 1，否则为 0。
代入总和表达式：
$$\text{Total Sum} = \sum_{i=1}^{n} \sum_{A \in \text{Permutations}(n)} \sum_{j=1}^{i-1} [a_j < a_i]$$
再次交换求和顺序：
$$\text{Total Sum} = \sum_{i=1}^{n} \sum_{j=1}^{i-1} \left( \sum_{A \in \text{Permutations}(n)} [a_j < a_i] \right)$$
内层 $\sum_{A \in \text{Permutations}(n)} [a_j < a_i]$ 计算的是在所有 $n!$ 个排列中，满足 $a_j < a_i$ 条件的排列数量（对于固定的 $i$ 和 $j < i$）。

考虑任意一对固定的不同位置 $(j, i)$ 且 $j < i$。在 $1$ 到 $n$ 的所有排列中，这两个位置上的值 $a_j$ 和 $a_i$ 必然是不同的 ($a_j \neq a_i$)。
由于排列是对称的，对于任何一对值 $(u, v)$ ($u \neq v$)，它们出现在位置 $(j, i)$ 的排列数量（即 $a_j=u, a_i=v$）和出现在位置 $(i, j)$ 的排列数量（即 $a_j=v, a_i=u$）是相同的，都等于 $(n-2)!$（固定两个位置的值，剩下 $n-2$ 个元素任意排列）。
考虑所有 $n!$ 个排列。对于固定的位置 $j$ 和 $i$ ($j < i$)，比较 $a_j$ 和 $a_i$ 的大小。由于对称性， $a_j < a_i$ 发生的情况数量 和 $a_j > a_i$ 发生的情况数量是完全相同的。
因为 $a_j \neq a_i$，这两种情况覆盖了所有 $n!$ 个排列。
所以，满足 $a_j < a_i$ 的排列数量恰好是总排列数量的一半，即 $n! / 2$。

现在我们可以将这个结果代回总和公式：
$$\text{Total Sum} = \sum_{i=1}^{n} \sum_{j=1}^{i-1} \left( \frac{n!}{2} \right)$$
内层的和 $\sum_{j=1}^{i-1}$ 共有 $i-1$ 项，每一项都是 $n!/2$。所以内层和等于 $(i-1) \times \frac{n!}{2}$。
$$\text{Total Sum} = \sum_{i=1}^{n} (i-1) \frac{n!}{2}$$
将常数因子 $\frac{n!}{2}$ 提出来：
$$\text{Total Sum} = \frac{n!}{2} \sum_{i=1}^{n} (i-1)$$
令 $k = i-1$，则求和变为 $\sum_{k=0}^{n-1} k$。这是一个等差数列求和：
$$\sum_{k=0}^{n-1} k = \frac{(0 + n-1) \times n}{2} = \frac{n(n-1)}{2}$$
将求和结果代回：
$$\text{Total Sum} = \frac{n!}{2} \times \frac{n(n-1)}{2} = \frac{n! \cdot n \cdot (n-1)}{4}$$

计算与模运算
我们需要计算 $\frac{n! \cdot n \cdot (n-1)}{4}$ 对 $p = 998244353$ 取模的结果。
$p$ 是一个质数。
1. 计算 $n! \pmod p$。可以通过循环 $1$ 到 $n$ 累乘并取模得到。
2. 计算 $n \pmod p$ 和 $(n-1) \pmod p$。
3. 计算 $4$ 在模 $p$ 下的乘法逆元 $4^{-1} \pmod p$。因为 $p$ 是质数且 $p > 4$，逆元存在。可以使用费马小定理计算 $4^{p-2} \pmod p$。
4. 将以上结果相乘，并在每步乘法后取模：
$$\text{Answer} \equiv (n! \pmod p) \cdot (n \pmod p) \cdot ((n-1) \pmod p) \cdot (4^{-1} \pmod p) \pmod p$$

代码实现
代码中使用了 MInt 模板类来自动处理模运算。
Z ans = 1; 初始化 ans。
for (int i = 1; i <= n; i ++ ) { ans *= i; } 计算 $n! \pmod p$，结果存储在 ans 中。
ans = ans * n * (n - 1) / 4; 直接计算最终公式。MInt 类重载了乘法 * 和除法 / 运算符。除法 / 4 会自动计算 $4$ 的模逆元并进行乘法。所有运算都在模 $p$ 下进行。
cout << ans << "\n"; 输出结果。

时间复杂度

• 计算 $n!$ 需要 $O(N)$ 时间。
• 计算模逆元（如果用快速幂）需要 $O(\log p)$ 时间，但在 MInt 类中可能已经优化或集成。
• 其余计算是 $O(1)$。
• 总时间复杂度为 $O(N)$。

空间复杂度

• 存储变量需要 $O(1)$ 额外空间（不计 MInt 类内部可能使用的空间）。
• 总空间复杂度为 $O(1)$。

C++ 代码

#include <bits/stdc++.h> // 引入所有标准库

using namespace std;
using i64 = long long; // 定义 i64 为 long long

// 模板函数：计算 a 的 b 次幂 (模意义下)
template <class T>
T power(T a, i64 b) {
    T res = 1;
    for (; b; b /= 2, a *= a) {
        if (b % 2) {
            res *= a;
        }
    }
    return res;
}

// 模板类：模整数 MInt
template <int P> struct MInt {
    int x; // 存储模 P 下的值
    MInt() : x{} {} // 默认构造函数
    MInt(i64 x_) : x{norm(x_ % getMod())} {} // 构造函数，处理取模和负数

    // 静态成员变量 Mod，用于 P=0 时的动态模数 (本题 P>0)
    static int Mod;
    // 静态成员函数获取模数
    static int getMod() { return P > 0 ? P : Mod; } 
    // 静态成员函数设置动态模数 (本题未使用)
    static void setMod(int Mod_) { Mod = Mod_; }

    // 规范化函数，确保值在 [0, P-1]
    int up(int x) const { if (x < 0) x += getMod(); return x; }
    int down(int x) const { if (x >= getMod()) x -= getMod(); return x; }
    int norm(int x) const { return up(down(x)); }

    // 获取值和类型转换
    int val() const { return x; }
    explicit  operator int() const { return x; }

    // 运算符重载
    MInt operator-() const { MInt res; res.x = norm(getMod() - x); return res; }
    MInt inv() const { assert(x != 0); return power(*this, getMod() - 2); } // 模逆元
    MInt &operator+=(MInt rhs) & { return x = down(x + rhs.x), *this; }
    MInt &operator-=(MInt rhs) & { return x = up(x - rhs.x), *this; }
    MInt &operator*=(MInt rhs) & { return x = 1LL * x * rhs.x % getMod(), *this; }
    MInt &operator/=(MInt rhs) & { return *this *= rhs.inv(); } // 除法实现为乘以逆元

    // 友元函数实现普通运算符
    friend MInt operator+(MInt lhs, MInt rhs) { return lhs += rhs; }
    friend MInt operator-(MInt lhs, MInt rhs) { return lhs -= rhs; }
    friend MInt operator*(MInt lhs, MInt rhs) { return lhs *= rhs; }
    friend MInt operator/(MInt lhs, MInt rhs) { return lhs /= rhs; }
    friend bool operator==(MInt lhs, MInt rhs) { return lhs.val() == rhs.val(); }
    friend  bool operator!=(MInt lhs, MInt rhs) { return lhs.val() != rhs.val(); }

    // 友元函数实现流运算符
    friend  std::istream &operator>>(std::istream &is, MInt &a) { i64 x = 0; is >> x; a = MInt(x); return is; }
    friend  std::ostream &operator<<(std::ostream &os, const MInt &a) { return os << a.val(); }
};
// // 如果需要动态模数，需要定义 Mod
// template<int P> int MInt<P>::Mod = P > 0 ? P : 998244353;

constexpr int mod = 998244353; // 定义模数
using Z = MInt<mod>; // 定义 Z 为模整数类型 MInt<998244353>

int main() {
    // 加速 IO
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n; // 输入 n
    cin >> n;

    Z ans = 1; // 初始化 ans 为 1，用于计算阶乘
    // 计算 n! mod p
    for (int i = 1; i <= n; i ++ ) {
        ans *= i; // 累乘，MInt 类自动处理模运算
    }

    // 计算最终结果: (n! * n * (n-1) / 4) mod p
    // MInt 类重载了 * 和 / 运算符，自动处理模运算和模逆元
    ans = ans * n * (n - 1) / 4; 

    // 输出结果
    cout << ans << "\n";

    return 0; // 程序正常结束
}