← 返回题目列表

Codeforces · 2176/D

D. 斐波那契路径

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

您将获得 有向图 由 $$$n$$$ 个顶点和 $$$m$$$ 个边组成。每个顶点$$$v$$$对应一个正数$$$a_v$$$。计算不同的数量 简单路径$$$^{\text{*}}$$$ 由至少两个顶点组成,使得沿着路径写在顶点处的数字序列形成广义斐波那契序列。

在这个问题中,我们将认为数字序列 $$$x_0, x_1, \ldots, x_k$$$ 形成广义斐波那契序列,如果:

  • $$$x_0, x_1$$$ 是任意自然数。
  • $$$x_i = x_{i - 2} + x_{i - 1}$$$ 对于所有 $$$2 \le i \le k$$$。

请注意,广义斐波那契数列至少由两个数字组成。

由于答案可能很大,因此输出它对 $$$998\,244\,353$$$ 取模。

$$$^{\text{*}}$$$有向图中的简单路径是顶点序列 $$$v_1, v_2, \ldots, v_k$$$,使得图中的每个顶点最多在路径中出现一次,并且对于所有 $$$i \lt 都有一条从 $$$v_i$$$ 到 $$$v_{i+1}$$$ 的有向边k$$$。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个数字 $$$n$$$, $$$m$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$1 \le m \le 2 \cdot 10^5$$$) - 分别是图中的顶点数和边数。

每个测试用例的第二行包含 $$$n$$$ 自然数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^{18}$$$) - 写在顶点处的数字。

接下来的 $$$m$$$ 行包含图形的边缘;每条边由两个自然数 $$$v, u$$$ ($$$1 \le v, u \le n$$$, $$$u \neq v$$$) 定义,表示从 $$$v$$$ 到 $$$u$$$ 的有向边。保证图中不存在重边。

保证所有测试用例的 $$$n$$$ 总和和 $$$m$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出形成广义斐波那契序列的路径数,以 $$$998\,244\,353$$$ 为模。

示例

输入
复制

4
4 4
3 4 3 6
1 2
1 3
2 4
3 4
4 6
1 1 1 2
1 2
2 3
3 1
1 4
2 4
3 4
8 11
2 4 2 6 8 10 18 26
1 2
2 3
3 1
4 3
2 4
3 5
5 6
4 6
6 7
7 5
5 8
2 2
10 10
1 2
2 1

输出
复制

5
9
24
2

注意

第一个测试用例示例说明(括号外面是顶点编号,里面是顶点写的数字):

在本例中,有 5 条广义斐波那契路径:($$$1, 2$$$)、($$$1, 3$$$)、($$$2, 4$$$)、($$$3, 4$$$)、($$$1,3,4$$$)。例如,对于路径 ($$$1,3,4$$$),沿该路径的顶点处写入的数字序列为:[$$$3,3,6$$$]。很容易看出,序列中的第三个数字是前两个数字的总和。

第二个测试用例示例说明:

在本例中,有 9 条广义斐波那契路径:($$$1, 2$$$)、($$$1, 4$$$)、($$$2, 3$$$)、($$$2, 4$$$)、($$$3, 1$$$)、($$$3, 4$$$)、($$$1, 2, 4$$$), ($$$2, 3, 4$$$), ($$$3, 1, 4$$$)。注意,对于路径($$$1, 2, 3$$$),沿着这条路径的顶点处写入的数字序列是:[$$$1,1,1$$$],并且它不是广义的斐波那契序列。