【题解】CF1540C Converging Array
题意：
现在有长度为 $n$ 的数组 $a$ 和长度为 $n - 1$ 的数组 $b$，进行无穷次如下过程直至 $a$ 数组值收敛。
- 选择一个数字 $i$。
- 同时使 $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$ 有多少个。
$2\le n\le 100,0\le b_i,c_i\le 100,1\le q\le 10^5,-10^5\le x\le 10^5$。
首先，对于上述操作，有几个比较基本的观察：
两个操作要么同时成功，要么同时失败。
第一个操作成功当且仅当 $2a_i>a_i+a_{i+2}-b_i$，第二个操作成功当且仅当 $2a_{i+1}<a_i+a_{i+1}+b_i$，这两个不等式显然等价。
进行任意次操作，$\sum_{i=0}^n a_i$ 保持不变。
因为 $\dfrac{a_i+a_{i+1}-b_i}{2}+\dfrac{a_i+a_{i+1}+b_i}{2}=a_i+a_{i+1}$。
一次操作成功，当且仅当 $|a_{i+1}-a_i|<b_i$，操作过后 $a_{i+1}-a_i=b_i$。
因为上述操作实际上可以描述为先取平均数，然后左右各走 $\dfrac{b_i}{2}$ 步。
于是，假设 $\{a_n\}$ “收敛”后变成 $\{f_n\}$，则 $\{f_n\}$ 需要满足以下条件：
- $\sum_{i=1}^n a_i=\sum_{i=1}^n f_i$。
- $\forall 1\le i<n, f_{i+1}\ge f_{i}+b_i$。
注意到，若对于任意 $1\le i<n$，$f_{i+1}=f_i+b_i$，又有 $\sum_{i=1}^n f_i$ 的限制，于是我们实际上可以解出 $\{f_n\}$。具体来说：
$$ f_i=f_1+\sum_{j=1}^{i-1} b_j $$
$$ \sum_{i=1}^n a_i=\sum_{i=1}^n f=\sum_{i=1}^n(f_1+\sum_{j=1}^{i-1} b_j) $$
$$ =f_1 \times n+\sum_{i=1}^{n-1}(n-i)\times b_i $$
于是可以得到：
$$ f_1=\dfrac{\sum_{i=1}^n a_i-\sum_{i=1}^{n-1}(n-i)\times b_i}{n} $$
但是，我们知道并不一定所有 $f_{i+1}=f_i+b_i$。不过，对于 $f_{i+1}>f_{i}+b_i$ 的情况，我们可以得知：在 $i$ 与 $i+1$ 之间没有进行过操作。
这是因为我们一次操作一定会使得 $f_{i+1}=f_i+b_i$，但最后 $f_{i+1}>f_i+b_i$，只能说明一开始 $a_i$ 与 $a_{i+1}$ 的差就已经 $>b_i$ 了。
于是，总存在一个前缀 $[1,p]$，满足 $\forall 1\le i<p,f_{i+1}=f_i+b_i$，且 $[p+1,n]$ 与 $[1,p]$ 是互不影响的。因此，如果我们已经得知了 $p$ 的确切值，那么 $f_1$ 的值就得到了确定，他应该是：
$$ \dfrac{\text{suma}_p-\text{sumb}_p}{p} $$
其中：
$$ \text{suma}_p=\sum_{i=1}^p a_i,\ \text{sumb}_p=\sum_{i=1}^{p-1}(p-i)\times b_i $$
不过实际上，$p$ 的取值是未知的。那应该怎么确定 $f_1$ 呢？
首先，由于一定存在一个合法的 $p$，所以：
$$ f_1\in\Big\{\dfrac{\text{suma}_p-\text{sumb}_p}{p}\ |\ p\in[1,n]\Big\} $$
同时，假设对于一个前缀 $p$，他不满足 $\forall 1\le i<p,f_{i+1}=f_i+b_i$，那么一定有：
$$ f_1<\dfrac{\text{suma}_p-\text{sumb}_p}{p} $$
这是因为，前缀 $p$ 不满足一定是因为存在一个位置满足 $f_{i+1}>f_i+b_i$，则 $f_{i+1}$ 的大小超出了我们的预计。又 $f$ 的和是一定的，所以 $i$ 及其前面的部分应该比预计的更小。
于是，结合上述两条观察，我们可以得出一个厉害的结论：
$$ f_1=\min\Big\{\dfrac{\text{suma}_p-\text{sumb}_p}{p}\Big\} $$
至此，我们得到了一种方式，能够快速通过 $\{a_n\}$、$\{b_n\}$ 来计算 $F(a,b)$（即 $f_1$）的值。
接下来考虑计数，$F(a,b)\ge x$ 实际上就是：
$$ \forall\ p\in[1,n],\ \dfrac{\text{suma}_p-\text{sumb}_p}{p}\ge x $$
即：
$$ \text{suma}_p\ge \text{sumb}_p+p\times x $$
这是一个背包的模型，设 $m$ 为 $a_i$ 的值域上界的话，对于单个 $x$ 进行求解的复杂度是 $\mathcal{O}(n^2m^2)$，容易通过前缀和优化的方式做到单次 $\mathcal{O}(n^2m)$。于是，我们便得到了一种 $\mathcal{O}(qn^2m)$ 的做法。
但在困难版中，$q\le 10^5$，这是无法接受的。考虑如何快速计算不同 $x$ 的答案。
感性地想，如果这个 $x$ 极小，导致甚至 $\{a_n\}$ 中全是 $0$ 都合法，那么便说明所有序列都是合法的，方案数是：
$$ \prod_{i=1}^n (c_i+1) $$
需要满足什么条件？应该是：
$$ x\le \min\Big\{\dfrac{-\text{sumb}_p}{p}\Big\} $$
即就算 $\{a_n\}$ 中全是 $0$ 仍然合法。相应的，如果这个 $x$ 极大，导致 $\forall\ 1\le i\le n,\ a_i=c_i$ 都不满足条件，则说明所有序列都是不合法的，答案为 $0$。他需要满足条件：
$$ x>\min\Big\{\dfrac{p\times m-\text{sumb}_p}{p}\Big\} $$
因此，只有 $x\in \Big(\min\Big\{\dfrac{-\text{sumb}_p}{p}\Big\},\ \min\Big\{\dfrac{p\times m-\text{sumb}_p}{p}\Big\}\Big]$ 的部分是需要计算的，这里只有 $\mathcal{O}(m)$ 个取值！
因此，我们可以在 $\mathcal{O}(n^2m^2)$ 的时间内进行预处理，然后 $\mathcal{O}(1)$ 回答。
//Code By CXY07 - It's My Fiesta.
#include<bits/stdc++.h>
using namespace std;
//#define FILE
#define int long long
#define randint(l, r) (rand() % ((r) - (l) + 1) + (l))
#define abs(x) ((x) < 0 ? (-(x)) : (x))
#define popc(x) __builtin_popcount(x)
#define inv(x) qpow((x), mod - 2)
#define lowbit(x) ((x) & (-(x)))
#define ull unsigned long long
#define pii pair<int, int>
#define LL long long
#define mp make_pair
#define pb push_back
#define scd second
#define vec vector
#define fst first
#define endl '\n'
#define y1 _y1
const int MAXN = 110;
const int MAXX = 2e5 + 10;
const int SIZ = 1e4 + 10;
const int INF = 2e9;
const double eps = 1e-6;
const double PI = acos(-1);
const int mod = 1e9 + 7;
//const int mod = 998244353;
//const int G = 3;
//const int base = 131;
int n, m, q, prod = 1, c[MAXN], b[MAXN];
int L, R, sav[MAXX], sumb[MAXN];
int dp[SIZ], sum[SIZ];
bool vis[MAXX];
template<typename T> inline bool read(T &a) {
a = 0; char c = getchar(); int f = 1;
while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); }
while(c >= '0' && c <= '9') { a = a * 10 + (c ^ 48); c = getchar(); }
return a *= f, true;
}
template<typename A, typename ...B>
inline bool read(A &x, B &...y) { return read(x) && read(y...); }
int calc(int x) {
if(vis[x + (int)1e5]) return sav[x + (int)1e5];
vis[x + (int)1e5] = true;
memset(sum, 0, sizeof sum);
for(int i = 0; i <= n * m; ++i) sum[i] = 1;
for(int i = 1; i <= n; ++i) {
memset(dp, 0, sizeof dp);
for(int j = 0; j <= n * m; ++j) {
if(j < i * x + sumb[i]) continue;
dp[j] = sum[j];
if(j > c[i]) (dp[j] -= sum[j - c[i] - 1]) %= mod;
}
for(int j = 0; j <= n * m; ++j)
sum[j] = (dp[j] + (j > 0 ? sum[j - 1] : 0)) % mod;
}
return sav[x + (int)1e5] = (sum[n * m] + mod) % mod;
}
signed main () {
#ifdef FILE
freopen(".in", "r", stdin);
freopen(".out", "w", stdout);
#endif
read(n), m = 100;
for(int i = 1; i <= n; ++i) {
read(c[i]);
prod = prod * (c[i] + 1) % mod;
}
for(int i = 1; i < n; ++i) read(b[i]);
L = R = INF;
for(int i = 1, s = 0, si = 0; i <= n; ++i) {
sumb[i] = (i * s - si + mod) % mod;
(s += b[i]) %= mod, (si += b[i] * i) %= mod;
L = min(L, -sumb[i] / i - 1);
R = min(R, (i * m - sumb[i]) / i + 1);
}
read(q);
while(q--) {
int x; read(x);
if(x < L) printf("%lld\n", prod);
else if(x > R) puts("0");
else printf("%lld\n", calc(x));
}
return 0;
}