1 条题解
-
2
详解不过多赘述,详见锣鼓题解
阎帝代码(码风处理):
#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
- 上传者