自动搬运

查看原文

来自洛谷，原作者为

	Sliarae Re:start

搬运于2025-08-24 23:07:55，当前版本为作者最后更新于2025-01-08 15:06:22，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

感谢镜像赛工作人员 @沉石鱼惊旋 提供官方题解。

以下设 $V$ 为值域，题目中保证 $V \le 10^7$。

考虑在 $x$ 处放一根薯条的作用效果。枚举这根薯条向左传了 $d$ 次，那么 $x + T - 2d$ 处的人会获得 $\frac{{T \choose d}}{2^T}$ 根薯条。

预处理 $dif_i$ 表示在某个位置放一根薯条，最终距离它为 $i$ 的人能获得多少根薯条。这一部分我们只需预处理 $T$ 以内的阶乘，阶乘可能很大，可以取以 $2$ 为底的对数，这样方便除 $2^T$。

观察杨辉三角，我们发现两边的数比起中间是非常小的。我们可以设一个宽度 $W$，在 $x$ 放薯条时只处理 $x$ 对 $[x - W, x + W]$ 的影响，也就是说我们认为 $dif_i(i > W)$ 约等于 $0$。事实上 $W$ 取 $O(\sqrt T)$ 即可，代码中 $W = 10^5$。

直接暴力考虑每个放薯条的位置对两边 $W$ 个数的影响，可以得到一个时间复杂度 $O(V + P\sqrt T)$ 的做法，期望得到 $74$ 分。

进一步观察操作性质。发现 $dif$ 可以按奇偶性分成两个序列，一个全是 $0$，一个单调递减（因为杨辉三角从中间到两边单调递减），下面只讨论后者。

考虑将 $dif$ 分成若干极长段，每一段的最大值 $mx$ 和最小值 $mi$ 满足 $\frac{mx}{mi}$ 不超过一阈值 $D = 1.25$，将这一段中所有值都认为是 $\sqrt{mi \times mx}$。

由于每一段最大值不超过上一段的 $\frac{1}{D}$，这样做将 $O(W)$ 个单点加变成了 $O(\log_D \alpha)$ 个区间加，其中 $\alpha$ 为代码精度（大概是 $10^{18}$ 级别），以便我们快速用差分维护。

再来分析误差，由于 $\frac{mx}{mi} \le D$，$mx$ 这个数变成了原来的 $\sqrt{\frac{mi}{mx}} \ge D^{-0.5}$ 倍，而 $mi$ 变成了原来的 $\sqrt{\frac{mx}{mi}} \le D^{0.5}$ 倍。所以误差为 $D^{-0.5} \sim D^{0.5}$，算一算是 $0.91287 \sim 1.09545$，而题目中允许的误差是 $0.8 \sim 1.2$，可以接受。

时间复杂度 $O(P \log_{D} \alpha + V + T)$，期望获得满分。

#include <iostream>
#include <cmath>

using namespace std;

const int W = 1e5, kW = W + 5; 
const int V = 1e7 + W * 2, kV = V + 5; 
const int kM = 5e7 + 5; 
const int kN = 3e5 + 5; 
const double D = 1.25;
const int L = 1000; 

int n, m, a[kN];
double g, fac[kM], mp[kV], dif[kW]; 
int len, l[L], r[L]; 
double v[L];

double C (int n, int m) {
	return fac[n] - fac[m] - fac[n - m]; 
}

int main () {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> m >> g;
	fac[0] = 0; 
	for (int i = 1; i <= m; ++i) 
		fac[i] = fac[i - 1] + log2(i);
	for (int i = 1; i <= n; ++i)
		cin >> a[i], a[i] += W;
	for (int i = 0; i <= min(m, W); ++i) {
		if ((i ^ m) & 1) continue;
		int c = (i + m) >> 1;
		double p = C(m, c) - m, v = 0; 
		if (p >= -60) v = pow(2, p);
		dif[i] = v; 
	}
	double mx, mi; 
	for (int o = m & 1, tl, tr, i = o; i <= W + 2; i += 2) {
		if (dif[i] * D < mx || i == W + 2 || i == o) {
			if (i != o) {
			  ++len, l[len] = tl, r[len] = tr;
			  ::v[len] = sqrt(mx * mi);
			}
			tl = tr = i, mx = mi = dif[i];
		}
		else {
			tr = i, mi = dif[i];
		}
	}
	auto add = [&](int l, int r, double x) -> void {
		mp[l] += x, mp[r + 2] -= x; 
	}; 
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= len; ++j) {
			add(a[i] - r[j], a[i] - l[j], v[j]);
			add(a[i] + l[j], a[i] + r[j], v[j]); 
		} 
	}
	for (int i = 2; i < V; ++i)
		mp[i] += mp[i - 2];
	int ans = 0; 
	for (int i = 0; i < V; ++i)
		ans += mp[i] >= g;
	cout << ans << '\n';
	return 0; 
}