【题解】CF1540C Converging Array

题目链接：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$，保证 $\mathrm{\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$ 保持不变。

因为 ${\displaystyle \frac{a_i+a_{i+1}-b_i}{2}}+{\displaystyle \frac{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$。

因为上述操作实际上可以描述为先取平均数，然后左右各走 ${\displaystyle \frac{b_i}{2}}$ 步。

于是，假设 $\{a_n\}$ “收敛”后变成 $\{f_n\}$，则 $\{f_n\}$ 需要满足以下条件：

• $\sum _{i=1}^n{a}_i=\sum _{i=1}^n{f}_i$。
• $\mathrm{\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={\displaystyle \frac{\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]$，满足 $\mathrm{\forall }1\le i<p,f_{i+1}=f_i+b_i$，且 $[p+1,n]$ 与 $[1,p]$ 是互不影响的。因此，如果我们已经得知了 $p$ 的确切值，那么 $f_1$ 的值就得到了确定，他应该是：

$${\displaystyle \frac{{\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 \{{\displaystyle \frac{{\text{suma}}_p-{\text{sumb}}_p}{p}}|p\in [1,n]\}$$

同时，假设对于一个前缀 $p$，他不满足 $\mathrm{\forall }1\le i<p,f_{i+1}=f_i+b_i$，那么一定有：

$$f_1<{\displaystyle \frac{{\text{suma}}_p-{\text{sumb}}_p}{p}}$$

这是因为，前缀 $p$ 不满足一定是因为存在一个位置满足 $f_{i+1}>f_i+b_i$，则 $f_{i+1}$ 的大小超出了我们的预计。又 $f$ 的和是一定的，所以 $i$ 及其前面的部分应该比预计的更小。

于是，结合上述两条观察，我们可以得出一个厉害的结论：

$$f_1=min\{{\displaystyle \frac{{\text{suma}}_p-{\text{sumb}}_p}{p}}\}$$

至此，我们得到了一种方式，能够快速通过 $\{a_n\}$、$\{b_n\}$ 来计算 $F(a,b)$（即 $f_1$）的值。

接下来考虑计数，$F(a,b)\ge x$ 实际上就是：

$$\mathrm{\forall }p\in [1,n],{\displaystyle \frac{{\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^2{m}^2)$，容易通过前缀和优化的方式做到单次 $\mathcal{O}(n^{2}m)$。于是，我们便得到了一种 $\mathcal{O}(q{n}^{2}m)$ 的做法。

但在困难版中，$q\le {10}^5$，这是无法接受的。考虑如何快速计算不同 $x$ 的答案。

感性地想，如果这个 $x$ 极小，导致甚至 $\{a_n\}$ 中全是 $0$ 都合法，那么便说明所有序列都是合法的，方案数是：

$$\prod _{i=1}^n(c_i+1)$$

需要满足什么条件？应该是：

$$x\le min\{{\displaystyle \frac{-{\text{sumb}}_p}{p}}\}$$

即就算 $\{a_n\}$ 中全是 $0$ 仍然合法。相应的，如果这个 $x$ 极大，导致 $\mathrm{\forall }1\le i\le n,a_i=c_i$ 都不满足条件，则说明所有序列都是不合法的，答案为 $0$。他需要满足条件：

$$x>min\{{\displaystyle \frac{p\times m-{\text{sumb}}_p}{p}}\}$$

因此，只有 $x\in (min\{{\displaystyle \frac{-{\text{sumb}}_p}{p}}\},min\{{\displaystyle \frac{p\times m-{\text{sumb}}_p}{p}}\}]$ 的部分是需要计算的，这里只有 $\mathcal{O}(m)$ 个取值！

因此，我们可以在 $\mathcal{O}(n^2{m}^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;
}