[bzoj1005][HNOI2008]明明的烦恼-Prufer编码+高精度

Brief Description

给出标号为1到N的点,以及某些点最终的度数,允许在

任意两点间连线,可产生多少棵度数满足要求的树?

Algorithm Design

结论题.

首先可以参考这篇文章了解一下什么是Prufer编码:

然后, 根据排列组合和计数原理的相关知识, 设没有限制的节点数为\(m\), 答案就是

然后在分子和分母上分解因式, 把次数加加减减就好了.

Code

#include <algorithm>

#include <cctype>

#include <cstdio>

#include <cstring>

#define ll long long

const int maxn = 3000;

const ll mod = 1000000000000000;

inline int read() {

  int x = 0, f = 1;

  char ch = getchar();

  while (!isdigit(ch)) {

    if (ch == '-')

      f = -1;

    ch = getchar();

  }

  while (isdigit(ch)) {

    x = x * 10 + ch - '0';

    ch = getchar();

  }

  return x * f;

}

int n, m, tot, cnt;

ll d[maxn], num[maxn], prime[maxn], check[maxn], ans[maxn], l = 1;

void getprime() {

  for (int i = 2; i <= 1000; i++) {

    if (!check[i])

      prime[cnt++] = i;

    for (int j = 0; j < cnt; j++) {

      if (i * prime[j] > 1000)

        break;

      check[i * prime[j]] = 1;

      if (i % prime[j] == 0)

        break;

    }

  }

}

void solve(int a, int f) {

  for (int k = 1; k <= a; k++) {

    int x = k;

    for (int i = 0; i < cnt; i++) {

      if (x <= 1)

        break;

      while (x % prime[i] == 0) {

        num[i] += f;

        x /= prime[i];

      }

    }

  }

}

void mul(int x) {

  for (int i = 1; i <= l; i++)

    ans[i] *= x;

  for (int i = 1; i <= l; i++) {

    ans[i + 1] += ans[i] / mod;

    ans[i] %= mod;

  }

  while (ans[l + 1]) {

    l++;

    ans[l + 1] += ans[l] / mod;

    ans[l] %= mod;

  }

}

void print() {

  for (int i = l; i; i--)

    if (i == l)

      printf("%lld", ans[i]);

    else

      printf("%06lld", ans[i]);

}

int main() {

  getprime();

  ans[1] = 1;

  n = read();

  if (n == 1) {

    int x = read();

    if (!x || x == -1)

      printf("1");

    else

      printf("0");

    return 0;

  }

  for (int i = 1; i <= n; i++) {

    d[i] = read();

    if (!d[i]) {

      printf("0");

      return 0;

    }

    if (d[i] == -1)

      m++;

    else {

      d[i]--;

      tot += d[i];

    }

  }

  if (tot > n - 2) {

    printf("0");

    return 0;

  }

  solve(n - 2, 1);

  solve(n - 2 - tot, -1);

  for (int i = 1; i <= n; i++)

    solve(d[i], -1);

  for (int i = 0; i < cnt; i++)

    while (num[i]--)

      mul(prime[i]);

  for (int i = 1; i <= n - 2 - tot; i++)

    mul(m);

  print();

  return 0;

}