时间限制： 1.0 秒

空间限制： 2 MB

题目背景

所谓 Fib-AVL 树，就是每一个非叶子节点的右子树高度都比左子树高度大 1 的二叉树。例如下图中为高度 $h=1,2,3$ 的 Fib-AVL 树。在本题中，根节点的深度定义为 $0$。

题目描述

请设计一个算法，在高度为 $h$ 的 Fib-AVL 树中，对于任意的 $0\le k\le h$，计算深度为 $k$ 的节点总个数 $s(h,k)$，要求时间复杂度为 $O(h^2)$，空间复杂度为 $O(h)$。

由于答案可能很大，你只需要给出答案对 $10^9+7$ 取模的值即可。

输入格式

从标准输入读入数据。

本题包含多组测试数据。

输入的第一行包含一个正整数 $T$，表示测试数据组数。

对于每组测试数据：

输入一行两个整数 $h,k$。

输出格式

输出到标准输出。

对于每组测试数据：

输出一行一个整数，表示高度为 $h$ 的 fib-AVL 树中，深度为 $k$ 的节点个数对 $10^9+7$ 取模的值。

9
1 0
1 1
2 0
2 1
2 2
3 0
3 1
3 2
3 3

1
1
1
2
1
1
2
3
1

子任务

对于所有数据，保证：

• $1\le T\le 10^4$；
• $1\le h\le 10^4,~0\le k\le h$；
• 每个测试点内的所有数据 $\sum h\le 10^4$；

本题无数据梯度，需要通过全部数据获得所有分数。

提示

请注意本题非同寻常的空间限制，如有需要，请使用 int 类型的静态数组进行存储。此外，引用万能头（bits/stdc++.h）或者使用动态数组 vector 也会消耗大量空间，建议不要使用。

此外，由于本题每个测试点拥有多组数据，建议在重复的一个全局静态数组上进行计算，注意多组数据的情况下，数组需要初始化。

考虑一下如何将空间复杂度降到 $O(h)$ 呢？

来源

清华 826 考研初试 2026 - 算法大题（2）