Prufer序.

Table of Contents

  1. Description
  2. Solution

Description

给定$n$个点在生成树中的度数限制或没有限制, 求方案数.

Solution

我们知道完全图的生成树方案数为$n^{n - 2}$, 对应的就是在长度为$n - 2$的Prufer序列中, 每个位置都有n种可能.

当加入度数限制后, 每个有度数限制的点会在Prufer序中出现$dgr - 1$次.

我们设$tot = \sum_{i}{dgr_i - 1} , \text{i with constraint}$.

那么第一个点的可选方案有$tot \choose dgr_1-1$种, 相应地, 第二个有$tot - (dgr_1 - 1) \choose dgr_2 - 1$种, 我们有:

$C_{tot}^{dgr_1 - 1} \times C_{tot - (dgr_1 - 1)}^{dgr_2 - 1} \times \ldots \times C_{tot - \ldots - {(dgr_{k-1}-1)}}^{dgr_k - 1} = \frac{tot!}{\prod{dgr - 1}}$

此外，对于剩余的$m$个点, 有方案数$m^{n - 2 - tot}$.

但本题没有取模, 而写高精除法太恶心了, 我们可以用约分统计素因子的方法, 将分母都约分掉, 然后实现一个高精乘单精就可以了.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

using namespace std;

const int maxn = 1005;

int n, dgr[maxn], tot, x;

int bigint[100000];
int len;

int pr[maxn], npr[maxn], cnt, mindiv[maxn];
int ind[maxn];
void euler() {
  for (int i = 2; i < maxn; ++i) {
    if (!npr[i]) pr[++cnt] = i, mindiv[i] = cnt;
    for (int j = 1; j <= cnt && i * pr[j] < maxn; ++j) {
      npr[i * pr[j]] = 1;
      mindiv[i * pr[j]] = j;
      if (!(i % pr[j])) break;
    }
  }
}
void divi(int x, int v) {
  if (!x) return;
  while (x != 1) {
    ind[mindiv[x]] += v;
    x /= pr[mindiv[x]];
  }
}

int main() {
  euler();
  scanf("%d", &n);
  bigint[1] = 1; len = 1;
  for (int i = 1; i <= n - 2; ++i) divi(i, 1);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &dgr[i]);
    if (dgr[i] == -1) {
      x++; continue;
    }
    tot += dgr[i] - 1;
    if (dgr[i] >= n || (dgr[i] <= 0 && n != 1)) {
      puts("0"); return 0;
    }
    for (int j = 1; j <= dgr[i] - 1; ++j) divi(j, -1);
  }
  if (n - 2 - tot < 0) {
    puts("0");
    return 0;
  }
  for (int i = 1; i <= n - 2 - tot; ++i) divi(i, -1), divi(x, 1);
  for (int i = 1; i <= cnt; ++i) {
    while (ind[i] > 0) {
      --ind[i];
      for (int j = 1; j <= len; ++j) {
        bigint[j] *= pr[i];
      }
      for (int j = 1; j < len; ++j) {
        bigint[j + 1] += bigint[j] / 10;
        bigint[j] %= 10;
      }
      while (bigint[len] > 10) {
        bigint[len + 1] = bigint[len] / 10;
        bigint[len] %= 10;
        len++;
      }
    }
  }
  for (int i = len; i; --i)
    printf("%d", bigint[i]);
  return 0;
}