【题解】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$,保证 $\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;
}
添加新评论