专栏文章

题解：P13662 「TPOI-5A」Luminescence

DDeaphetS
P13662题解参与者 3已保存评论 3

文章操作

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

当前评论
3 条
当前快照
1 份
快照标识符
@miogaaip
此快照首次捕获于
2025/12/02 18:43
3 个月前
此快照最后确认于
2025/12/02 18:43
3 个月前
查看原文
首先观察题目，很难不看出 aa 对应的是前缀最小值，bb 对应的是后缀最小值。
那么一个合法的 aa 数组必然是单调不升的，且对于每个 ai<ai−1a_i\lt a_{i-1} 的位置，一定有 qi=aiq_i=a_i。而对于 ai=ai−1a_i=a_{i-1} 的位置，则有 qi>aiq_i\gt a_i 的限制。
同理，一个合法的 bb 数组必然单调不降，且对于每个 bi<bi+1b_i\lt b_{i+1} 的位置，一定有 qi=biq_i=b_i。而对于 bi=bi+1b_i=b_{i+1} 的位置，则有 qi>biq_i\gt b_i 的限制。
另外，考虑数字 00 出现的位置 xx，其会导致 i<xi\lt x 时 ai>0,bi=0a_i\gt 0,b_i=0 且 i>xi\gt x 时 ai=0,bi>0a_i=0,b_i\gt 0。所以有且仅有一个位置会满足 ai=bi=0a_i=b_i=0。
到这里，我们完成了是否存在合法排列的判断。如果只是计算合法排列的数量，我们发现对于每个不确定 qiq_i 的位置 ii，都会有形如 qi>xiq_i\gt x_i 的限制。那么按照这个限制降序排序，根据当前可用的数字个数以及已经用掉的数字个数，很容易根据乘法原理计算出合法的方案数。
接下来考虑题目中给出的权值信息有什么用，可以看出其含义是计算所有区间的 mex\text{mex} 值并求和。
那么考虑枚举 mex\text{mex} 的值，变成对 i=1,2,…,ni=1,2,\dots,n，去计算有多少区间满足 mex=i\text{mex}=i 并乘上贡献进行求和。再采用经典技巧，变成对每个 ii，计算有多少区间满足 mex≥i\text{mex}\ge i 并求和。即利用 x=∑i=1∞[x≥i]x=\sum_{i=1}^{\infty} [x\ge i] 对式子进行拆分。
也就是：∑1≤l≤r≤nMEX(l,r)=∑1≤l≤r≤n∑i=1n[MEX(l,r)≥i]=∑i=1n∑1≤l≤r≤n[MEX(l,r)≥i]\sum_{1\le l\le r\le n}\text{MEX}(l,r)=\sum_{1\le l\le r\le n} \sum_{i=1}^{n} [\text{MEX}(l,r)\ge i]=\sum_{i=1}^{n} \sum_{1\le l\le r\le n} [\text{MEX}(l,r)\ge i]。
对于统计有多少区间满足 mex≥i\text{mex}\ge i，则可以转化成有多少区间包含了 [0,i)[0,i) 在内的所有数，进一步变成考虑 [0,i)[0,i) 内数字出现的最左边位置 LL 和最右边位置 RR，那么对应方案数就是 L(N−R+1)L(N-R+1)（下标从 11 开始）。
到这里好像进行不下去了，我们考虑充分利用题目性质。注意到对于某个 xx，若其没有出现在数组 a,ba,b 中，这就意味着存在一个 <x\lt x 的数出现在了 xx 的左边，且存在一个 <x\lt x 的数出现在了 xx 的右边。分别考虑 a,ba,b 中 <x\lt x 的最大数字出现的位置，以两个位置为左右端点的区间一定是包含 [0,x)[0,x) 在内的所有数的最小区间。否则若存在 [0,x)[0,x) 的一个数 yy 不在这一区间内，那么这个数 yy 一定会作为前缀最小值或者后缀最小值出现在 qq 内，进一步会出现在 a,ba,b 中不在区间内的某个位置，产生矛盾。
于是对于每个 ii，我们可以计算出包含 [0,i)[0,i) 内所有数的最小区间 [L,R][L,R]，从而计算出对应权值。同时我们会发现，对于给定的 a,ba,b，一个合法排列的权值是确定的，于是我们只需计算出对应权值，以及合法排列的方案数就能计算出最终答案。
实现方面，在计算方案数时可以采用双指针来规避排序部分，同时也能完成权值的计算，时间复杂度 O(n)O(n)。
CPP
#include<bits/stdc++.h>
using namespace std;
#define N 200020
#define MOD 998244353
int T,n,a[N],b[N];
int main()
{
	scanf("%d",&T);
	while(T--){
		int flg=1;
		scanf("%d",&n);
		a[0]=b[n+1]=n;
		for(int i=1;i<=n;i++)scanf("%d",&a[i]);
		for(int i=1;i<=n;i++)scanf("%d",&b[i]);
		for(int i=1;i<=n;i++)if(a[i]>a[i-1])flg=0;
		for(int i=1;i<=n;i++)if(b[i]>b[i+1])flg=0;
		int l=1,r=n,m=-1;
		for(int i=1;i<=n;i++)if(b[i]==0)m=i;
		if(m==-1 || a[m]>0 || a[m-1]==0)flg=0;
		if(!flg){
			printf("0\n");
			continue;
		}
		int ans=0,tot=1,lst=n,cnt=0;
		while(l<=r){
			int x=max(a[l],b[r]),t=1ll*l*(n-r+1)%MOD;
			ans+=1ll*t*(lst-x)%MOD,ans%=MOD;
			cnt+=lst-x-1;
			lst=x;
			if(l==r)break;
			if(a[l]>b[r]){
				l++;
				while(a[l]==x && l<=n)l++,tot=1ll*tot*cnt%MOD,cnt--;
			}
			else{
				r--;
				while(b[r]==x && r>=1)r--,tot=1ll*tot*cnt%MOD,cnt--;
			}
		}
		printf("%lld\n",1ll*tot*ans%MOD);
	}
}

评论

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

正在加载评论...