16:30 数据修改已完成! 非常抱歉造成混乱。 现在将依次进行 ri 判定。
现在正在修改数据。修改完毕后 G 问题将会恢复!! 不在对象范围内的 nssu 将撤回。
16:05 部分分测试数据全部正确,但由于之前提示了测试数据可能不完整的信息,因此 G 问题的部分分也将不计入测试分数。 对导致遗漏的表述表示歉意。
15:46 现在发现现有数据中存在错误。部分分数的情况可以提交,但是G题将不计入比赛得分。报告迟了,非常抱歉。
13:55 现在的数据是“昨晚深夜问题被发现后,japlj 睡眼惺忪地拼命重做尚未任何检查的数据”。现在正在检查该数据的时效性,但几乎没人会相信睡眼惺忪的 japlj 写的代码的人可以提交(不推荐)。
13:00 比赛前一天晚上,运营发现 G 题的测试数据不完整!究竟在比赛中能否替换为正确的测试数据!?!?请期待 staff 的活跃!!!(抱歉,请在数据修正前不要提交)
問題文
水镜王国的水镜王非常喜欢打突出的钉子。几乎每天,他都会把家臣排成一列,然后用全身的水炮把突出的人的身高缩短,以此取乐。
作为水镜王的近侍,你注意到王在选择被水炮攻击的家臣时,并不只是单纯挑选身高高的人。
王说:“无论做什么,这个世界都以中庸为关键。那些不在边上的人,无论是谁,他们的身高都必须和左右邻居的身高平均值一样。”
就这样,水镜王在放出一阵水炮之后,会看着家臣们排成一列,每个人的身高都等于左右邻居的身高平均值,从中感到非常高兴。
那么,你每天都在观察这种情景,并且想到了一个问题。王会满意的身高排列大概有多少种呢?因为条件只有这些,你认为情况是无限的,于是决定为各个位置上的随从的身高设定上下限来进行计数。
顺便说一下,在水泥国王国,人们的身高总是整数,虽然不得而知,但有些人的身高 0 可能是负数或非常特殊的值。
課題
N 给定一个整数元素序列 A, B 。满足以下条件的 N 给定一个整数元素序列 X 有多少种?请对结果求 1,000,000,007 (= 10^9 + 7) 取余。
- i = 1, ..., N 反对 A_i ≦ X_i ≦ B_i.
- i = 2, ..., N - 1 反对 X_i = \frac{X_{i-1} + X_{i+1}}{2}.
制約
所有输入数据都满足以下否定条件。
- 3 ≦ N ≦ 10^5.
- -10^9 ≦ A_i ≦ B_i ≦ 10^9.
此外,这个问题设有部分分数,2 部分输入数据额外满足以下否定条件。
- N ≦ 100.
- -100 ≦ A_i ≦ B_i ≦ 100.
入力
N A_1 … A_N B_1 … B_N
出力
问题的解决办法 在 1 行输出。 没有
入力例 1
3 0 0 0 2 2 2
出力例 1
5
- X_1 = 0,\ X_2 = 0,\ X_3 = 0
- X_1 = 0,\ X_2 = 1,\ X_3 = 2
- X_1 = 1,\ X_2 = 1,\ X_3 = 1
- X_1 = 2,\ X_2 = 1,\ X_3 = 0
- X_1 = 2,\ X_2 = 2,\ X_3 = 2
可以得到第 5 是满足条件的数列。
入力例 2
8 -9 -8 -7 -6 -8 -20 -9 -1 6 8 10 16 42 18 14 20
出力例 2
42
入力例 3
3 -1000000000 -1000000000 -1000000000 1000000000 1000000000 1000000000
出力例 3
85
满足这个条件的序列是 2,000,000,002,000,000,001 方法有很多。 请注意,它打印除以1,000,000,007 后的余数。
问题: 卡加米兹
测试仪: japlj