首先，叶子结点为\(k\)时，整个完整的二叉树存在\(2k – 1\)个节点。我们设置一个 DP 来进行计数。
考虑设置状态\(dp[i][j]\)为当前树已有\(i\)个节点，且有当前加入的节点到根的路径有\(j\)单位长度。考虑以下转移：
\[ dp[i + 1][j + 1] += dp[i][j] \\ dp[i + 1][j – 1] += dp[i][j] \]
向新的节点加入统计数据：多了一个叶子结点，要么向左走，加深当前的路径；要么补上最后一个向左走的右节点。
然后就可以写代码了。
这道题是一道好题。
我们可以直接暴力 DP，考虑状态\(dp[i][j]\)为\(i\)个\(1\)与\(j\)个\(-1\)的答案。那么，我们可以从少一个\(1\)的情况和少一个\(-1\)的情况进行转移：
真难。
简单来讲，题目要求满足\(\{x_i \mod m \in [1, m – 1]\}\)的\(k\)元组个数。我们可以先把\(x_i\)全部模上一个\(m\)，然后令\(A = \sum_{i = 1}^k (x_i \mod m)\)（注意，\(A\)并没有被整体取模，只是各项余数之和），可知\(A \mod m = n \mod m\)，且\(A\)的上限就是\(A = k(m – 1)\)（各项上限）。
我们做了这样一个设置之后，问题就可以转换为：对于每一个不同的\(A\)，满足\(A \mod m = n \mod m\)且\(A = \sum_{i = 1}^k (x_i \mod m), \forall i, x_i \in [1, m – 1]\)的\(k\)元组方案数。首先，我们可以先枚举每一个\(A\)来缩小问题的范围，根据\(A\)所满足的条件，可以这样遍历\(i\)来获得每一个\(A\)：
这道题的式子跟 Codeforces 一道 F 题是一样的，让我误以为是 BSGS 之类的玩意，最后发现其实算是矩阵乘法的题。
考虑任意一个答案都是由\(\{f_n\}\)的幂的积组成的，由于\(k\)很小，所以我们可以考虑计算每一个\(f\)的指数，然后就可以用快速幂来计算这些东西。
今天这几题咋就那么毒瘤呢？
其实这道题考场上应该能做出来的，是一道很简单的计数问题。在考场上一看到字符串就懵了，不知道为什么我对字符串的字典序有阴影，现在看来就是一道傻逼题。
考虑这样计数：
结论 节点个数为\(n\)的无根标号树的个数为\(n^{n-2}\)。
这个结论在很多计数类题目中出现，要证明它首先需要了解 Prufer 序列的相关内容。接下来给出证明。