题解：P10912 [蓝桥杯 2024 国 B] 数星星

· · 题解

P10912 [蓝桥杯 2024 国 B] 数星星 题解

解题思路

首先，题目的意思就是数菊花图。

记一个节点的子节点个数为 s_i。

我们对于一个菊花，考虑它在树中的构造。显然如果已经确立了菊花的“根”，那么剩下的“花瓣”就一定是它的子节点或父节点。

那么对“花瓣”中有无父节点进行讨论，假设要选 x 个点：

  1. 有父节点。前置条件是至少也要选一个子节点，不然会有重复。那么个数就是 C_{s_i}^{x-2}。
  2. 无父节点。个数显然是 C_{s_i}^{x-1}。

显然一个点只会作为子节点一次，所以大力枚举即可。

组合数的话，模数是质数，预处理阶乘再用费马小定理即可。

AC 代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int N=1e5+50;
int n,l,r;
vector<int> G[N];
int siz[N];
void dfs(int p){
    for(auto j:G[p]){
        if(siz[j]) continue;
        siz[p]++;
        dfs(j);
    }
}
ll qpow(ll a,ll b){
    ll res=1LL;
    while(b){
        if(b&1) res=res*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return res;
}
ll jc[N];
ll C(int a,int b){
    if(b>a) return 0LL;
    return jc[a]*qpow(jc[a-b],mod-2)%mod*qpow(jc[b],mod-2)%mod;
}
int main(){
    scanf("%d",&n);
    jc[0]=jc[1]=1LL;
    for(ll i=2;i<=n;i++){
        jc[i]=jc[i-1]*i%mod;
    }
    for(int i=1;i<n;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1);
    scanf("%d%d",&l,&r);
    ll ans=0;
    for(int j=l-1;j<=min(r-1,siz[1]);j++){
        ans=(ans+C(siz[1],j))%mod;
    }
    for(int i=2;i<=n;i++){
        for(int j=l-1;j<=min(r-1,siz[i]+1);j++){
            if(j>=2) ans=(ans+C(siz[i],j-1))%mod;
            if(j<=siz[i]) ans=(ans+C(siz[i],j))%mod;
        }
    }
    printf("%lld",ans);
}
/*

*/