树

1s 512MB

问题描述

有一棵树 $T$，初始时只有一个点。接下来将下列操作重复 $n$ 次：

• 建一棵树 $T'$，初始时 $T' = T$。接着对 $T$ 中的每一个点 $v$，在 $T'$ 中新增一个叶子 $l$ 使得 $l$ 和 $v$ 相连。最后令 $T = T'$。

容易发现，最终得到的树有 $2n$ 个点。求这棵树上满足 $u$ 和 $v$ 的距离为 $d$ 的无序点对 $(u, v)$ 个数，答案对 $P$ 取模。

输入格式

输入数据共一行，包含三个整数 $n$, $d$, $P$。

输出格式

输出一行一个数，满足条件的点对个数对 $P$ 取模的结果。

输入输出样例 1

输入：

3 3 1000000007

输出：

8

输入输出样例 2

输入：

10 5 1000000009

输出：

21352

数据范围与约定

对于 $20\%$ 的数据，$n \le 10$。

对于另外 $30\%$ 的数据，$d \le 3$。

对于另外 $30\%$ 的数据，$d \le 500$。

对于另外 $10\%$ 的数据，$d \le 10^5, P = 998244353$。

对于所有数据，$1 \le n \le 10^9, 1 \le d \le 10^7, 10^8 \le P \le 1.05 × 10^9$，$P$ 是质数。

---

目前已推出：

$$f(n, d) = \begin{cases} 2^n - 1 \quad d = 1 \\ \sum\limits_{i = 0}^{n - \lceil \frac{d + 1}{2} \rceil}{2^i \sum\limits_{j = 0}^{d - 1}{{n - i - 1 \choose j}{n - i - 1 \choose d - j - 1}}} \quad 1 < d \le 2n - 1 \\ 0 \quad d > 2n - 1 \end{cases}$$

其中 $f(n, d)$ 即为答案，但不知道下一步该怎么做。