Problem 6F. 我爱上课
Problem 6F. 我爱上课
时间限制:1s
空间限制:256MB
Description
显然,我们把从宿舍到教室的路径表示为一条直线,这样我们就可以方便地计算宿舍和教室之间的距离。
比如, 的宿舍和教室之间的距离是 米 我们认为 的宿舍位于坐标 处,教室位于坐标 处。
但是,长时间走路太累了。如果 自从上次停下来休息后已经又走了 米,他认为走第 公里的难度为 。
保证任意 。去上课的难度用走路过程中每米的难度之和表示。
幸好,在教室和宿舍之间 可能 有一些休息点。从 到 的每一个整数点都 可能 包含一个休息点。
当 进入休息点时,由于他比较怕累,所以将会休息一下,那么下一米的难度将会为 ,再下一米的难度为 ,以此类推。
例如,如果 和坐标 上有一个休息点,那么行程的难度将是 : 第一公里的难度为 ,第二公里的难度为 ,然后 休息,第三公里的难度为 ,第四公里的难度为 ,最后一公里的难度为 。
再比如,如果 ,坐标 和 有休息点, 的旅程难度为 。
但是, 不知道哪个整数点包含休息点。所以他必须考虑所有可能的情况。
显然,有 个不同的休息点分布( 如果存在某个点 ,使得它恰好在其中一个分布中包含休息点,则两个分布是不同的 )。
认为所有这些分布都是等概率的。他想计算期望 他上课途中困难的预期值。
显然, 是一个整数。你的任务是计算它对 取模。
Input Format
第一行包含一个数字 ( ) 从 宿舍到教室的距离。
第二行包含 整数 , ,…, ( ),其中 为 休息后第 米的难度。
Output Format
打印一个数字 ,并对 取模。
Input Example #1:
Output Example #1:
Input Example #2:
Output Example #2:
Data Range
, 。
信息
- ID
- 1548
- 难度
- 9
- 分类
- (无)
- 标签
- (无)
- 递交数
- 2
- 已通过
- 1
- 通过率
- 50%
- 上传者