A16499 | $LCM is Legendary Counting Master$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

给定一个长度为 $n$ 的序列 $a$ 和一个正整数 $m$。序列 $a$ 的每个元素都是 $[0, m]$ 范围内的整数。 当且仅当以下两个条件都满足时，序列 $a$ 被认为是好的： - $a_1 < a_2 < a_3 < \ldots < a_n$； - $\frac{1}{\operatorname{lcm}(a_1,a_2)}+\frac{1}{\operatorname{lcm}(a_2,a_3)}+\ldots+ \frac{1}{\operatorname{lcm}(a_{n-1},a_n)}+{\color{red}\frac{1}{\operatorname{lcm}(a_n,a_1)}}\ge 1$。$^{\text{∗}}$ 你需要将序列 $a$ 中所有的零替换成 $[1, m]$ 范围内的整数。求有多少种不同的替换方式，使得最终的序列 $a$ 是好的。 请输出答案对 $998\,244\,353$ 取模。 $^{\text{∗}}$ 两个正整数的最小公倍数（$\operatorname{lcm}$）是同时被两个数整除的最小正整数。例如，$\operatorname{lcm}(2,3)=6,\, \operatorname{lcm}(4,6)=12$。

每组测试数据包含多组测试用例。第一行为测试用例数 $t$（$1 \le t \le 1000$）。接下来为每组测试用例的描述。 每个测试用例的第一行包含两个整数 $n$ 和 $m$（$2 \le n \le m \le 3000$）。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \le a_i \le m$）。 保证所有测试用例中 $m$ 的总和不超过 $3000$。

对于每个测试用例，输出一个整数——将序列补全并使其变为好序列的方案数，答案对 $998\,244\,353$ 取模。

输入 #1

5
4 6
1 0 0 6
2 2
2 1
5 24
0 0 4 0 0
5 6
0 0 6 0 0
20 2000
1 0 0 0 0 14 0 0 0 0 0 0 0 0 0 514 0 0 0 0

输出 #1

C++ 编辑器

输入

输出