Codeforces 1540C Converging Array

\(a_i\)\(\frac{a_i + a_{i + 1} - b_i}{2}\) 做个比较,发现前者小于等于后者的条件为 \(a_{i + 1} - a_{i} \ge b_i\)

\(a_{i + 1}\)\(\frac{a_i + a_{i + 1} + b_i}{2}\) 做个比较,发现前者大于等于后者的条件为 \(a_{i + 1} - a_i \ge b_i\)

发现这两个条件是一样的,也就是说,一次操作的本质是:

  • 如果 \(a_{i + 1} - a_i \ge b_{i}\),则不会发生变化。
  • 如果 \(a_{i + 1} - a_i < b_i\),则发生变化。

更近一步的,如果发生了一次变化,那相邻两个数的差会变成什么呢?

\[\frac{a_{i} + a_{i + 1} + b_{i}}{2} - \frac{a_{i} + a_{i + 1} - b_{i}}{2} = b_i \]

也就是说,相邻的两个数的差,从原本的 \(< b_i\) 变成了 $ = b_i$,且这两个数的和不变

\(f_{1 \cdots n}\) 表示最终收敛的数组,必然对任意 \(i\) 都存在 \(f_{i+1} - f_i \ge b_i\)

并且如果 \(f_{i + 1} - f_i > b_i\),则整个过程中,\(a_i\)\(a_{i + 1}\) 之间就从来没有发生过赋值操作。

这是因为,如果发生了操作,那么这次操作后 \(f_{i + 1} - f_{i}\) 就会变得等于 \(b_i\),而且我们知道两个数的差只能从小于 \(b_i\) 变成等于 \(b_i\),而不能变成大于 \(b_i\),所以最终无法满足 \(f_{i + 1} - f_i > b_i\) 的条件。

以满足这种严格大于关系的点 \(i\) 为断点,可以发现,\(a_{1 \cdots i}\)\(a_{i + 1 \cdots n}\) 是完全互相不影响的。

现在要解决最棘手的一个问题,如何求出 \(f_1\) 呢?

假设我们知道了第一个断点的位置是 \(p\),那可以得到一个方程组:

\[\begin{cases} f_{2} - f_{1} = b_{1} \f_{3} - f_{2} = b_{2} \\cdots \f_{p} - f_{p - 1} = b_{p - 1} \\sum\limits_{i = 1}^{p} f_i = \sum\limits_{i = 1}^{p} a_i \end{cases} \]

\(f\) 看成未知数,则有 \(p\) 个未知数,\(p\) 个方程!于是我们可以手动解出 \(f_1\) 的值:

\[(f_1) + (f_1 + b_1) + (f_1 + b_1 + b_2) + \cdots = \sum_{i = 1}^{p} a_i \f_1 \times p + \sum_{i = 1}^{p - 1}(p - i)b_i = \sum_{i = 1}^{p} a_i \f_{1} = \frac{\sum\limits_{i = 1}^{p} a_i - \sum\limits_{i = 1}^{p - 1}(p - i)b_i}{p} \]

\(sa_p = \sum\limits_{i = 1}^{p}a_i, sb_p = \sum\limits_{i = 1}^{p - 1}(p - i)b_i\),则 \(f_1 = \frac{sa_p - sb_p}{p}\)

但问题是,我们并不知道 \(p\) 是多少。正确的解决方法是,将每个位置都尝试作为第一个端点,取解出来的 \(f_1\) 的最小值即可,也就是 \(f_1 = \min \left\{ \frac{s a_i - sb_i}{i} \right\}\)

首先证明 \(f_1 \ge \min \left\{ \frac{sa_i - sb_i}{i} \right\}\),这是因为必然存在某个前缀 \(p\) 使得 \(f_1 = \frac{sa_p - sb_p}{p}\),所以 \(f_1\) 大于等于取任意 \(p\) 时的最小值。

然后证明 \(f_1 \le \min \left\{ \frac{sa_i - sb_i}{i} \right\}\),这是因为对于任意前缀 \(p\),如果 \(f_1 \ne \frac{sa_p - sb_p}{p}\),就说明必然存在 \(f_{i + 1} - f_i > b_i\ (i < p)\) 的位置。但因为 \(\sum f\) 是保持不变的,为了使得跨度变大只能减小初值,得出 \(f_1 < \frac{sa_p - sb_p}{p}\)

回到原题,现在变成了一个计数问题。即,能找到多少个序列 \(a\),满足 \(0 \le a_i \le c_i\),且 \(\min \left\{ \frac{s a_i - sb_i}{i} \right\} \ge x\)

\(\min\) 转化为任意,命题等价于,对任意前缀 \(i\),都要满足:

\[\frac{sa_i - sb_i}{i} \ge x \quad \Rightarrow \quad sa_i \ge i \cdot x + sb_i \]

\(q = 1\) 时,不等式右边都是已知量,考虑一个 DP,用 \(f_{i, j}\) 表示前 \(i\) 项,和为 \(j\) 的方案数。因为合法的 \(a\) 必然是一个后缀,使用前缀和优化转移即可,单次转移 \(O(1)\)

时间复杂度 \(O(qn^2m)\)\(m\)\(a\) 的上限。

现在考虑多组询问,不同的 \(x\) 是否存在等价关系呢?

  • 如果存在 \(i\),满足 $ i \cdot x + sb_i > n \cdot m$,即 \(x > \min\left\{\frac{n \cdot m - sb_i}{i}\right\}\),答案必然为 \(0\)
  • 如果任意 \(i\),满足 \(i \cdot x + sb_i \le 0\),即 \(x \le \min\left\{ \frac{-sb_i}{i} \right\}\),答案必然为 \(\prod(c_i + 1)\)

现在只需要特别考虑 \(x \in \left(\min\left\{ \frac{-sb_i}{i} \right\}, \min\left\{\frac{n \cdot m - sb_i}{i}\right\}\right]\) 即可。

于是只有 \(O(m)\) 种本质不同的询问,全部预处理丢 map 里即可。时间复杂度 \(O(n^2m^2 + q \log m)\)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 105, MOD = 1e9 + 7;
int n, f[N * N], g[N * N], b[N], sb[N], c[N];
map<int, int> ans;
int Solve(int x)
{
	fill(g, g + N * N, 1);
	for(int i = 1, sumc = c[1], lim; i <= n; i++, sumc += c[i]) 
	{
		lim = i * x + sb[i]; memset(f, 0, sizeof(f));
		for(int j = max(0, lim); j < N * N; j++) f[j] = (g[j] - (j - c[i] - 1 >= 0 ? g[j - c[i] - 1] : 0) + MOD) % MOD;
		memset(g, 0, sizeof(g)); g[0] = f[0];
		for(int j = 1; j < N * N; j++) g[j] = (g[j - 1] + f[j]) % MOD;
	}
	return g[N * N - 1];
}
int main()
{
	ios::sync_with_stdio(false);
	cin >> n;
	int prod = 1;
	for(int i = 1; i <= n; i++) { cin >> c[i]; prod = (ll)prod * (c[i] + 1) % MOD; }
	for(int i = 1; i < n; i++) cin >> b[i];
	for(int i = 1; i <= n; i++) for(int j = 1; j < i; j++) sb[i] += (i - j) * b[j];
	int lb = 0, rb = INT_MAX, m = *max_element(c + 1, c + n + 1);
	for(int i = 1; i <= n; i++) lb = min(lb, -((sb[i] - 1) / i + 1)), rb = min(rb, (n * m - sb[i] - 1) / i + 1);
	for(int i = lb; i <= rb; i++) ans[i] = Solve(i);
	int q; cin >> q;
	while(q--)
	{
		int x; cin >> x;
		if(x >= lb && x <= rb) cout << ans[x] << endl;
		else if(x > rb) cout << 0 << endl;
		else if(x < lb) cout << prod << endl;
	}
	return 0;
}

Codeforces 1540C Converging Array

上一篇:HelloWorld


下一篇:移动方块