编写题解 3294: 蓝桥杯2024年第十五届决赛真题-数星星

解题思路:

题意转化：

求根节点的子节点数为y∈[L-1,R-1]，深度为1的子树集

假设一个结点子节点数为x，取其中的y个，就是排列组合Cxy

求Cxy要借助double数组

特殊情况：

子节点数为0，直接+n即可

子节点数为1，排列组合后要扣除重复的（n-1）

注意事项:

参考代码:

#include<bits/stdc++.h>

using namespace std;

const int N = 1e5+5;

const int mod = 1000000007;

int main(){

    int v[N]={0},n,i,x,y,L,R,j;

    long long sum=0; double d[N]; d[0]=1;

    cin>>n;

    for(i=1;i<n;i++){

        cin>>x>>y;

        v[x]++,v[y]++;

        d[i]=(i*d[i-1]);

    }

    d[i]=(i*d[i-1]);

    cin>>L>>R;

    for(i=L-1;i<=R-1;i++){

        if(i==0){ sum=(sum+n)%mod; continue;}

        for(j=1;j<=n;j++)

            if(v[j]>=i) sum=(long long)(sum+(d[v[j]]/d[v[j]-i])/d[i])%mod;

        if(i==1) sum=sum-n+1;

    }

    cout<<sum;

    return 0;

}