文本解题报告

1、Another Counting Problem解题摘要题意简述定义严格 n 叉树为：所有非叶子节点都恰好有 n 个孩子节点的树。计算深度恰好为 d+1的严格 n 叉树的个数。其中，一个节点的各个孩子是有序的。（详见原题）初步分析本题是一个计数问题。由于树结构清晰的分为 d+1 层，很容易想到以层为阶段进行递推。很明显，除了根节点以外，树上每一层的节点数都是 n 的倍数。而这个倍数恰好就表示本层是由上一层的几个点扩展而来的。由于树上一个节点的各个孩子是需要考虑顺序的，那么如果两棵树第 k 层上的的节点总数相同，那么不论树的上半部什么形状，下面的的部分的变化总数是相同的。因此，可以从树的根部向下

2、进行递推。f(k,t)表示，深度为 k+1，且在第 k+1 层上有nt 个节点的严格 n 叉树的总数。这样，可以每次在当前的树下面加上一层，也就是在当前最底层节点中选一些分叉的点，进而推到下一层。具体一些说，在计算 f(k,t)时，需要枚举上一层的底层节点个数。如果上一层的底层节点有 ni 个，那么这种情况下本层有 nt 个节点的树的个数就是 f(k1,i)乘以从 ni 个节点中选出 t 个节点分叉的方案数。递推公式如下：1此处分析的时间空间复杂度都不包精度的复杂度。算法一算法二基本思路递推递推时间复杂度1O(d(nd)2)O(dlog2n)空间复杂度O(nd)O(1)其中初始条件是 f(1,

3、1)=1，而对于深度为 1 的情况则需要特殊处理，直接输出1。否则就统计 f(d,i)的总和（其中，1ind1），这就是最后的。时空分析一上面的递推方法，状态总数为 d nd。由于递推是一层一层进行的，因此可以使用滚动数组，这样，空间复杂度为 nd。时间方面，状态转移中，需要枚举一遍 i，并且需要计算组合数，这样的时间约为(nd)2。可以对组合数的计算进行一定的优化，完全可以从以前计算的组合数通过一次乘法一次除法得出。这样，不考虑高精度的时间，状态转移的时间复杂度约为 nd。再乘以状态总数，递推算法的时间复杂度约为O(d(nd)2)。当然，上面时间复杂度的分析是比较粗略的。本题中，由于保证了

4、nd 不超过 210，也就决定了 n 和 d 的取值范围有一定的限制。n 较大时，d 就很小，那么状态数就减少了，时间复杂度相应的降低。d 较大时，n 就不会很大，那么的位数就不会很高了，高精度计算的时间也会变少。因此，整个算法的时间效率是勉强可以接受的。深入分析但上面的算法毕竟不令人满意，须要寻找到更好的办法。在上一个算法中，我们是每次在当前的树底部加上一层，推倒新的状态。如果换一种思路，每次将 n 棵深度不超过 k 的树（其中至少有一棵深度恰好为 k）进行递推。为一棵深度为 k+1 的树，根据这种思路那么如果分别知道深度为 1 至 k 的严格 n 叉树的数量，如何计算深度为 k+1 的严格

5、 n叉树种类呢。问题的关键在于以根节点孩子为根的 n 棵子树中至少要有一棵深度为 k。如果正面计算，使用容斥原理，复杂度很高，计算也非常复杂，容易出错。利用“补集转化”，计算出深度不超过 k+1 的严格 n 叉树的总和，再减去深度不超过 k 的 n 叉树方案数。也就求出了深度为 k+1 的严格 n 叉树的数量。问题在于如何计算深度在 2 至 t 之间的严格 n 叉树的总数量。可以这样理解，选出n 棵深度在 1 至 t1 之间的严格 n 叉树，将它们排好顺序，然后让他们成为根节点的孩子，这样新的树也就增加了一层。定义 Ck 表示深度为 k+1 的严格 n 叉树总和，Sk 则表示深度在 1 到 k

6、+1 之间严格 n叉树的总数。递推计算深度在 2 至 t 之间的 n 叉树数量时，根节点的每一个孩子都可以选择St2 种树，也就是方案总数为 (St2)n 种。因此，棵一的到下面的递推公式：其中，C0=C1=S0=1，S1=2。最后的也就是 Cd。时空分析二上面的递推算法，明显的比第一种算法简单许多。各种状态只有 2d 个。而由于每次计算时，需要用到的值只有 3 个。因此，利用滚动技术，空间复杂度是 O(1)的。时间上，计算S 的n 次方可以采用反复平方法，那么每计算一次Ck 的值就只需要O(log2n)的时间，总的时间复杂度就是 O(dlog2n)，比上一种算法大大改进。到此，本题也就得到了很好的解决。小结解决本题的过程中，有两点很需要注意：（1）从算法