题意：
给定一个N，随机从[1,N]里产生一个n，然后随机产生一个n个数的全排列，求出n的逆序数对的数量，加到cnt里，然后随机地取出这个全排列中的一个非连续子序列（注意这个子序列可以是原序列），再求出这个子序列的逆序数对，加到cnt里，重复这个过程，直到最后取出的为空。
题解：
先不考虑第一步随机从[1,N]里产生一个n，只考虑n给定的情况，求出了f[n],那么最后的结果就是
$ ans[N]=frac{sum_{n=1}^N f[n]}{N} $
赛时和队友利用找规律法和暴力模拟法推出
$ f[i]=sum_{i=1}^{n-1}frac{2i}{3} $
下面给出证明：
因为任意一个长度为n的全排列，其所含的逆序对的期望为
$ inom{n}{2}/2 $ （不难理解，就是随便取两个点交换一下就出来一个逆序对）
而取出的那一个非连续子序列，我们把它里面的数字离散化以后也是一个全排列，所以
$ f[i]=inom{n}{2}/2+frac{1}{2^i}sum_{j=0}^iinom{i}{j}f[j] $
移项，得到递推公式
$ f[i]=frac{2^{i-1}}{2^i-1}inom{n}{2}/2+frac{1}{2^i-1}sum_{j=0}^{i-1}inom{i}{j}f[j] $
f[1]=0，不难推出通项公式
$ f[i]=sum_{i=1}^{n-1}frac{2i}{3} $
代码：
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <cctype> #include <string> #include <vector> #include <map> #include <set> #include <vector> #include <queue> #include <stack> const int MOD = 998244353; #define rep(i,n,m) for(int i=n;i<=m;++i) const double eps = 1e-16; #define ll long long using namespace std; const int maxn = 10000000; const int maxm = 2e5 + 10; const int inf = 1 << 28; typedef pair<int, int> P; #define zero(a) fabs(a)<eps inline int read() { int x = 0, f = 1; char ch = getchar(); while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') { x = 10 * x + ch - '0'; ch = getchar(); } return x * f; } ll quick_mod(ll x, ll n) { ll res = 1; while (n) { if (n & 1) res = res * x % MOD; x = x * x % MOD; n = n >> 1; } return res; } ll a[3005]; void init() { a[0] = a[1] = 0; a[2] = 2; for (int i = 3; i <= 3000; ++i) a[i] = a[i - 1] + (i - 1) * 2; for (int i = 1; i <= 3000; ++i) a[i] += a[i - 1]; } int main() { ll n; init(); while (~scanf("%lld", &n)) { if (n == 1) { cout << "0" << endl; continue; } ll a1 = a[n]; ll b = 3 * n; ll x = quick_mod(b, MOD - 2); cout << a1 % MOD * x % MOD<<endl; } }