Complete Tree Labeling

题目描述

分析:如果已知深度为d – 1的k叉树(以下代称T(d-1))一共有a(k, d – 1)种标号法,那么深度为d的k叉树(以下代称T(d))的a(k, d)如何计算?
对T(d)来说,除去根节点,恰好有k棵T(d-1)子树,考虑到根节点的标号必须是1,则T(d)的标号方法可以分两步进行:首先把2~n的标号分成k组,每组m个,共有
x = C(km, m)*C((km – m), m)*C((km – 2m), m)*…*C((km – (k – 1)m), m) = (k*m)!/((m!)^k)
种方法;对于每种分组方法,又有a(k, d – 1)^k种组合;因此
a(k, d) = (a(k, d – 1)^k)*(k*m)!/((m!)^k)
其中m=(k^d – 1)/(k – 1),a(k, 0) = 1。但要注意:
1)k = 1时,树退化为链表,无论d如何a(1, d)都是1。
2)注意到其实
m(d) = 1 + k + k^2 + … + k^(d – 1)
因此可以用递推的方式高效计算m(0)到m(n)的值。
3)注意到k*d<=21,当k=4,d=5时m的数量级在1000,但1000!已远超64位整数的能力范围,如不能设法简化a(k, d)的算式,避免(m!)^k这样的大数运算,就只有……使用自定义的大数运算了(很不幸地,C/C++的标准库都没有大整数运算函数,因此为解题不得不手工编写 bigint.h(但是Java标准库却有BigInt类可用,因此此题用Java可以很方便地求解)。

#include <iostream>
#include <vector>
#include <cstring>
#include "bigint.h"

using namespace std;

BigInt results[22][22];

int m[22][22];

void init() {
  int k, d;
  for (d = 0; d < 22; d++) {
    results[1][d] = 1;
  }
  for (k = 2; k < 22; k++) {
    results[k][0] = 1;
  }
  memset(m, 0, sizeof(m));
}

int compute_m(int k, int d) {
  int r = m[k][d];
  if (!r && d) {
    r = k * compute_m(k, d - 1) + 1;
    m[k][d] = r;
  }
  return r;
}

BigInt compute(int k, int d) {
  BigInt r = results[k][d];
  if (r.zero()) {
    BigInt smaller = compute(k, d - 1);
    int m = compute_m(k, d);
    //x = (k * m)! / ((m!) ^ k);
    //r = (smaller ^ k) * x;
    BigInt x = BigInt::fact(m * k) / BigInt::pow(BigInt::fact(m), k);
    r = BigInt::pow(smaller, k) * x;
    results[k][d] = r;
  }
  return r;
}

int main() {
  init();
  int k, d;
  while (cin >> k >> d) {
    cout << compute(k, d) << endl;
  }
  return 0;
}

《Complete Tree Labeling》有1个想法

  1. Pingback: 目录 | 狂童

发表评论

电子邮件地址不会被公开。 必填项已用*标注

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>