33OJ
登录 注册

#P17759. 「RSOI-3H」数组划分 / partition

「RSOI-3H」数组划分 / partition

背景

题目来源:【HT-126-Div.2】核桃 CSP-S 组模拟赛

题目描述

给定一个长度为 nn 的正整数数组 AA。

你需要将数组 AA 划分为若干个连续的非空子段,且必须满足:对于划分出的每一个子段,其内部最大值与最小值的最大公约数严格大于 11。

另有 kk 组约束,每组约束由两个整数 (u,v)(u, v) 组成,表示原数组中下标为 uu 和下标为 vv 的元素不能被划分在同一个连续子段内。

求所有合法的划分方案数,答案对 998244353998244353 取模。

输入格式

第一行包含两个非负整数 n,kn, k。

第二行包含 nn 个正整数,表示数组 A1,A2,…,AnA_1, A_2, \dots, A_n。

接下来 kk 行,每行包含两个整数 u,vu, v,表示一组不能在同一子段的下标约束。

输出格式

输出一行一个整数,表示合法的划分方案数对 998244353998244353 取模后的结果。

4 0
2 4 3 6
7
5 1
2 2 2 2 2
2 4
12

提示

【样例解释 #1】

本样例无约束条件,所有合法的划分方案如下:

  • [2], [4], [3], [6]:各子段 gcd⁡\gcd 分别为 2, 4, 3, 6,均合法。
  • [2, 4], [3], [6]:[2, 4] 最大值为 4,最小值为 2,gcd⁡(4,2)=2>1\gcd(4, 2) = 2 > 1,合法。
  • [2], [4], [3, 6]:[3, 6] 最大值为 6,最小值为 3,gcd⁡(6,3)=3>1\gcd(6, 3) = 3 > 1,合法。
  • [2, 4], [3, 6]:合法。
  • [2], [4, 3, 6]:[4, 3, 6] 最大值为 6,最小值为 3,gcd⁡(6,3)=3>1\gcd(6, 3) = 3 > 1,合法。
  • [2, 4, 3], [6]:[2, 4, 3] 最大值为 4,最小值为 2,gcd⁡(4,2)=2>1\gcd(4, 2) = 2 > 1,合法。
  • [2, 4, 3, 6]:整个数组最大值为 6,最小值为 2,gcd⁡(6,2)=2>1\gcd(6, 2) = 2 > 1,合法。

注意,[2], [4, 3], [6] 是非法的,因为 [4, 3] 的 gcd⁡(4,3)=1\gcd(4, 3) = 1。共计 7 种合法方案。

【数据范围】

本题采用捆绑测试。

对于 100%100\% 的数据,满足 1≤n,Ai≤2×1051 \le n,A_i \le 2\times 10^5,0≤k≤2×1050 \le k \le 2\times 10^5,1≤u<v≤n1 \le u < v \le n。

Subtask n≤n\le k≤k\le 特殊性质 分值
1 500500 无 1010
2 50005000 ^ 1515
3 8×1048\times 10^4 1010
4 2×1052\times 10^5 所有的 AiA_i 均相等
5 ^ ^ 所有的 AiA_i 均为质数
6 00 无 1515
7 2×1052\times 10^5 ^ 3030