CF2176D Fibonacci Paths 题解

· · 题解

考虑 dp。

定义边 (u,v) 的边权为 a_u+a_v。显然在斐波那契路径中，边权是单调不降的。因此，为了维护转移顺序，我们先将边按权值升序排序。

考虑做一个朴素的 dp。定义 dp_i 为以边 i=(v,w) 为终点的斐波那契路径个数。转移时，先枚举边 i=(v,w)，再枚举满足 a_w=a_u+a_v 的边 j=(u,v)，则有 dp_i=\sum dp_j。这样做是 O(m^2) 的，不可接受。

考虑优化。为了快速计算 \sum dp_j 的值，我们将权值设计到状态中。定义 dp_{v,k} 为以边 i=(v,w) 为终点的斐波那契路径个数，其中 w 的权值为 k。转移时，枚举边 i=(u,v)，则转移方程为：

dp_{v,a_u+a_v} \leftarrow dp_{v,a_u+a_v}+dp_{u,a_v}+1

如何理解这个方程？我们发现，dp_{u,a_v} 为从边 i=(u,v) 走过来的方案数，1 为边 (v,w) 单独组成一条路径的方案数，因此，它们加起来即为以边 (v,w) 为终点的总方案数。

答案即为 dp_{u,a_v}+1 的和。

时间复杂度 O(m \log m)。

:::success[代码]

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 2e5 + 10;
const int MOD = 998244353;
ll a[MAXN];
struct Edge{
    int u, v;
}e[MAXN];
bool cmp(Edge x, Edge y){
    return a[x.u] + a[x.v] < a[y.u] + a[y.v];
}
map <ll, int> dp[MAXN];
void solve(){
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++){
        cin >> a[i];
    }
    for (int i = 1; i <= m; i++){
        cin >> e[i].u >> e[i].v;
    }
    sort(e + 1, e + m + 1, cmp);
    for (int i = 1; i <= n; i++){
        dp[i].clear();
    }
    int ans = 0;
    for (int i = 1; i <= m; i++){
        int u = e[i].u, v = e[i].v;
        ans = (ans + dp[u][a[v]] + 1) % MOD;
        dp[v][a[u] + a[v]] = (dp[v][a[u] + a[v]] + dp[u][a[v]] + 1) % MOD;
    }
    cout << ans << endl;
    return;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--){
        solve();
    }
    return 0;
}

:::