专栏文章

题解：P7099 [yLOI2020] 灼

CCryn_Frog195
P7099题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minggwuh
此快照首次捕获于
2025/12/02 02:01
3 个月前
此快照最后确认于
2025/12/02 02:01
3 个月前
查看原文

题意

给定 nn 个陷阱（坐标 xix_i），qq 只穿山甲在这些陷阱之间（坐标 yiy_i，按从小到大顺序给出，穿山甲与陷阱在同一坐标就会被抓住）等概率向左或向右随机游走，救援队问你他们穿山甲期望多久会被陷阱抓住，以确认他们的决策。

高斯消元做法

我们把坐标 yy 时期望设成 fif_i，得出 fi=12(fi−1+fi+1)+1f_i = \frac{1}{2}(f_{i - 1} + f_{i + 1}) + 1，这就导致转移出现环，移向得 12fi−1−fi+12fi+1=−1\frac{1}{2}f_{i - 1} - f_i + \frac{1}{2}f_{i + 1} = -1。
直接用高斯消元是 O⁡(n3+q)\operatorname{O}(n^3 + q) 的，能拿 5050 分，而由于矩阵中只有 fi−1,fi,fi+1,fV+1f_{i - 1},f_i,f_{i + 1},f_{V + 1} 不为 00，考虑从上往下消元时只需要消下一行和上一行，可以得到 O⁡(nlog⁡n+q)\operatorname{O}(n\log n + q) 或 O⁡(n+q)\operatorname{O}(n + q) 的做法并得到 7070 分。

打表与结论

这个时候套路已经结束，此时可以试图用 7070 分做法找结论，可以发现若穿山甲在距离为 dd 的两个陷阱之间，里较近的陷阱距离为 kk 时答案为 k(d−k+1)k(d - k + 1)。
证：
由于 12fi−1−fi+12fi+1=−1\frac{1}{2}f_{i - 1} - f_i + \frac{1}{2}f_{i + 1} = -1，乘上 22 得到 fi−1−2fi+fi+1=−2f_{i - 1} - 2f_i + f_{i + 1} = -2，即 (fi+1−fi)−(fi−fi−1)=−2(f_{i + 1} - f_i) - (f_i - f_{i - 1}) = -2，也就是说二阶差分固定，又因为零点为整点，故一阶差分为一次函数 y=−2xy = -2x。
我们知道一阶差分为一次函数时原数组求积可得到二次函数，这就意味着 fi=ak2+bk+cf_i = ak^2 + bk + c，可以解得 a=−1a = -1。
我们将 kk 的定义范围扩展为到其中一点的距离，不需要最小，在 k=0k = 0 与 k=l+1k = l + 1 时得到取值为 00，解得 fi=−k(k−l−1)=k(l−k+1)f_i = -k(k - l - 1) = k(l - k + 1)，注意原题需要取模，这样问题就解决了。

code

CPP
#include<bits/stdc++.h>
using namespace std;
int n,q,x[100009],pl[5000009],f[100009][4];//f[i][0] = g[i][i - 1],f[i][1] = g[i][i],f[i][2] = g[i][i + 1],f[i][2] = g[i][N + 1];
const int mod = 998244353;
int fp(int x,int y){
	if(x == 0)
		return 0;
	if(y == 0)
		return 1;
	int t = fp(x,y >> 1);
	t = 1ll * t * t % mod;
	if(y & 1)
		t = 1ll * t * x % mod;
	return t;
}
int main(){
	scanf("%*d %d %d",&n,&q);
	for(int i = 1; i <= n; i ++){
		scanf("%d",&x[i]);
	}
	sort(x + 1,x + n + 1);
	if(x[n] <= 100000){//这里时70分部分分部分，赛场上用 if 将对应部分分分开处理有利于防掉大分。
		for(int i = x[1]; i <= x[n]; i ++){
			int o = lower_bound(x + 1,x + n + 1,i) - x;
			if(x[o] == i){
				f[i][1] = 1;
			}
			else{
				f[i][0] = (mod + 1) >> 1,f[i][1] = mod - 1,f[i][2] = (mod + 1) >> 1,f[i][3] = mod - 1;
			}
		}
		for(int i = x[1]; i < x[n]; i ++){
			int d = fp(f[i][1],mod - 2);
			f[i][1] = 1ll * d * f[i][1] % mod;
			f[i][2] = 1ll * f[i][2] * d % mod;
			f[i][3] = 1ll * f[i][3] * d % mod;
			//printf("%d %d %d %d\n",f[i][0],f[i][1],f[i][2],f[i][3]);
			f[i + 1][3] = (mod + f[i + 1][3] - 1ll * f[i + 1][0] * f[i][3] % mod) % mod;
			f[i + 1][1] = (mod + f[i + 1][1] - 1ll * f[i + 1][0] * f[i][2] % mod) % mod;
			f[i + 1][0] = 0;
		}
		for(int i = x[n]; i > x[1]; i --){
			int d = fp(f[i][1],mod - 2);
			f[i][1] = 1ll * d * f[i][1] % mod;
			f[i][3] = 1ll * d * f[i][3] % mod;
			f[i - 1][3] = (mod + f[i - 1][3] - 1ll * f[i][3] * f[i - 1][2] % mod) % mod;
			f[i - 1][2] = 0;
		}
		int a = 0,b = 0,c = 0,d = 0x3f3f3f3f;
		for(int i = 1; i <= q; i ++){
			int y = 0;
			scanf("%d",&y);
			//printf(" %d\n",f[y][3]);
			a = a ^ f[y][3];
			b = b + (f[y][3] & 1);
			c = max(c,f[y][3]);
			d = min(d,f[y][3]);
		}
		printf("%d\n%d\n%d\n%d\n",a,b,c,d);
	}
	else{
		int l = 1;
		long long a = 0,b = 0,c = 0,d = 9e18;
		for(int i = 1; i <= q; i ++){
			int y;
			long long ret;
			scanf("%d",&y);
			while(x[l + 1] <= y)
				l++;
			if(y == x[l])
				ret = 0;
			else{
				int k = min(y - x[l],x[l + 1] - y);
				int fl = x[l + 1] - x[l] - 1;
				ret = 1ll * k * (fl - k + 1);
			}
			ret = ret % 998244353;
			a = a ^ ret;
			b += ret & 1;
			c = max(c,ret);
			d = min(d,ret);
		}
		printf("%lld\n%lld\n%lld\n%lld\n",a,b,c,d);
	}
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...