cf846 F. Random Query · 数学期望

题解

题意：给n个数，任取一个区间，端点可以重合，每个区间被取到的概率是一样的，设每个区间的价值是其不同的数的个数，问整段区间的价值期望

学习来源 · 大佬博客直通车

记记笔记…

在这道题里，
期望 = 总价值 / 区间总数，
因为 $l$l 和 $r$r 是等概率随机的，所以区间也是等概率的，
所以期望 $E=\sum x$E=∑x_区间价值*$p$p_{(区间概率)}$=p\sum x=\cfrac{_{总价值}}{_{区间总数}}$=p∑x=区间总数​总价值​​，

接着是计算总价值：

总共有$n*n$n∗n个 $l、r$l、r，可以知道如果是不同的 $l、r$l、r，贡献要算两次，而相同的贡献只需算一次

设前 $i-1$i−1 个数里总贡献为 $f(i-1)$f(i−1)，

• 假设第 $i$i 个数字在前面的区间里没有出现过，
  则第 $i$i 个数会对区间 $[1,i][2,i][3,i]...[i-1,i][i,i]$[1,i][2,i][3,i]...[i−1,i][i,i] 都有+1的贡献，
• 假设第 $i$i 个数字在前面第 $pos$pos 个位置出现过，
  则第 $i$i 个数对前面 $[1,i][2,i][3,i]...[pos,i]$[1,i][2,i][3,i]...[pos,i] 不会造成影响，对剩余的区间都有+1的影响

总结一下有如下公式：
$f(i)=f(i-1)+(i-pre[i])$f(i)=f(i−1)+(i−pre[i])，其中pre[i]为第i个数之前出现的位置

又因为区间端点可以交换，每个数字的贡献为 $2f(i)-1$2f(i)−1，减1是当l、r相同的时候贡献只要算一次就够了

---

---

#include <bits/stdc++.h>
using namespace std;
typedef double ll;
const int N = 1e6 + 10;
ll f[N];//范围会爆int
int n,m, k;
int pre[N],a[N];
int main() {
    ios::sync_with_stdio(0);

    cin>>n;
    double ans=0.0;
    for (int i = 1; i <= n; ++i) {
        cin>>a[i];
        f[i]=f[i-1]+i-pre[a[i]];
        ans+=2.0*f[i]-1;
        pre[a[i]]=i;
    }
    printf("%.6f\n",ans/(1.0*n*n) );
    
    return 0;
}