跳到主要内容
图灵 OJTURING / ONLINE JUDGE

#F0273. #6072. 「2017 山东一轮集训 Day5」苹果树

  • ID: 279
  • 传统题
  • 1000ms
  • 512MiB
  • 尝试: 0
  • AC · 已通过: 0
  • 教学难度:待分级
  • 上传者:
  • 待分类
  • 整理状态
  • 难度待定
  • 难度
  • 共享题库
  • LibreOJ
  • 中文题面
  • 题目来源
  • 题面语言

#6072. 「2017 山东一轮集训 Day5」苹果树

题目描述

给定 个苹果,对于苹果 ,其甜度为 ,。假如 ,代表苹果 是坏的,否则它是好的。

现在要用 条线把这 个苹果连成一个连通块,也就是一棵树,定义树上一个苹果是有用的,当且仅当它是一个好苹果,且至少与一个好苹果直接相连,一棵树的权值定义为树上的有用的苹果的甜度之和。

给定 ,问有多少种不同的生成树,满足其权值小于等于 ,答案对 取模。两个生成树是不同的,当且仅当存在一条边 ,满足 在一棵生成树中出现,在另外一棵中没有出现。

输入格式

第一行两个整数 。
第二行 个整数,依次描述 。

输出格式

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

样例

样例输入

4 5
1 2 -1 3

样例输出

7

数据范围与提示

对于 的数据,;
对于另外 的数据,坏苹果的数量 ;
对于 的数据,。


题目来源:fps-loj-small-pics.zip;FPS 共享题包,题包内第 169 题。保留原作者与原赛事署名。