CF D. Fibonacci Paths
题目大意
给定一个 n 个顶点、m 条边的有向图，每个顶点 v 有一个正整数 a_v。求所有长度至少为 2 的简单路径的数目，使得路径上顶点值依次构成广义斐波那契数列，即从第三项起每一项等于前两项之和。答案对 998244353 取模。
数据范围：多组测试，总 n, m 不超过 2×10^5，a_i ≤ 10^18。
分析
广义斐波那契数列要求任意连续三项 x, y, z 满足 z = x + y。在路径中，若已知最后两个顶点值 a_u, a_v，则前一个顶点值必须为 a_u + a_v 才能继续向前延伸。因此，我们可以从后向前递推：对于每条边 (u, v)，它可以作为路径的最后一步，那么前面可能的路径必须是以某个顶点 w 结尾且满足 a_w = a_u + a_v，并且存在边 (w, v)。这种依赖关系提示我们按某种顺序处理边，使得在计算时所需信息已经得到。
一般思路
考虑动态规划，定义 dp[u][x] 表示以顶点 u 结尾，且路径中上一个顶点（即 u 的前驱）上的值为 x 的路径总数（这些路径长度至少为 2）。对于一条边 (u, v)，它可以作为路径的最后一步，有两种情况：
这条边本身构成一条长度为 2 的路径（即只包含 u, v），贡献 1。
若存在某个顶点 w 使得 a_w = a_u + a_v，并且有边 (w, v)，那么所有以 v 结尾且上一个值为 a_w 的路径（即 dp[v][a_w] 条）都可以接上 u 形成新路径，新路径以 u 结尾且上一个值为 a_v。
因此，对于每条边 (u, v)，令 sum = a_u + a_v，则新增路径数为 dp[v][sum] + 1，并将这些路径计入以 u 结尾且上一个值为 a_v 的贡献中：dp[u][a_v] 增加该值。同时，所有新增路径都计入答案。
为了保证计算时 dp[v][sum] 已经包含了所有可能的路径，需要按照边的 sum 值从大到小处理。因为若存在一条边 (w, v) 使得 a_w = sum，则它的 sum' = a_w + a_v = sum + a_v > sum，所以会先被处理，从而 dp[v][sum] 已被更新。
代码解释（对应给出的 AC 代码）
读入 n, m 和每个顶点的值 a_i。
将每条边存储为结构体 bi，包含起点 u、终点 v 以及两端点值之和 sum。
按 sum 降序排序所有边。
定义 dp 数组，每个 dp[u] 是一个 map，键为某个数值，值为以 u 结尾且前一个顶点值为该键的路径数。
初始化答案 ans = 0。
遍历排序后的每条边：
取出 u, v, sum。
计算 add = dp[v][sum] + 1，其中 dp[v][sum] 表示以 v 结尾且前一个值为 sum 的路径数（若不存在则为 0）。
将 add 累加到 dp[u][a_v] 上（取模）。
将 add 累加到答案 ans 上（取模）。
输出 ans。
注意：由于 a_i 可能很大，用 map 存储状态是合适的。每条边只处理一次，排序保证无后效性。
时间复杂度
排序边：O(m log m)
遍历边并更新 map：每条边一次 map 查找和插入，总 O(m log m)
总复杂度 O(m log m)，满足 m ≤ 2×10^5 的要求。
总结
本题巧妙地将斐波那契递推转化为图上的路径计数，利用按和排序保证无后效性，用 map 动态存储状态，简洁高效地解决了问题。
下面是代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define endl '\n'
#define fast ios::sync_with_stdio(0),cin.tie(0)
#define pll pair<ll,ll>const ll mod = 998244353;struct bi{ll u,v,sum;
};bool comp(bi a, bi b){return a.sum > b.sum;
}void solve(){ll n, m; cin >> n >> m;vector<ll> aa(n + 1);for(ll i = 1; i <= n; i++) cin >> aa[i];//顶点的数字vector<bi> bb(m + 1);for(ll i = 1; i <= m; i++){cin >> bb[i].u >> bb[i].v;//这里的u和v是单纯的顶点bb[i].sum = aa[bb[i].u] + aa[bb[i].v];}sort(bb.begin() + 1, bb.end(),comp);vector<map<ll,ll>> dp(n + 1);ll ans = 0;for(ll i = 1; i <= m; i++){ll u = bb[i].u, v = bb[i].v;ll fl = aa[u] + aa[v];ll add = (dp[v][fl] + 1);dp[u][aa[v]] = (dp[u][aa[v]] + add) % mod;ans = (ans + add) % mod;}cout<<ans<<endl;return;
}int main(){fast;ll t = 1; cin >> t;while(t--){solve();}return 0;
}