题解 | #冥古之潮#

先从 x 做一遍 BFS，把每个点到 x 的距离分层统计成 c[d]；题目要求锚点距离严格递增，其实就是“每一层最多选 1 个点”。

所以答案就是从这些层里选 k 层、每层选一个点的方案数：做个 0/1 背包 DP，遇到第 d 层就把 f[j] 转移到 f[j+1] 并乘 c[d]，最后 f[k] 就是答案。

void solve(){
    int n,m,q,x;cin>>n>>m>>q>>x;
    vi h(n+1,-1),to(2*m),ne(2*m);
    int tt=0;
    for(int i=1;i<=m;++i){
        int u,v;cin>>u>>v;
        to[tt]=v;ne[tt]=h[u];h[u]=tt++;
        to[tt]=u;ne[tt]=h[v];h[v]=tt++;
    }
    vi ks(q);
    int km=0;
    for(int i=0;i<q;++i){
        cin>>ks[i];
        km=max(km,ks[i]);
    }
    km=min(km,5000);
    vi d(n+1,-1);
    queue<int> qu;
    d[x]=0;
    qu.push(x);
    int dm=0;
    while(!qu.empty()){
        int u=qu.front();qu.pop();
        for(int i=h[u];i!=-1;i=ne[i]){
            int v=to[i];
            if(d[v]!=-1)continue;
            d[v]=d[u]+1;
            dm=max(dm,d[v]);
            qu.push(v);
        }
    }
    vi c(dm+1,0);
    for(int i=1;i<=n;++i){
        if(i==x)continue;
        if(d[i]>=1)++c[d[i]];
    }
    vi f(km+1,0),g(km+1,0);
    f[0]=1;
    for(int i=1;i<=dm;++i){
        for(int j=0;j<=km;++j)g[j]=f[j];
        for(int j=1;j<=km;++j){
            g[j]=(g[j]+1LL*f[j-1]*c[i])%MOD;
        }
        f.swap(g);
    }
    for(int i=0;i<q;++i){
        int k=ks[i];
        if(k>km||k>dm)cout<<0<<endl;
        else cout<<f[k]<<endl;
    }
}