Converging Array (Hard Version)

题意翻译

这是这道题的困难版，与简单版唯一不同是 $1 \le q \le 10^5$ 现在有长度为 $n$ 的数组 $a$ 和长度为 $n - 1$的数组 $b$，进行无穷次如下过程直至 $a$ 数组值收敛 1. 选择一个数字 $i$ 2. 同时使 $a_i = min(a_i, \frac{a_i + a_{i + 1} - b_i}{2}),\ a_{i + 1} = max(a_{i + 1}, \frac{a_i + a_{i + 1} + b_i}{2})$ （没有取整） 定义 $F(a, b)$ 为操作完成后 $a_1$ 的值 现在你知道数组 $b$ 和 长度为 $n$ 的数组 $c$，保证 $\forall i \in [1, n],\ 0 \le a_i \le c_i$ 有 $q$ 组询问，每次问使 $F(a, b) \ge x$ 的数组 $a$ 有多少个 答案对 $1\ 000\ 000\ 007$ 取模

题目描述

This is the hard version of the problem. The only difference is that in this version $ 1 \le q \le 10^5 $ . You can make hacks only if both versions of the problem are solved. There is a process that takes place on arrays $ a $ and $ b $ of length $ n $ and length $ n-1 $ respectively. The process is an infinite sequence of operations. Each operation is as follows: - First, choose a random integer $ i $ ( $ 1 \le i \le n-1 $ ). - Then, simultaneously set $ a_i = \min\left(a_i, \frac{a_i+a_{i+1}-b_i}{2}\right) $ and $ a_{i+1} = \max\left(a_{i+1}, \frac{a_i+a_{i+1}+b_i}{2}\right) $ without any rounding (so values may become non-integer). See notes for an example of an operation.It can be proven that array $ a $ converges, i. e. for each $ i $ there exists a limit $ a_i $ converges to. Let function $ F(a, b) $ return the value $ a_1 $ converges to after a process on $ a $ and $ b $ . You are given array $ b $ , but not array $ a $ . However, you are given a third array $ c $ . Array $ a $ is good if it contains only integers and satisfies $ 0 \leq a_i \leq c_i $ for $ 1 \leq i \leq n $ . Your task is to count the number of good arrays $ a $ where $ F(a, b) \geq x $ for $ q $ values of $ x $ . Since the number of arrays can be very large, print it modulo $ 10^9+7 $ .

输入输出格式

输入格式

The first line contains a single integer $ n $ ( $ 2 \le n \le 100 $ ). The second line contains $ n $ integers $ c_1, c_2 \ldots, c_n $ ( $ 0 \le c_i \le 100 $ ). The third line contains $ n-1 $ integers $ b_1, b_2, \ldots, b_{n-1} $ ( $ 0 \le b_i \le 100 $ ). The fourth line contains a single integer $ q $ ( $ 1 \le q \le 10^5 $ ). The fifth line contains $ q $ space separated integers $ x_1, x_2, \ldots, x_q $ ( $ -10^5 \le x_i \le 10^5 $ ).

输出格式

Output $ q $ integers, where the $ i $ -th integer is the answer to the $ i $ -th query, i. e. the number of good arrays $ a $ where $ F(a, b) \geq x_i $ modulo $ 10^9+7 $ .

输入输出样例

输入样例 #1

3
2 3 4
2 1
5
-1 0 1 -100000 100000

输出样例 #1

56
28
4
60
0

说明

The following explanation assumes $ b = [2, 1] $ and $ c=[2, 3, 4] $ (as in the sample). Examples of arrays $ a $ that are not good: - $ a = [3, 2, 3] $ is not good because $ a_1 > c_1 $ ; - $ a = [0, -1, 3] $ is not good because $ a_2 < 0 $ . One possible good array $ a $ is $ [0, 2, 4] $ . We can show that no operation has any effect on this array, so $ F(a, b) = a_1 = 0 $ . Another possible good array $ a $ is $ [0, 1, 4] $ . In a single operation with $ i = 1 $ , we set $ a_1 = \min(\frac{0+1-2}{2}, 0) $ and $ a_2 = \max(\frac{0+1+2}{2}, 1) $ . So, after a single operation with $ i = 1 $ , $ a $ becomes equal to $ [-\frac{1}{2}, \frac{3}{2}, 4] $ . We can show that no operation has any effect on this array, so $ F(a, b) = -\frac{1}{2} $ .

题意翻译

这是这道题的困难版，与简单版唯一不同是 $1 \le q \le 10^5$ 现在有长度为 $n$ 的数组 $a$ 和长度为 $n - 1$的数组 $b$，进行无穷次如下过程直至 $a$ 数组值收敛 1. 选择一个数字 $i$ 2. 同时使 $a_i = min(a_i, \frac{a_i + a_{i + 1} - b_i}{2}),\ a_{i + 1} = max(a_{i + 1}, \frac{a_i + a_{i + 1} + b_i}{2})$ （没有取整） 定义 $F(a, b)$ 为操作完成后 $a_1$ 的值 现在你知道数组 $b$ 和 长度为 $n$ 的数组 $c$，保证 $\forall i \in [1, n],\ 0 \le a_i \le c_i$ 有 $q$ 组询问，每次问使 $F(a, b) \ge x$ 的数组 $a$ 有多少个 答案对 $1\ 000\ 000\ 007$ 取模