A16817 · Fibonacci Paths

题目描述

给定一个包含 $n$ 个顶点和 $m$ 条边的有向图。每个顶点 $v$ 上对应一个正整数 $a_v$。请你统计所有由至少两个顶点组成的不同简单路径，使得沿路径经过顶点的数字序列构成一个广义斐波那契数列。 在本题中，若数列 $x_0, x_1, \ldots, x_k$ 满足以下条件，则称其为广义斐波那契数列： - $x_0, x_1$ 为任意自然数。 - 对所有 $2 \le i \le k$，都有 $x_i = x_{i-2} + x_{i-1}$。 注意，广义斐波那契数列至少包含两个数字。 由于答案可能很大，输出其对 $998\,244\,353$ 取模的结果。 一个简单路径指在有向图中按顺序经过顶点 $v_1, v_2, \ldots, v_k$，且所有顶点至多出现一次，并且对于所有 $i < k$，存在从 $v_i$ 到 $v_{i+1}$ 的有向边。

输入格式

每个测试点包含若干组测试数据。第一行为测试数据组数 $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 \ne v$），表示一条从 $v$ 到 $u$ 的有向边。保证不存在重边。 保证所有测试数据中 $n$ 的总和与 $m$ 的总和不超过 $2 \times 10^5$。

输出格式

对于每组测试数据，输出广义斐波那契路径的数量，对 $998\,244\,353$ 取模。

输入输出样例

输入 #1

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

输出 #1

A16817 | Fibonacci Paths

题目描述

输入格式

输出格式

输入输出样例

A16817 | $Fibonacci Paths$