#P18040. Partition AND/OR Aggregation

Partition AND/OR Aggregation

Partition AND/OR Aggregation

题目描述

给定长度为 NN 的正整数序列 AA。将它划分为恰好 MM 个连续、非空的子段 B1,…,BMB_1,\ldots,B_M。

对于子段 B=(AL,…,AR)B=(A_L,\ldots,A_R),定义

$$S(B)=\frac{A_L\mathbin{\&}A_{L+1}\mathbin{\&}\cdots\mathbin{\&}A_R}{A_L\mathbin{|}A_{L+1}\mathbin{|}\cdots\mathbin{|}A_R},$$

其中 &\& 表示按位与,∣| 表示按位或。

将这 MM 个分数按从大到小排序,排序后的第 KK 个分数就是本次划分的得分。相等的分数也分别占据位置。

求所有划分中,得分的最大值和最小值。

输入格式

第一行三个整数 N,M,KN,M,K。

第二行 NN 个整数 A1,…,ANA_1,\ldots,A_N。

1≤K≤M≤N≤1051\le K\le M\le N\le10^5,1≤Ai<2301\le A_i<2^{30}。

输出格式

输出两行。若最大值和最小值分别为最简分数 p/qp/q、r/sr/s,第一行输出 p qp\ q,第二行输出 r sr\ s。

必须满足 p,r≥0p,r\ge0,q,s≥1q,s\ge1,gcd⁡(p,q)=gcd⁡(r,s)=1\gcd(p,q)=\gcd(r,s)=1。零应输出为 0 1。

样例 1

输入:

5 3 3
6 5 7 3 2

输出:

2 3
1 7

样例 2

输入:

5 1 1
3 1 4 1 5

输出:

0 1
0 1

样例 3

输入:

9 5 3
998 244 353 469 762 49 754 974 721

输出:

1 1
208 1023