假设当前节点now的子树大小为size
now的方案数是他的所有儿子内部如何分配的方案数相乘得到的 这个可以递归计算
不过对于那么多儿子之间 他们分配走的标号可能是不同的 比如now将把2,3,4,5分配给他的子树，那有可能是2,3；4,5 也有可能是2,4; 3,5这样分
所以还得套个组合数 C(size,size') size需要一直减下去
#include<bits/stdc++.h> #define N 100005 #define ll long long using namespace std; const ll mod=998244353; template<class T> inline void read(T &x) { x=0; int f=1; static char ch=getchar(); while((!isdigit(ch))&&ch!='-') ch=getchar(); if(ch=='-') f=-1; while(isdigit(ch)) x=x*10+ch-'0',ch=getchar(); x*=f; } struct Node { int to,next; }edge[2*N]; int n,first[N],tot; inline void addedge(int x,int y) { tot++; edge[tot].to=y; edge[tot].next=first[x]; first[x]=tot; } int father[N]; ll size[N]; void dfs1(int now,int fa) { father[now]=fa; size[now]=1; for(int u=first[now];u;u=edge[u].next) { int vis=edge[u].to; if(vis==fa) continue; dfs1(vis,now); size[now]+=size[vis]; } } ll fac[N],inv[N]; inline int qpow(ll x,ll y) { ll base=x,ans=1; while(y) { if(y&1) ans=ans*base%mod; base=base*base%mod; y>>=1; } return ans; } void init(int n) { fac[0]=1; for(ll i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod; inv[n]=qpow(fac[n],mod-2); for(ll i=n-1;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod; //逆元可倒推 } inline ll C(int m,int n) { return fac[m]*inv[m-n]%mod*inv[n]%mod; } int dfs2(int now) { ll temp=size[now]-1; ll ans=1; for(int u=first[now];u;u=edge[u].next) { int vis=edge[u].to; if(vis==father[now]) continue; ans=ans*C(temp,size[vis])%mod*dfs2(vis)%mod; temp-=size[vis]; } return ans; } int main() { read(n); for(int i=1,x,y;i<n;i++) { read(x),read(y); addedge(x,y),addedge(y,x); } init(n); dfs1(1,0); cout<<dfs2(1)<<endl; return 0; }转载于:https://www.cnblogs.com/Patrickpwq/articles/9877187.html
相关资源：各显卡算力对照表！