zcmimi's blog

查看原题

点击跳转

prufer序列应用模板

n个点的完全图有2^{n-2}棵生成树。

对于给定度数为d_{1\sim n}​的一棵无根树共有\dfrac{(n-2)!}{\prod_{i=1}^n(d_i-1)!}​种情况

全部全排列方案数除以每个点i的排列方案数(除去重复的)

i个点度数为d_i​,会在prufer序列中出现d_i-1次,全排列方案数为(d_i-1)!

由于答案很大10^17并且爆long long,过程中有除法,所以使用python3自带高精度非常方便

python3代码:

n=int(input())
if n==1: # 特判
    print(1 if int(input())==0 else 0),exit()
# 阶乘
f=[1]*(n+1)
for i in range(1,n+1):f[i]=f[i-1]*i
# 计算
ans=f[n-2]
tot=0
for i in input().split():
    x=int(i)
    if x==0:print(0),exit()
    ans//=f[x-1]
    tot+=x-1
print(ans if tot==n-2 else 0) # 特判

为了避免除法,我们可以换一种统计方式,

依次把第i个点d_i-1个出现的数插入到prufer序列中,答案乘以方案数,空位数减去d_i-1

记得特判

c++代码

#include<bits/stdc++.h>
typedef long long ll;
const int N=155;
int n,s,d[N],C[N][N];
ll ans=1;
int main(){
    scanf("%d",&n);
    if(n==1)return scanf("%d",&s),puts(s==0?"1":"0"),0;
    for(int i=1;i<=n;++i)scanf("%d",d+i);
    C[0][0]=1;
    for(int i=1;i<=n;++i){
        C[i][0]=1;
        for(int j=1;j<=i;++j)C[i][j]=C[i-1][j]+C[i-1][j-1];
    }
    for(int i=1;i<=n;++i)ans*=C[n-2-s][d[i]-1],s+=d[i]-1;
    if(s!=n-2)puts("0");
    else printf("%lld\n",ans);
}
LG 2290 [HNOI2004]树的计数
comment评论
Search
search