P1494 [国家集训队] 小 Z 的袜子
题目描述
作为一个生活散漫的人,小 Z 每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天,小 Z 再也无法忍受这恼人的找袜子过程,于是他决定听天由命……
具体来说,小 Z 把 n 只袜子从 1 到 n 编号,第 i 只袜子的颜色为 ci,颜色相同的袜子用相同的整数表示。
对于一次询问 [l,r],小 Z 会从编号在 l 到 r 之间的袜子中随机抽出两只不同的袜子,把这两只袜子穿在脚上。每个由两只袜子构成的无序组合被抽到的概率相同。小 Z 并不在意两只袜子是不是完整的一双,却很在意袜子的颜色,毕竟穿两只不同色的袜子会很尴尬。
设这次询问的区间长度为 len=r−l+1,区间内颜色为 x 的袜子共有 cntx 只。若从区间中抽出两只颜色相同的袜子,这两只袜子必属于同一种颜色 x,并且有 $\frac{\mathrm{cnt}_x\left(\mathrm{cnt}_x-1\right)}{2}$ 种不同的抽法;而从区间中抽出两只袜子的总方案数为 2len(len−1)。因此抽到两只同色袜子的概率为
$\frac{\sum_x \mathrm{cnt}_x\left(\mathrm{cnt}_x-1\right)}{\mathrm{len}\left(\mathrm{len}-1\right)}$
这个概率总可以写成一个最简分数 ba,其中 a 与 b 互质。你需要输出这个最简分数。特别地,如果区间内不足两只袜子(即 l=r),或者这个概率为 0,请输出 "0/1"。
输入格式
第一行输入两个整数 n,m(1≦n,m≦5×104) 代表袜子的数量和询问次数。
第二行输入 n 个整数 $c_1, c_2, \dots, c_n \left(1 \leqq c_i \leqq n\right)$ 代表每只袜子的颜色。
此后 m 行,第 t 行输入两个整数 $l_t, r_t \left(1 \leqq l_t \leqq r_t \leqq n\right)$ 代表第 t 次询问的区间。
输出格式
输出 m 行,第 t 行输出一个形如 at/bt 的最简分数,代表第 t 次询问中抽到两只同色袜子的概率,其中 at 与 bt 互质。若该概率为 0,或者 lt=rt,输出 "0/1"。
测试样例
6 4
1 2 3 3 3 2
2 6
1 3
3 5
1 6
2/5
0/1
1/1
4/15
样例 1 解释
袜子的颜色依次为 {1,2,3,3,3,2},共有 4 次询问。
∙第 1 次询问的区间为 [2,6],颜色依次为 {2,3,3,3,2}。颜色 2 有 2 只,颜色 3 有 3 只,同色方案数为 1+3=4,总方案数为 10,概率为 104=52;
∙第 2 次询问的区间为 [1,3],颜色依次为 {1,2,3},任意两只袜子都不同色,概率为 0,输出 "0/1";
∙第 3 次询问的区间为 [3,5],颜色依次为 {3,3,3},抽出的两只袜子必然同色,概率为 33=11;
∙第 4 次询问的区间为 [1,6],颜色依次为 {1,2,3,3,3,2}。颜色 2 有 2 只,颜色 3 有 3 只,同色方案数为 1+3=4,总方案数为 15,概率为 154。
6 4
1 2 2 3 3 3
1 2
2 6
4 6
1 1
0/1
2/5
1/1
0/1
样例 2 解释
袜子的颜色依次为 {1,2,2,3,3,3},共有 4 次询问。
∙第 1 次询问的区间为 [1,2],颜色依次为 {1,2},两只袜子不同色,概率为 0,输出 "0/1";
∙第 2 次询问的区间为 [2,6],颜色依次为 {2,2,3,3,3},同色方案数为 1+3=4,总方案数为 10,概率为 104=52;
∙第 3 次询问的区间为 [4,6],颜色依次为 {3,3,3},概率为 11;
∙第 4 次询问的区间为 [1,1],区间内只有一只袜子,无法抽出两只,输出 "0/1"。
提示
对于 30% 的数据,1≦n,m≦5×103。
对于 60% 的数据,1≦n,m≦2.5×104。
对于 100% 的数据,1≦n,m≦5×104,1≦ci≦n,1≦lt≦rt≦n。