题意：给定一个N，随机从[1,N]里产生一个n，
然后随机产生一个n个数的全排列，求出n的逆序数对的数量并累加ans，
然后随机地取出这个全排列中的一个子序列，重复这个过程，直到为空，求ans在模998244353下的期望
思路：期望仅与长度有关，随手推一下式子
听说有通项公式
1 #include<bits/stdc++.h>
2 using namespace std;
3 typedef long long ll;
4 typedef unsigned int uint;
5 typedef unsigned long long ull;
6 typedef pair<int,int> PII;
7 typedef pair<ll,ll> Pll;
8 typedef vector<int> VI;
9 #define N 110000
10 #define M 1100000
11 #define fi first
12 #define se second
13 #define MP make_pair
14 #define pi acos(-1)
15 #define mem(a,b) memset(a,b,sizeof(a))
16 #define rep(i,a,b) for(int i=(int)a;i<=(int)b;i++)
17 #define per(i,a,b) for(int i=(int)a;i>=(int)b;i--)
18 #define lowbit(x) x&(-x)
19 #define Rand (rand()*(1<<16)+rand())
20 #define id(x) ((x)<=B?(x):m-n/(x)+1)
21 #define ls p<<1
22 #define rs p<<1|1
23
24 const ll MOD=998244353,inv2=(MOD+1)/2;
25 double eps=1e-6;
26 ll INF=1e14;
27
28 ll fac[N],inv[N],dp[N],mi[N];
29
30 ll pw(ll x,ll y)
31 {
32 ll t=1;
33 while(y)
34 {
35 if(y&1) t=t*x%MOD;
36 x=x*x%MOD;
37 y>>=1;
38 }
39 return t;
40 }
41
42 int read()
43 {
44 int v=0,f=1;
45 char c=getchar();
46 while(c<48||57<c) {if(c=='-') f=-1; c=getchar();}
47 while(48<=c&&c<=57) v=(v<<3)+v+v+c-48,c=getchar();
48 return v*f;
49 }
50
51 ll calc(ll n)
52 {
53 ll t=n*(n-1)/2;
54 return t*inv2%MOD;
55 }
56
57 ll c(ll n,ll m)
58 {
59 if(n<m||m<0) return 0;
60 ll t=fac[n]*inv[m]%MOD*inv[n-m]%MOD;
61 return t;
62 }
63
64 int main()
65 {
66 //freopen("1.in","r",stdin);
67 //freopen("1.out","w",stdout);
68 int n;
69 fac[0]=1;
70 rep(i,1,3000) fac[i]=fac[i-1]*i%MOD;
71 inv[0]=inv[1]=1;
72 rep(i,2,3000) inv[i]=inv[MOD%i]*(MOD-MOD/i)%MOD;
73 rep(i,1,3000) inv[i]=inv[i-1]*inv[i]%MOD;
74 mi[0]=1;
75 rep(i,1,3000) mi[i]=mi[i-1]*inv2%MOD;
76 rep(i,1,3000)
77 {
78 ll t=0;
79 rep(j,1,i-1) t=(t+dp[j]*c(i,j)%MOD*mi[i]%MOD)%MOD;
80 dp[i]=(calc(i)+t)%MOD*pw(1ll-mi[i]+MOD,MOD-2)%MOD;
81 }
82 rep(i,1,3000) dp[i]=(dp[i]+dp[i-1])%MOD;
83 inv[0]=inv[1]=1;
84 rep(i,2,3000) inv[i]=inv[MOD%i]*(MOD-MOD/i)%MOD;
85 while(scanf("%d",&n)!=EOF)
86 {
87 printf("%I64d\n",dp[n]*inv[n]%MOD);
88 }
89 return 0;
90 }