HDU2019多校1005题EverythingIsGeneratedInEqualProbability的期望可加性原理如何应用？

本文共计676个文字，预计阅读时间需要3分钟。

题目：给定一个数n，在[1，n]等概概率的选出一个数i，在[1，i]内每次等概概率的选出一个数组成长度为i的序列，这个序列中所有数都在[1，i]内，且两两互不相同。

题目：给出一个数n,在等概率的选择一个数i，在内每次等概率的选择一个数字组成长度为i的序列，这个序列中所有数都在内，且两两互不相同（也就是说这个长度为

题目：给出一个数n,在等概率的选择一个数i，在内每次等概率的选择一个数字组成长度为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:

#includeusing namespace std;#define lowbit(x) ((x)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 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 > x) { int ans = 0; for(int i = 1; i <= x; i++) ans = (ans + f[i]) % mod; ans = (ans * getInv(x, mod) ) % mod; cout < } return 0;}