← 返回题目列表

Codeforces · 2183/E

E. LCM 是传奇计数大师

中文机器翻译题面 查看原题

给定一个长度为 $$$n$$$ 的序列 $$$a$$$ 和一个正整数 $$$m$$$。 $$$a$$$ 的每个元素都是 $$$[0, m]$$$ 范围内的整数。

考虑序列 $$$a$$$ 好 当且仅当以下两个条件成立:

  • $$$a_1 \lt a_2 \lt a_3 \lt \ldots \lt a_n$$$,并且
  • $$$\frac{1}{\operatorname{lcm}(a_1,a_2)}+\frac{1}{\operatorname{lcm}(a_2,a_3)}+\ldots+\frac{1}{\opera名称{lcm}(a_{n-1},a_n)}+\color{red}{\frac{1}{\operatorname{lcm}(a_n,a_1)}}\ge1$$$.$$$^{\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$$$ 为模。

示例

输入
复制

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

输出
复制

2
0
10
0
973702700

注意

在第一个测试用例中,有 $$$2$$$ 方法来替换零,以使序列变得良好:

  • $$$[1, 2, 3, 6]$$$:总和为 $$$\frac{1}{\operatorname{lcm}(1, 2)} + \frac{1}{\operatorname{lcm}(2, 3)} + \frac{1}{\operatorname{lcm}(3, 6)} + \frac{1}{\operatorname{lcm}(6, 1)} = \frac{1}{2} + \frac{1}{6} + \frac{1}{6} + \frac{1}{6} = 1$$$。
  • $$$[1, 2, 4, 6]$$$:总和为 $$$\frac{1}{\operatorname{lcm}(1, 2)} + \frac{1}{\operatorname{lcm}(2, 4)} + \frac{1}{\operatorname{lcm}(4, 6)} + \frac{1}{\operatorname{lcm}(6, 1)} = \frac{1}{2} + \frac{1}{4} + \frac{1}{12} + \frac{1}{6} = 1$$$。

在第二个测试用例中,初始序列是 $$$[2, 1]$$$。由于$$$2 \not \lt 1$$$,不满足严格递增条件,所以答案是$$$0$$$。

在第四个测试用例中,序列固定为 $$$[0, 0, 6, 0, 0]$$$,其中 $$$m=6$$$。第三个元素是$$$6$$$。由于序列必须严格递增,并且元素不能超过 $$$6$$$,因此我们需要 $$$6 \lt a_4 \lt a_5 \le 6$$$,这是不可能的。