A6046 | $「2017 山东一轮集训 Day5」苹果树$

时间限制1s

内存限制512MB

通过 / 提交0/0

题目描述

给定 $ n $ 个苹果，对于苹果 $ i $，其甜度为 $ c_i $，$ c_i \geq -1 $。假如 $ c_i = -1 $，代表苹果 $ i $ 是坏的，否则它是好的。 现在要用 $ n - 1 $ 条线把这 $ n $ 个苹果连成一个连通块，也就是一棵树，定义树上一个苹果是有用的，当且仅当它是一个好苹果，且至少与一个好苹果直接相连，一棵树的权值定义为树上的有用的苹果的甜度之和。 给定 $ \text{limit} $，问有多少种不同的生成树，满足其权值小于等于 $ \text{limit} $，答案对 $ 10 ^ 9 + 7 $ 取模。两个生成树是不同的，当且仅当存在一条边 $ (u, v) $，满足 $ (u, v) $ 在一棵生成树中出现，在另外一棵中没有出现。

第一行两个整数 $ n, \text{limit} $。 第二行 $ n $ 个整数，依次描述 $ c_i $。

输出一行一个整数，代表生成树的数量。

输入 #1

4 5
1 2 -1 3

输出 #1

C++ 编辑器

输入

输出