#P17759. 「RSOI-3H」数组划分 / partition
「RSOI-3H」数组划分 / partition
背景
题目来源:【HT-126-Div.2】核桃 CSP-S 组模拟赛
题目描述
给定一个长度为 的正整数数组 。
你需要将数组 划分为若干个连续的非空子段,且必须满足:对于划分出的每一个子段,其内部最大值与最小值的最大公约数严格大于 。
另有 组约束,每组约束由两个整数 组成,表示原数组中下标为 和下标为 的元素不能被划分在同一个连续子段内。
求所有合法的划分方案数,答案对 取模。
输入格式
第一行包含两个非负整数 。
第二行包含 个正整数,表示数组 。
接下来 行,每行包含两个整数 ,表示一组不能在同一子段的下标约束。
输出格式
输出一行一个整数,表示合法的划分方案数对 取模后的结果。
4 0
2 4 3 6
7
5 1
2 2 2 2 2
2 4
12
提示
【样例解释 #1】
本样例无约束条件,所有合法的划分方案如下:
[2], [4], [3], [6]:各子段 分别为 2, 4, 3, 6,均合法。[2, 4], [3], [6]:[2, 4]最大值为 4,最小值为 2,,合法。[2], [4], [3, 6]:[3, 6]最大值为 6,最小值为 3,,合法。[2, 4], [3, 6]:合法。[2], [4, 3, 6]:[4, 3, 6]最大值为 6,最小值为 3,,合法。[2, 4, 3], [6]:[2, 4, 3]最大值为 4,最小值为 2,,合法。[2, 4, 3, 6]:整个数组最大值为 6,最小值为 2,,合法。
注意,[2], [4, 3], [6] 是非法的,因为 [4, 3] 的 。共计 7 种合法方案。
【数据范围】
本题采用捆绑测试。
对于 的数据,满足 ,,。
| Subtask | 特殊性质 | 分值 | ||
|---|---|---|---|---|
| 1 | 无 | |||
| 2 | ^ | |||
| 3 | ||||
| 4 | 所有的 均相等 | |||
| 5 | ^ | ^ | 所有的 均为质数 | |
| 6 | 无 | |||
| 7 | ^ | |||