prufer序列为无根树的一种数列。长度为 $n - 2$
prufer转无根树
将最小编号的叶子删去,prufer序列加入其父亲。重复至树只剩下两个节点。
无根树转prufer
取出prufer首元素,与待选点集中最小未出现在prufer序列中的点连边,并将该点在待选点集中删去,直至待选点集剩下两个节点,将这两个节点连边。待选点集初始为 $1$ ~ $n$。
一个节点在prufer序列中出现次数为该节点度数减一。
判断无解的情况:出现度数为 $0$ 的点,在prufer序列中出现次数超过 $n$ - $2$。
有解情况下,设 $cnt$ 为有度数要求的节点个数,$sum = \sum_{i = 1} ^{cnt}(d_i - 1)$。
那么答案为 $C_{n-2}^{sum} \times \dfrac{sum!}{\prod_{i=1}^{cnt}(d_i-1)!} \times (n-cnt)^{n-2-sum}$
化简得到$\dfrac{(n-2)!}{(n-sum-2)! \times \prod_{i=1}^{cnt}(d_i-1)!} \times (n-cnt)^{n-2-sum}$
#include <bits/stdc++.h> const int N = 1007; const int MOD = 10000; int num[N]; int prime[N], tol, d[N], c[N]; bool vis[N]; void init() { for (int i = 2; i < N; i++) { if (!vis[i]) prime[++tol] = i; for (int j = 1; j <= tol && i * prime[j] < N; j++) { vis[i * prime[j]] = 1; if (i % prime[j] == 0) break; } } } void add(int x, int o) { for (int i = 1; i <= tol; i++) { while (x % prime[i] == 0) c[i] += o, x /= prime[i]; } } int main() { init(); int n; scanf("%d", &n); bool flag = 0; int sum = 0, cnt = 0; for (int i = 1; i <= n; i++) { scanf("%d", d + i); if (!d[i] || d[i] > n - 1) flag = 1; if (d[i] != -1) sum += d[i] - 1, cnt++; } if (n == 1) { if (!d[1]) puts("1"); else puts("0"); return 0; } if (sum > n - 2 || flag) { puts("0"); return 0; } for (int i = n - 2 - sum + 1; i <= n - 2; i++) add(i, 1); for (int i = 1; i <= n; i++) { if (d[i] > -1) { for (int j = 2; j < d[i]; j++) add(j, -1); } } int len = 0; num[++len] = 1; for (int i = 1; i <= n - 2 - sum; i++) { for (int j = 1; j <= len; j++) num[j] *= n - cnt; for (int j = 1; j <= len; j++) { if (num[j] >= MOD) { num[j + 1] += num[j] / MOD; num[j] %= MOD; } } while (num[len + 1]) { num[len + 1] += num[len] / MOD; num[len] %= MOD; len++; } } for (int i = 1; i <= tol; i++) { while (c[i]) { for (int j = 1; j <= len; j++) num[j] *= prime[i]; for (int j = 1; j <= len; j++) { if (num[j] >= MOD) { num[j + 1] += num[j] / MOD; num[j] %= MOD; } } while (num[len + 1]) { num[len + 1] += num[len] / MOD; num[len] %= MOD; len++; } c[i]--; } } printf("%d", num[len]); for (int i = len - 1; i; i--) printf("%04d", num[i]); puts(""); return 0; }View Code