LG#P1494. 小 Z 的袜子

小 Z 的袜子

P1494 [国家集训队] 小 Z 的袜子

题目描述

\hspace{15pt}作为一个生活散漫的人,小 Z 每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天,小 Z 再也无法忍受这恼人的找袜子过程,于是他决定听天由命……

\hspace{15pt}具体来说,小 Z 把 nn 只袜子从 11 到 nn 编号,第 ii 只袜子的颜色为 cic_i,颜色相同的袜子用相同的整数表示。

\hspace{15pt}对于一次询问 [l,r][l, r],小 Z 会从编号在 ll 到 rr 之间的袜子中随机抽出两只不同的袜子,把这两只袜子穿在脚上。每个由两只袜子构成的无序组合被抽到的概率相同。小 Z 并不在意两只袜子是不是完整的一双,却很在意袜子的颜色,毕竟穿两只不同色的袜子会很尴尬。

\hspace{15pt}设这次询问的区间长度为 len=r−l+1\mathrm{len} = r - l + 1,区间内颜色为 xx 的袜子共有 cntx\mathrm{cnt}_x 只。若从区间中抽出两只颜色相同的袜子,这两只袜子必属于同一种颜色 xx,并且有 $\frac{\mathrm{cnt}_x\left(\mathrm{cnt}_x-1\right)}{2}$ 种不同的抽法;而从区间中抽出两只袜子的总方案数为 len(len−1)2\frac{\mathrm{len}\left(\mathrm{len}-1\right)}{2}。因此抽到两只同色袜子的概率为

$\frac{\sum_x \mathrm{cnt}_x\left(\mathrm{cnt}_x-1\right)}{\mathrm{len}\left(\mathrm{len}-1\right)}$

\hspace{15pt}这个概率总可以写成一个最简分数 ab\frac{a}{b},其中 aa 与 bb 互质。你需要输出这个最简分数。特别地,如果区间内不足两只袜子(即 l=rl = r),或者这个概率为 00,请输出 "0/1"\texttt{"0/1"}。

输入格式

\hspace{15pt}第一行输入两个整数 n,m(1≦n,m≦5×104)n, m \left(1 \leqq n, m \leqq 5 \times 10^4\right) 代表袜子的数量和询问次数。

\hspace{15pt}第二行输入 nn 个整数 $c_1, c_2, \dots, c_n \left(1 \leqq c_i \leqq n\right)$ 代表每只袜子的颜色。

\hspace{15pt}此后 mm 行,第 tt 行输入两个整数 $l_t, r_t \left(1 \leqq l_t \leqq r_t \leqq n\right)$ 代表第 tt 次询问的区间。

输出格式

\hspace{15pt}输出 mm 行,第 tt 行输出一个形如 at/bta_t/b_t 的最简分数,代表第 tt 次询问中抽到两只同色袜子的概率,其中 ata_t 与 btb_t 互质。若该概率为 00,或者 lt=rtl_t = r_t,输出 "0/1"\texttt{"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 解释

\hspace{15pt}袜子的颜色依次为 {1,2,3,3,3,2}\{1, 2, 3, 3, 3, 2\},共有 44 次询问。

∙ \hspace{23pt}\bullet\,第 11 次询问的区间为 [2,6][2, 6],颜色依次为 {2,3,3,3,2}\{2, 3, 3, 3, 2\}。颜色 22 有 22 只,颜色 33 有 33 只,同色方案数为 1+3=41 + 3 = 4,总方案数为 1010,概率为 410=25\frac{4}{10} = \frac{2}{5};

∙ \hspace{23pt}\bullet\,第 22 次询问的区间为 [1,3][1, 3],颜色依次为 {1,2,3}\{1, 2, 3\},任意两只袜子都不同色,概率为 00,输出 "0/1"\texttt{"0/1"};

∙ \hspace{23pt}\bullet\,第 33 次询问的区间为 [3,5][3, 5],颜色依次为 {3,3,3}\{3, 3, 3\},抽出的两只袜子必然同色,概率为 33=11\frac{3}{3} = \frac{1}{1};

∙ \hspace{23pt}\bullet\,第 44 次询问的区间为 [1,6][1, 6],颜色依次为 {1,2,3,3,3,2}\{1, 2, 3, 3, 3, 2\}。颜色 22 有 22 只,颜色 33 有 33 只,同色方案数为 1+3=41 + 3 = 4,总方案数为 1515,概率为 415\frac{4}{15}。

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 解释

\hspace{15pt}袜子的颜色依次为 {1,2,2,3,3,3}\{1, 2, 2, 3, 3, 3\},共有 44 次询问。

∙ \hspace{23pt}\bullet\,第 11 次询问的区间为 [1,2][1, 2],颜色依次为 {1,2}\{1, 2\},两只袜子不同色,概率为 00,输出 "0/1"\texttt{"0/1"};

∙ \hspace{23pt}\bullet\,第 22 次询问的区间为 [2,6][2, 6],颜色依次为 {2,2,3,3,3}\{2, 2, 3, 3, 3\},同色方案数为 1+3=41 + 3 = 4,总方案数为 1010,概率为 410=25\frac{4}{10} = \frac{2}{5};

∙ \hspace{23pt}\bullet\,第 33 次询问的区间为 [4,6][4, 6],颜色依次为 {3,3,3}\{3, 3, 3\},概率为 11\frac{1}{1};

∙ \hspace{23pt}\bullet\,第 44 次询问的区间为 [1,1][1, 1],区间内只有一只袜子,无法抽出两只,输出 "0/1"\texttt{"0/1"}。

提示

\hspace{15pt}对于 30%30\% 的数据,1≦n,m≦5×1031 \leqq n, m \leqq 5 \times 10^3。

\hspace{15pt}对于 60%60\% 的数据,1≦n,m≦2.5×1041 \leqq n, m \leqq 2.5 \times 10^4。

\hspace{15pt}对于 100%100\% 的数据,1≦n,m≦5×1041 \leqq n, m \leqq 5 \times 10^4,1≦ci≦n1 \leqq c_i \leqq n,1≦lt≦rt≦n1 \leqq l_t \leqq r_t \leqq n。