NOIP模拟赛：排列树与组合数学深入解析

做这道题的时候真的难受，属于知道他考你什么但就是不知道怎么做，令人蛋疼啊。。。。。

题意大概就是求拓扑排序的方案数，然额太菜了写不出来。。。。。。

对于树上每个节点，记录他的size，对于根节点，他的编号一定是1，因为子节点的编号一定比父节点大，就类似于一种偏序关系，考虑每个节点分配的编号数就是他的size，所以用组合数学求出方案数，每个子树的方案就是这个式子：

其中k表示已经考虑的子节点。最后统计f[1]即可。

#include
using namespace std;
typedef long long LL;
const LL MAXN=1e5+50;
const LL MAXM=2e5+10;
const LL MOD=998244353;
LL n,cnt;
LL head[MAXN],siz[MAXN];
LL nxt[MAXM],to[MAXM];
LL contri[MAXN];
LL jc[MAXN],incjc[MAXN];
LL Read(){
LL i=0,f=1;
char c;
for(c=getchar();(c>'9'||c<'0')&&c!='-';c=getchar());
if(c=='-')
f=-1,c=getchar();
for(;c>='0'&&c<='9';c=getchar())
i=(i<<3)+(i<<1)+c-'0';
return i*f;
}
void add(LL x,LL y){
nxt[cnt]=head[x];
head[x]=cnt;
to[cnt]=y;
cnt++;
}
LL mul(LL x,LL y){
return x*y%MOD;
}
LL ksm(LL a,LL b,LL c){
LL ans=1;
while(b){
if(b&1)
ans=mul(ans,a);
b>>=1;
a=mul(a,a);
}
return ans;
}
void pre(){
jc[0]=1;
for(LL i=1;i<=MAXN;++i)
jc[i]=mul(jc[i-1],i);
incjc[MAXN-1]=ksm(jc[MAXN-1],MOD-2,MOD);
for(LL i=MAXN-2;i>=0;--i)
incjc[i]=mul(incjc[i+1],(i+1));
}
LL C(LL x,LL y){
return mul(jc[x],mul(incjc[y],incjc[x-y]));
}
void dfs(LL u,LL f){
contri[u]=1;
for(LL i=head[u];i!=-1;i=nxt[i]){
LL v=to[i];
if(v==f)
continue;
dfs(v,u);
contri[u]=mul(contri[u],contri[v]);
contri[u]=mul(contri[u],C(siz[u]+siz[v],siz[u]));
siz[u]+=siz[v];
}
siz[u]++;
}
int main(){
memset(head,-1,sizeof(head));
pre();
n=Read();
for(LL i=1;i LL x=Read(),y=Read();
add(x,y),add(y,x);
}
dfs(1,-1);
cout< return 0;
}