题目：
给出一个数n,在【1，n】等概率的选择一个数i，在【1，i】内每次等概率的选择一个数字组成长度为i的序列，这个序列中所有数都在【1，i】内，且两两互不相同（也就是说这个长度为i的序列是1->n的一种排列），以这个长度为i的序列为参数array运行程序：
1.统计array中的逆序对数目
2.统计array的子序列的逆序对数目（子序列的长度为0->length(array)），
3.array长度为0结束程序，否则以这个子序列为参数array运行程序，重复1，2
求最终逆序对数目的期望值，对998244353取模
程序如下：
input:
0
1
2
output:
0
332748118
554580197
SOLUTION:
对于这种无限向里递归，我们可以套路的使用递推来推出来
CODE:
#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) ((x)&(-x))
typedef long long ll;
const int maxn = 3005;
const int mod = 998244353;
ll mu[maxn], zi[maxn], f[maxn], c[maxn][maxn];
ll qkpow(ll a,ll p,ll mod)
{
ll t=1,tt=a%mod;
while(p)
{
if(p&1)t=t*tt%mod;
tt=tt*tt%mod;
p>>=1;
}
return t;
}
ll getInv(ll a,ll mod)
{
return qkpow(a,mod-2,mod);
}
void init()
{
//组合数
for(int i = 1; i < maxn;i++)
{
c[i][i] = 1, c[i][0] =1;
for(int j = 1; j < i; j++)
c[i][j] = (c[i-1][j] + c[i-1][j-1]) % mod;
}
//分母
mu[1] = 2;
for(int i = 2; i < maxn; i++)
mu[i] = (mu[i - 1] * 2) % mod;
f[0] = 0, f[1] = 0;
for(int i = 2; i < maxn; i++)
{
//或者不用单开一个分子数组，存到f[i]里
zi[i] = (c[i][2] * mu[i-1]) % mod;//原序列的逆序对期望值!!不要写成c[i][2]/2 * mu[i-1] 因为c[2][2]/2=0，而应该是0.5
zi[i]=0;
for(ll j = 0; j < i; j++)
zi[i] = (zi[i] + (c[i][j] * f[j]) % mod) % mod;
f[i] = (zi[i] * getInv(mu[i] -1 , mod)) % mod;//得到第二个式子的f[i]
f[i] += (1ll*c[i][2] * mu[i-1]%mod*getInv(mu[i]-1,mod)) % mod;
f[i] %=mod;
//p rintf("f[%d]: %lld\n", i, f[i]);
}
}
int main()
{
ios::sync_with_stdio(false);
int x;
init();
while(cin >> x)
{
int ans = 0;
for(int i = 1; i <= x; i++)
ans = (ans + f[i]) % mod;
ans = (ans * getInv(x, mod) ) % mod;
cout << ans << endl;
}
return 0;
}
【HDU2019多校】1005 - Everything Is Generated In Equal Probability（期望可加性）
原文：https://www.cnblogs.com/zhangbuang/p/11285577.html