zcmimi's blog

arrow_backprufer序列共3篇文章

avatar
zcmimi
2020-09-28 14:07:23

prufer序列

这是一种将带标号的树用一个唯一的整数序列表示的方法.

很多与度数有关的树上计数问题,都可以用它以及它的性质来解决

avatar
zc
2020-09-29 12:40:52

查看原题

点击跳转

s_i为每个连通块点数

对每个连通块构建prufer序列

由于度数为边数两倍,\displaystyle \sum_{i=1}^k d_i=2k-2

对于给定d序列构造prufer序列的方案数为:

\displaystyle {k-2\choose d_1-1,d_2-1,\dots,d_k-1} = \frac{(k-2)!}{(d_1-1)!(d_2-1)!\cdot(d_k-1)!}

对于第i个连通块,它的连接方式有s_i^{d_i}种,对于给定d序列使图连通的方案数为:

\displaystyle {k-2\choose d_1-1,d_2-1,\dots,d_k-1}\cdot \prod_{i=1}^k s_i^{d_i}

枚举d序列:

\displaystyle \sum_{d_i\ge 1,\sum d_i=2k-2} {k-2\choose d_1-1,d_2-1,\dots,d_k-1}\cdot \prod_{i=1}^k s_i^{d_i}

换元,设e_i=d_i-1:

\displaystyle \sum_{e_i\ge 0,\sum e_i=k-2} {k-2\choose e_1,e_2,\dots,e_k}\cdot \prod_{i=1}^k s_i^{e_i+1}

根据多元二项式定理:

\displaystyle (x_1+x_2+\dots+x_m)^p=\sum_{c_i\ge 0,\sum c_i=p} {p\choose c_1,c_2,\dots,c_m}\cdot \prod_{i=1}^m x_i^{c_i}

原式化简得:

\displaystyle (s_1+s_2+\dots+s_k)^{k-2}\cdot \prod_{i=1}^k s_i

\displaystyle n^{k-2} \cdot \prod_{i=1}^k s_i

avatar
zc
2020-09-28 20:30:29

查看原题

点击跳转

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++代码

1/1
Search
search