1 条题解

  • 2
    @ 2025-12-21 15:06:55

    详解不过多赘述,详见锣鼓题解

    阎帝代码(码风处理):

    #include<bits/stdc++.h>
    #define int long long
    using namespace std;
    const int N=110,P=998244353;
    int n,K;
    int f[N][N][N];//u为根,点数为i,不包括u的父亲与之相连的点数为j的连通块个数
    vector<int>G[N];
    int siz[N];
    int jc[N<<1],inv[N<<1];//i! i!的逆元
    int qpow(int n,int k=P-2/*意义不明*/)
    {
    	int res=1;
    	for(;k;k>>=1,n=n*n%P)if(k&1)res=res*n%P;
    	return res;
    }
    void init(int n)//初始化 
    {
    	jc[0]=inv[0]=1;
    	for(int i=1;i<=n;i++)jc[i]=jc[i-1]*i%P;
    	inv[n]=qpow(jc[n]);
    	for(int i=n-1;i>=1;i--)inv[i]=inv[i+1]*(i+1)%P;
    }
    int tmp[N][N];
    void dfs(int x,int xfa)
    {
    	f[x][1][0]=1;siz[x]=1;
    	for(int i:G[x])if(i!=xfa)
    	{
    		dfs(i,x);
    		memset(tmp,0,sizeof(tmp));
    		f[i][0][1]=1;
    		for(int j=0;j<=siz[x];j++)//加进来i这颗树 
    			for(int k=0;k<=siz[x];k++)
    				for(int s=0;s<=siz[i];s++)
    					for(int t=0;t<=siz[i];t++)
    						tmp[j+s][k+t]=(tmp[j+s][k+t]+f[x][j][k]*f[i][s][t]%P)%P;
    		siz[x]+=siz[i];
    		for(int j=0;j<=siz[x];j++)
    			for(int k=0;k<=siz[x];k++)
    				f[x][j][k]=tmp[j][k]; 
    	}
    }
    signed main()
    {
    	scanf("%lld%lld",&n,&K);
    	init(2*n);
    	for(int i=1,x,y;i<n;i++)
    	{
    		scanf("%lld%lld",&x,&y);
    		G[x].push_back(y);
    		G[y].push_back(x);
    	}
    	dfs(1,0);
    	int ans=0;
    	for(int i=1;i<=n;i++)
    		for(int j=K+1;j<=siz[i];j++)
    			for(int k=0;k<=siz[i];k++)
    			{
    				int rl=k+(i!=1);
    				ans=(ans+f[i][j][k]*jc[j]%P*jc[rl]%P*inv[j+rl]%P)%P;//计算概率,公式见题解
    			}
    	printf("%lld\n",ans);
    	return 0;
    }
    
    • 1

    信息

    ID
    205
    时间
    2000ms
    内存
    1024MiB
    难度
    7
    标签
    递交数
    31
    已通过
    8
    上传者