这是问题的简单版本。唯一的区别是在此版本中 $$$q = 1$$$。只有当问题的两个版本都得到解决时,你才能进行黑客攻击。
在长度分别为 $$$n$$$ 和长度 $$$n-1$$$ 的数组 $$$a$$$ 和 $$$b$$$ 上发生一个过程。
该过程是一个无限的操作序列。各个操作如下:
- 首先,选择一个随机整数 $$$i$$$ ($$$1 \le i \le n-1$$$)。
- 然后,同时设置 $$$a_i = \min\left(a_i, \frac{a_i+a_{i+1}-b_i}{2}\right)$$$ 和 $$$a_{i+1} = \max\left(a_{i+1}, \frac{a_i+a_{i+1}+b_i}{2}\right)$$$,无需任何舍入(因此值可能会变成非整数)。
可以证明数组$$$a$$$收敛,即。 e.对于每个 $$$i$$$ 存在一个限制 $$$a_i$$$ 收敛到。让函数 $$$F(a, b)$$$ 返回值 $$$a_1$$$ 在 $$$a$$$ 和 $$$b$$$ 上进行处理后收敛到。
给出了数组 $$$b$$$,但没有给出数组 $$$a$$$。然而,你得到了第三个数组$$$c$$$。如果数组 $$$a$$$ 只包含整数并且满足 $$$0 \leq a_i \leq c_i$$$(对于 $$$1 \leq i \leq n$$$),那么它是好的。
你的任务是计算好数组 $$$a$$$ 的数量,其中 $$$F(a, b) \geq x$$$ 为 $$$x$$$ 的 $$$q$$$ 值。由于数组的数量可能非常大,因此将其打印为 $$$10^9+7$$$ 模。
输入
第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 100$$$)。
第二行包含 $$$n$$$ 整数 $$$c_1, c_2 \ldots, c_n$$$ ($$$0 \le c_i \le 100$$$)。
第三行包含 $$$n-1$$$ 整数 $$$b_1, b_2, \ldots, b_{n-1}$$$ ($$$0 \le b_i \le 100$$$)。
第四行包含一个整数 $$$q$$$ ($$$q=1$$$)。
第五行包含 $$$q$$$ 空格分隔的整数 $$$x_1, x_2, \ldots, x_q$$$ ($$$-10^5 \le x_i \le 10^5$$$)。
输出
输出 $$$q$$$ 整数,其中第 $$$i$$$ 个整数是第 $$$i$$$ 个查询 i 的答案。 e.好数组的数量 $$$a$$$ 其中 $$$F(a, b) \geq x_i$$$ 模 $$$10^9+7$$$。
示例
输入 #1
3 2 3 4 2 1 1 -1
输出 #1
56
注意
以下解释假设 $$$b = [2, 1]$$$ 和 $$$c=[2, 3, 4]$$$(如示例中所示)。
不好的数组 $$$a$$$ 的示例:
- $$$a = [3, 2, 3]$$$ 不好,因为 $$$a_1 > c_1$$$;
- $$$a = [0, -1, 3]$$$ 不好,因为 $$$a_2 < 0$$$。
一个可能的好数组 $$$a$$$ 是 $$$[0, 2, 4]$$$。我们可以证明没有任何操作对该数组有任何影响,因此 $$$F(a, b) = a_1 = 0$$$。
另一个可能的好数组 $$$a$$$ 是 $$$[0, 1, 4]$$$。在 $$$i = 1$$$ 的单个操作中,我们设置 $$$a_1 = \min(\frac{0+1-2}{2}, 0)$$$ 和 $$$a_2 = \max(\frac{0+1+2}{2}, 1)$$$。因此,在 $$$i = 1$$$ 进行一次操作后,$$$a$$$ 就等于 $$$[-\frac{1}{2}, \frac{3}{2}, 4]$$$。我们可以证明没有任何操作对该数组有任何影响,因此 $$$F(a, b) = -\frac{1}{2}$$$。