304429: CF846F. Random Query

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Random Query

题意翻译

- 给定长度为 $n$ 的序列 $a$。您要随机地选取两个数 $l,r\in [1,n]$,如果 $l>r$,则交换 $l,r$。求 $a_l\sim a_r$ 中不同数字个数的期望。 - $1\le n\le 10^6$,$1\le a_i\le 10^6$。答案被认为是正确的当且仅当 $\min\left(|x-y|,\dfrac{|x-y|}{x}\right)\le 10^{-4}$,其中 $x$ 是标准答案,$y$ 是您的答案。

题目描述

You are given an array $ a $ consisting of $ n $ positive integers. You pick two integer numbers $ l $ and $ r $ from $ 1 $ to $ n $ , inclusive (numbers are picked randomly, equiprobably and independently). If $ l>r $ , then you swap values of $ l $ and $ r $ . You have to calculate the expected value of the number of unique elements in segment of the array from index $ l $ to index $ r $ , inclusive ( $ 1 $ -indexed).

输入输出格式

输入格式


The first line contains one integer number $ n $ $ (1<=n<=10^{6}) $ . The second line contains $ n $ integer numbers $ a_{1} $ , $ a_{2} $ , ... $ a_{n} $ $ (1<=a_{i}<=10^{6}) $ — elements of the array.

输出格式


Print one number — the expected number of unique elements in chosen segment. Your answer will be considered correct if its absolute or relative error doesn't exceed $ 10^{-4} $ — formally, the answer is correct if ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF846F/1e3a6016727b2f57aeaab3dcbe84256bba31c89a.png), where $ x $ is jury's answer, and $ y $ is your answer.

输入输出样例

输入样例 #1

2
1 2

输出样例 #1

1.500000

输入样例 #2

2
2 2

输出样例 #2

1.000000

Input

题意翻译

- 给定长度为 $n$ 的序列 $a$。您要随机地选取两个数 $l,r\in [1,n]$,如果 $l>r$,则交换 $l,r$。求 $a_l\sim a_r$ 中不同数字个数的期望。 - $1\le n\le 10^6$,$1\le a_i\le 10^6$。答案被认为是正确的当且仅当 $\min\left(|x-y|,\dfrac{|x-y|}{x}\right)\le 10^{-4}$,其中 $x$ 是标准答案,$y$ 是您的答案。

加入题单

上一题 下一题 算法标签: