题解 | #冥古之潮#

1. 问题分析

本问题的核心在于无权联通图中基于距离约束的组合计数。我们需要从图中选取 个点组成集合 ，满足这些点到给定中心点 的最短路径长度（记为 ）呈严格升序且不为 。

1. 拓扑结构与距离：由于所有边长均为 1，且不存在重边与自环，点 到其他点的最短距离可以通过广度优先搜索（BFS）在 时间内精确计算。
2. 严格升序条件：。这一条件蕴含了两个关键信息：
   • 被选取的 个锚点必须分布在 个不同的距离层中。
   • 每一层只能选取 恰好一个 顶点。
3. 距离瓶颈：题目给定 。这意味着尽管 较大，但有效距离层的数量 是受限的。

2. 生成函数与动态规划

本题的本质是求取多项式系数。对于每一个距离 ，设其对应的顶点个数为 。如果我们在集合 中包含了距离为 的点，共有 种取法；如果不包含，则为 1 种取法（即不选）。

数学模型： 我们要计算的是以下生成函数的第 项系数： 展开后， 的系数即为选取 个距离互不相同的锚点的方案总数。

算法范式： 采用动态规划（DP）实现的组合递推。由于我们需要处理多个 的询问，计算出 展开后的前 个系数是最高效的策略。

3. 复杂度分析

• 时间复杂度：

  • BFS 预处理：遍历所有边和点，复杂度 。
  • 统计分布：统计 数组，复杂度 。
  • DP 计算：状态数为 ，状态转移为 ，总复杂度 。
  • 询问响应： 查表，总复杂度 。
  • 总计：。

• 空间复杂度：

  • 图存储：邻接表需 。
  • 距离与计数：。
  • DP 状态：使用滚动数组优化后，仅需 空间。
  • 总计：主要受 限制，约 体量。

4. 代码实现

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

static constexpr ll MOD = 1e9 + 7;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, q, x;
    cin >> n >> m >> q >> x;

    vector<vector<int>> adj(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    vector<int> dist(n + 1, -1);
    dist[x] = 0;
    queue<int> Q;
    Q.push(x);

    while (!Q.empty()) {
        int u = Q.front();
        Q.pop();
        for (int v : adj[u]) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                Q.push(v);
            }
        }
    }

    vector<int> cnt(5001, 0);
    for (int i = 1; i <= n; i++) {
        if (dist[i] == -1)
            continue;
        cnt[dist[i]]++;
    }

    vector<ll> dp(5001, 0);
    dp[0] = 1;
    for (int d = 1; d <= 5000; d++) {
        if (cnt[d] == 0)
            continue;
        for (int j = d; j >= 1; j--) {
            dp[j] = (dp[j] + dp[j - 1] * (ll)cnt[d]) % MOD;
        }
    }

    while (q--) {
        int k;
        cin >> k;
        cout << dp[k] << "\n";
    }
}