题解 | 冥古之潮 | bfs + dp 排列组合

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5, M = 5e3 + 5, mod =1e9 + 7;

int n, m, q, x;
vector<int> e[N];
bool vis[N];
int cnt[N];
int dp[M][M];

void bfs() {
    queue<int> Q;
    Q.push(x);
    vis[x]=true;
    int d = 0;
    while(Q.size()) {
        int t = Q.size();
        cnt[d] = t;
        while(t--) {
            int u = Q.front(); Q.pop();
            for(auto v: e[u]) {
                if(!vis[v]) {
                    vis[v] = true;
                    Q.push(v);
                }
            }
        }
        d++;
    }
}

void solve() {
    cin >> n >> m >> q >> x;
    for(int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    bfs();
    dp[0][0] = 1;
    // dp[i][j] 表示前 i 层的 数字 恰好选择 j 个的方法数量
    for(int i = 1; i < M; i++) {
        dp[i][0] = 1;
        for(int j = 1; j < M; j++) {
            dp[i][j] = (dp[i-1][j] + (long long)dp[i-1][j-1] * cnt[i]) % mod;
        }
    }
    while(q--) {
        int k;
        cin >> k;
        cout << dp[M-1][k] << "\n";
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    solve();
}
// 64 位输出请用 printf("%lld")