CFCF2176D.Fibonacci Paths

普及+/提高

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定一个包含 $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

说明/提示

第一个样例的解释（顶点编号在括号外，顶点上的数字在括号内）：

本例中共有 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]，这不是广义斐波那契数列。

首页