Converging Array (Hard Version)
Contest: Codeforces Round 728 (Div. 1)
Difficulty rating: 2900
Tags: dp, math

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).

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$$$.

Input format:
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 format:
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$$$.

Constraints:
Time limit: 5.0 s
Memory limit: 256.0 MB

Note:
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}$$$.

Example input:
3
2 3 4
2 1
5
-1 0 1 -100000 100000

Example output:
56
28
4
60
0

Editorial:
First, reduce the operations into something more manageable. It turns out operation $$$i$$$ sets $$$a_{i+1}-a_i=\max(b_i, a_{i+1}-a_i)$$$ while keeping $$$a_{i+1}+a_i$$$ constant. Visually, this is simultaneously moving $$$a_i$$$ up and $$$a_{i+1}$$$ down until $$$a_{i+1}-a[i] \geq b_i$$$.
Define $$$f$$$ to be the final converged array.
Let's some observations
1. If $$$a_{i+1}-a_i = b_i$$$ is ever satisfied throughout the process (if an operation ever moves anything), $$$f_{i+1}-f_i = b_i$$$. Equivalently, if $$$f_{i+1}-f_i > b_i$$$ then no operation $$$i$$$ could have ever been conducted
2. If no operation $$$i$$$ has been conducted, then $$$[1, i]$$$ is independent of $$$[i+1, n]$$$.
3. If $$$i$$$ is the first operation that has never been conducted, then $$$\sum_{j=1}^i a_j = \sum_{j=1}^i f_j$$$ because no sum could have been exchanged between $$$a_i$$$ and $$$a_{i+1}$$$.
Let's assume that we know that $$$i$$$ is the first observation that hasn't been conducted. We can then restore $$$f_1$$$ because we know that $$$f_1 + f_1+b_1+f_1+b_1+b_2 \ldots = a_1+a_2+\ldots+a_i$$$. To keep the tutorial clean, we refer to the prefix of prefix summation of $$$b_i$$$ as $$$bp_i$$$ and the prefix summation of $$$a_i$$$ as $$$ap_i$$$. Namely, we can solve for $$$f_1 = \frac{ap_i - bp_i}{i}$$$ given that $$$i$$$ is the first observation never conducted.
It turns out that $$$f_1 = \min(\frac{ap_i - bp_i}{i})$$$ over all $$$i$$$. This can be shown to be a lower bound on $$$f_1$$$ because the answer is obviously in this set as there must be some $$$i$$$ that is the first operation never conducted. This can also be shown to be an upperbound on the answer by playing the game on each prefix $$$i$$$. At each prefix $$$i$$$, the term $$$\frac{ap_i - bp_i}{i}$$$ is an upperbound because, if it's not equal to that term, there must be some $$$f_{i+1}-f_i > b_i$$$ so $$$f_1 < \frac{ap_i - bp_i}{i}$$$ because $$$f_1+f_2+\ldots+f_i$$$ remains the same.
Returning to the actual problem, we need to count arrays $$$\min(\frac{ap_i-bp_i}{i}) \geq x$$$. In other words, $$$ap_i \geq i \cdot x + bp_i$$$ must hold for all $$$i$$$. Let's do dynamic programming on $$$ap_i$$$. Call $$$dp[i][ap_i]$$$ the number of prefixes of length $$$i$$$ with current prefix sum of $$$ap_i$$$. We can transition to $$$i+1$$$ from $$$i$$$ using prefix sums on each valid $$$ap_i$$$.
Define $$$M = max(a_i)$$$. The current complexity is $$$O(Q M N^2)$$$ The final step is noticing that there are only $$$O(M)$$$ valid integer positions that end up being important for $$$f_1$$$. Intuitively, this is because in nearly all cases every operation $$$i$$$ ends up being used. To rigorously prove, let's find an upperbound on relevant $$$x$$$. If $$$M\cdot n < x\cdot n + bp_i$$$ then there are $$$0$$$ valid arrays. Because $$$x\cdot n + bp_i$$$ is concave and negative on the decreasing portion (i.e. the function goes down immediately into negative if it ever becomes negative, otherwise strictly increases), we can draw the inequality $$$0 \geq x\cdot n + bp_i$$$, otherwise every array ends up being good. Reducing the inequalities, we can realize that there is exactly $$$M$$$ different possible solutions. So, we can precalculate in $$$O(M^2N^2)$$$ and answer in $$$O(1)$$$.