昔我往矣 杨柳依依

Description

1.给出N，随机$n\in [1,n]$，随机生成n的一个排列。

2对于这个序列统计其逆序对数量。

3.再随机这个序列的一个子序列。

4.如果子序列长度为0，则结束。否则转2。

求期望逆序对数量

Solution

由于每次选取的是原序列的一个子序列，所以每次一个数有1/2的几率被保留/删除

考虑一对逆序对的贡献，首先它在原序列中存在的概率是1/2，考虑这对逆序对期望贡献多少。当这对逆序对中的任何一个数被删除，这对逆序对都将被破坏，那么每一次有3/4的概率将这对逆序对破坏（考虑仅第一个数保留，仅第二个数保留，都不保留），那么期望4/3次后这对逆序对被破坏，即期望贡献4/3。

设 f i f_i fi​为原序列长度为i时的期望贡献，则。
a n s = 1 n ∑ i = 1 n f i f i = 1 2 i ∗ ( i − 1 ) 2 ∗ 4 3 = i ∗ ( i − 1 ) 3 a n s = 1 3 ∗ n ∑ i = 1 n i ∗ i − i = ( n + 1 ) ∗ ( 2 n + 1 ) 18 − ( 1 + n ) 6 = n 2 − 1 9 ans=\frac{1}{n}\sum_{i=1}^nf_i\\f_i=\frac{1}{2}\frac{i\ast(i-1)}{2}\ast\frac{4}{3}=\frac{i\ast(i-1)}{3}\\ans=\frac{1}{3\ast n}\sum_{i=1}^ni\ast i-i=\frac{(n+1)\ast(2n+1)}{18}-\frac {(1+n)}{6}=\frac{n^2-1}{9}\\ ans=n1​i=1∑n​fi​fi​=21​2i∗(i−1)​∗34​=3i∗(i−1)​ans=3∗n1​i=1∑n​i∗i−i=18(n+1)∗(2n+1)​−6(1+n)​=9n2−1​

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！