/ ZYCode / 题库 /

【ZYCode R3】参天大树

【ZYCode R3】参天大树

题目描述

有一颗无限大的树,每个节点有 \(n\) 个子节点,连接它与第 \(i\) 个子节点的边长为 \(a_i\)。求这颗树上有多少节点与根节点的距离小于等于 \(k\)。对 \(1e9+7\) 取模

输入格式

第一行两个数 \(n\),\(k\)

第二行 \(n\) 个数,第 \(i\) 个数代表 \(a_i\)

输出格式

这棵树上离根节点距离小于等于 \(k\) 的节点个数

样例

样例输入 1

2 4
1 2

样例输出 1

7

提示说明

对于 30% 的数据

\( n \le 10 \)

对于 60% 的数据

\( k \le 10^3 \)

对于 100% 的数据

\( n \le 10^5 \)

\( k \le 10^9 \)

\(a_i \le 100\)

信息

ID
1018
难度
2100
分类
树结构 | 动态规划 | 矩阵乘法 点击显示
标签
递交数
1
已通过
1
通过率
100%
上传者