题解 | 冥古之潮

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

const ll N = 1e6 + 5;
const ll MOD = 1e9 + 7; 

vector<vector<ll>> adj(N);
vector<ll> vis(N, -1);
ll c[5001]; 
ll dm = 0;

void bfs(ll x) {
    queue<ll> q;
    q.push(x);
    
    while (!q.empty()) {
        ll t = q.front();
        q.pop();
        
        for (auto it : adj[t]) {
            if (vis[it] == -1) {
                vis[it] = vis[t] + 1;
                dm = max(dm, vis[it]);
                c[vis[it]]++;
                q.push(it);
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    ll n, m, q, x;
    cin >> n >> m >> q >> x;
    
    for (ll i = 1; i <= m; i++) {
        ll u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    vis[x] = 0;
    bfs(x);
    
    // --- 01 背包 DP 部分 ---
    // f[j] 表示选 j 个锚点的方案数
    vector<ll> f(5001, 0); 
    f[0] = 1; // 初始化：选0个点的方案数为1
    
    // 遍历每一层（距离 d）
    for (ll d = 1; d <= dm; d++) {
        if (c[d] == 0) continue; // 这一层没节点，跳过
        
        // 01背包倒序遍历，防止重复选择同一层
        // k最大是5000，所以直接遍历到5000
        for (ll j = 5000; j >= 1; j--) {
            f[j] = (f[j] + f[j-1] * c[d]) % MOD;
        }
    }
    
    // 处理询问
    while (q--) {
        ll k;
        cin >> k;
        cout << f[k] << '\n';
    }
    
    return 0;
}