题目链接：HDU 6595

Y\_UME 有一个整数 $N$ 和一串有趣的代码：

首先，他先等概率随机一个正整数 $n \in [1, N]$，再等概率随机一个长度为 $n$ 的排列。最后他会将这个排列传入函数 $\text{Calculate}$ 并得到一个返回值。请你求出这个值的期望，答案对 $998244353$ 取模。

本题有多组数据。

数据范围：$1 \le N \le 3000$，$\sum N \le 5 \times 10 ^ {4}$。

Solution

一个长度为 $n$ 的随机排列的期望逆序对个数为 $\frac{\binom{n}{2}}{2}$。我们设 $f(i)$ 表示 $N = i$ 的答案。那么有递推式：

$$ f(i) = \frac{\binom{i}{2}}{2} + \frac{1}{2 ^ i} \sum_{j = 0} ^ {i} \binom{i}{j} f(j) $$

移项可以得到：

$$ f(i) = \frac{\binom{i}{2} \cdot 2 ^ {i - 1} + \sum_{j = 0} ^ {i - 1} \binom{i}{j} f(j)}{2 ^ {i} - 1} $$

时间复杂度：$\mathcal O(N ^ 2 + \sum N)$。

Code

#include <cstdio>

const int N = 3e3 + 5;
const int MOD = 998244353;

int n, pw[N], c[N][N], f[N];

void add(int &x, int y) {
    (x += y) >= MOD && (x -= MOD);
}
int pow(int x, int k) {
    int ans = 1;
    for (; k; k >>= 1, x = 1LL * x * x % MOD) {
        if (k & 1) ans = 1LL * ans * x % MOD;
    }
    return ans;
}
int inv(int x) {
    return pow(x, MOD - 2);
}
void init(int n) {
    pw[0] = 1;
    for (int i = 1; i <= n; i++) pw[i] = 2LL * pw[i - 1] % MOD;
    c[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        c[i][0] = 1;
        for (int j = 1; j <= i; j++) {
            c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % MOD;
        }
    }
    for (int i = 2; i <= n; i++) {
        f[i] = 1LL * c[i][2] * pw[i - 1] % MOD;
        for (int j = 0; j < i; j++) add(f[i], 1LL * c[i][j] * f[j] % MOD);
        f[i] = 1LL * f[i] * inv(pw[i] - 1) % MOD;
    }
    for (int i = 1; i <= n; i++) add(f[i], f[i - 1]);
    for (int i = 1; i <= n; i++) f[i] = 1LL * f[i] * inv(i) % MOD;
}
int main() {
    init(N - 5);
    for (; scanf("%d", &n) == 1; ) printf("%d\n", f[n]);
    return 0;
}