← 返回题目列表

AtCoder · k4pc_g

G. 四十二

中文机器翻译题面 查看原题
16:40 已结束 ri 判定。
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
问题: 卡加米兹
测试仪: japlj