#P18040. Partition AND/OR Aggregation
Partition AND/OR Aggregation
Partition AND/OR Aggregation
题目描述
给定长度为 的正整数序列 。将它划分为恰好 个连续、非空的子段 。
对于子段 ,定义
$$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},$$其中 表示按位与, 表示按位或。
将这 个分数按从大到小排序,排序后的第 个分数就是本次划分的得分。相等的分数也分别占据位置。
求所有划分中,得分的最大值和最小值。
输入格式
第一行三个整数 。
第二行 个整数 。
,。
输出格式
输出两行。若最大值和最小值分别为最简分数 、,第一行输出 ,第二行输出 。
必须满足 ,,。零应输出为 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