当前位置 : 主页 > 网络编程 > 其它编程 >

【HDU2019多校】1005EverythingIsGeneratedInEqualProbability(期望可加性)

来源:互联网 收集:自由互联 发布时间:2023-07-02
题目:给出一个数n,在【1,n】等概率的选择一个数i,在【1,i】内每次等概率的选择一个数字组成长度为i的序列,这个序列中所有数都在【1,i】内,且两两互不相同(也就是说这个长
题目:给出一个数n,在【1,n】等概率的选择一个数i,在【1,i】内每次等概率的选择一个数字组成长度为i的序列,这个序列中所有数都在【1,i】内,且两两互不相同(也就是说这个长度为

题目:给出一个数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:

#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;}

  

网友评论