gym-102956



 2021.02.21 17:16  2023.09.01 18:14  ACM  Prufer序列  组合计数  树 󰈭 672字

[题目链接](2020-2021 Winter Petrozavodsk Camp, Belarusian SU Contest (XXI Open Cup, Grand Prix of Belarus))

G. prufer && 树上组合计数问题

当n为奇数时显然为0.

当n为偶数时，首先将n个点分组成两个两个，有$\frac {n!}{(\frac n 2)!2^{\frac n2}}$种（先排列起来，然后除去n/2组交换顺序的情况，再除去组内的两种组合情况）

上述分式化简结果为$(n-1)!!$

~~没有想到怎么样直接地化简得来，只能用数学归纳法证明结论的正确性。~~

另一方面，由凯莱公式可以知道，n/2个节点的带标号完全图生成树有$(\frac n 2) ^ {\frac n 2 -2}$个

而这n/2个"节点"都是由一对真实的单点组成的，所以n/2树上的任意一条边，都是由2个点对组合构成的，共有4种可能的结果。

那么当n/2个点对已经被指定后，该树可能的形态就有$(\frac n 2) ^ {\frac n 2 -2} * 4^{\frac n 2 -1}$种

所以综上考虑，总的方案数就是$(n-1)!! * (\frac n 2) ^ {\frac n 2 -2} * 4^{\frac n 2 -1}$

 1const int maxn = 5e6 + 10;
 2int n;
 3int par[maxn], prufer[maxn], du[maxn];
 4
 5void encode(){
 6    int ptr = -1;
 7    for(int i = 1; i <= n; i++) if(ptr == -1 && du[i] == 1) ptr = i;
 8    
 9    int leaf = ptr;
10    for(int i = 0; i < n - 2; i++){
11        int next = prufer[i] = par[leaf];
12        if(--du[next] == 1 && next < ptr) leaf = next;
13        else{
14            ptr++;
15            while(du[ptr] != 1) ptr++;
16            leaf = ptr;
17        }
18    }
19}
20
21void rebuild(){
22    int ptr = 0;
23    while(du[ptr] != 1) ptr++;
24    
25    int leaf = ptr;
26    for(int i = 0; i < n - 2; i++){
27        int next = par[leaf] = prufer[i];
28        if(--du[next] == 1 && next < ptr) leaf = next;
29        else{
30            ptr++;
31            while(du[ptr] != 1) ptr++;
32            leaf = ptr;
33        }
34    }
35    par[leaf] = n;
36}
37
38void hsh(int a[maxn], int n){
39    ll ans = 0;
40    for(int i = 0; i < n; i++) ans ^= (i + 1) * 1ll * a[i];
41    printf("%lld\n", ans);
42}
43
44int main(){
45//    Fastin;
46    
47    int op;
48    scanf("%d %d", &n, &op);
49    if(op == 1){
50        for(int i = 1; i <= n - 1; i++){
51            scanf("%d", par + i);
52            du[par[i]]++; du[i]++;
53        }
54        encode();
55        hsh(prufer, n - 2);
56    }
57    else{
58        for(int i = 1; i <= n; i++) du[i] = 1;
59        for(int i = 0; i < n - 2; i++){
60            scanf("%d", prufer + i);
61            du[prufer[i]]++;
62        }
63        rebuild();
64        hsh(par + 1, n - 1);
65    }
66    return 0;
67}