题解 CF846F 【Random Query】

2019-03-13 14:29:24


其实,我们就是要求一个序列的所有子区间的数的种类数之和

我们考虑,假设从左到右第一次出现的数产生贡献

那么,对于一个数$a_i$,它产生贡献的区间

l 需要在 相同数的上一次出现的位置 + 1 ~ i

r 需要在 i~n

对于生成的l,r 有 $n^2$种情况

其中l ≠ r 时都有两种可能(l> r 和 l < r)

l = r时候只有一种情况

所以要特殊处理 l = r

#include<bits/stdc++.h>
using namespace std;

#define LL long long
#define MAXN 1000005

LL n,m;
LL a[MAXN],c[MAXN];
LL ans;

void rd()
{
    cin >> n;
    for(int i = 1; i <= n; i ++)
        cin >> a[i];
}

int main()
{
    rd();
    for(int i = 1; i <= n; i ++) {
        ans += (i - c[a[i]]) * (n - i+1) * 2 - 2;
        c[a[i]] = i;
    }
    ans += n;
    printf("%.6lf",(double)ans/(double)(n*n));
    return 0;
 }