题解 | #冥古之潮#

计数题

很容易想到求一下所有点到的距离

然后问题就转化成了, 在个筐中选个东西, 框里面的东西的编号不同, 编号不同代表不同的方案数的问题

可以用类似背包问题的方法去考虑, 定义状态表示考虑前个框并且已经选了个的方案数

预处理这个 表即可

#include <bits/stdc++.h>

#define x first
#define y second
#define all(x) x.begin(), x.end()
#define vec1(T, name, n, val) vector<T> name(n, val)
#define vec2(T, name, n, m, val) vector<vector<T>> name(n, vector<T>(m, val))
#define vec3(T, name, n, m, k, val) vector<vector<vector<T>>> name(n, vector<vector<T>>(m, vector<T>(k, val)))
#define vec4(T, name, n, m, k, p, val) vector<vector<vector<vector<T>>>> name((n), vector<vector<vector<T>>>((m), vector<vector<T>>((k), vector<T>((p), (val)))))

using namespace std;
using i128 = __int128;
using u128 = unsigned __int128;
using LL = long long;
using LD = long double;
using ULL = unsigned long long;
using PII = pair<int, int>;
using PLL = pair<LL, LL>;
using PLD = pair<LD, LD>;

const int N = 1e6 + 10, MOD = 1e9 + 7;
const int INF = 1e9;
const LL LL_INF = 1e18;
const LD EPS = 1e-8;
const int dx4[] = {-1, 0, 1, 0}, dy4[] = {0, 1, 0, -1};
const int dx8[] = {-1, -1, -1, 0, 0, 1, 1, 1}, dy8[] = {-1, 0, 1, -1, 1, -1, 0, 1};

istream& operator>>(istream& is, i128& val) {
    string str;
    is >> str;
    val = 0;
    bool flag = false;
    if (str[0] == '-') flag = true, str = str.substr(1);
    for (char& c : str) val = val * 10 + c - '0';
    if (flag) val = -val;
    return is;
}

ostream& operator<<(ostream& os, i128 val) {
    if (val < 0) os << "-", val = -val;
    if (val > 9) os << val / 10;
    os << static_cast<char>(val % 10 + '0');
    return os;
}

bool cmp(LD a, LD b) {
    if (fabs(a - b) < EPS) return 1;
    return 0;
}
LL fact[N], infact[N];

LL qpow(LL a, LL b) {
    LL ans = 1;
    a %= MOD;
    while (b) {
        if (b & 1) ans = ans * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return ans;
}

void init() {
    fact[0] = 1, infact[0] = 1;
    for (LL i = 1; i < N; ++i) {
        fact[i] = fact[i - 1] * i % MOD;
        infact[i] = qpow(fact[i], MOD - 2) % MOD;
    }
}

LL C(LL a, LL b) {
    if (a < b || b < 0) return 0;
    return fact[a] % MOD * infact[b] % MOD * infact[a - b] % MOD;
}

void solve() {
    int n, m, q, x;
    cin >> n >> m >> q >> x;
    vector<vector<int>> g(n + 1);
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    vector<int> d(n + 1, -1);
    d[x] = 0;
    queue<int> qu;
    qu.push(x);
    map<int, int> mp;
    while (qu.size()) {
        int u = qu.front();
        qu.pop();
        for (int v : g[u]) {
            if (d[v] == -1) {
                d[v] = d[u] + 1;
                mp[d[v]]++;
                qu.push(v);
            }
        }
    }

    vector<PII> tmp;
    tmp.assign(mp.begin(), mp.end());
    int sz = tmp.size();
    vec2(LL, f, sz + 1, 5000 + 1, 0);
    f[0][0] = 1;
    for (int i = 1; i <= sz; ++i) {
        for (int j = 0; j <= 5000; ++j) {
            if (!j) {
                f[i][j] = f[i - 1][j];
                continue;
            }
            f[i][j] = f[i - 1][j];
            f[i][j] = (f[i][j] + f[i - 1][j - 1] * tmp[i - 1].y) % MOD;
        }
    }

    while (q--) {
        int k;
        cin >> k;
        if (k > mp.size()) {
            cout << 0 << '\n';
            continue;
        }
        cout << f[sz][k] << '\n';
    }

/**/ #ifdef LOCAL
    cout << flush;
/**/ #endif
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    init();

    int T = 1;
    while (T--) solve();
    cout << fixed << setprecision(15);

    return 0;
}