专栏文章

TPOI T1 题解

RRegister_int-std=c++14
P13662题解参与者 18已保存评论 17

文章操作

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

当前评论
17 条
当前快照
1 份
快照标识符
@mip3voff
此快照首次捕获于
2025/12/03 05:44
3 个月前
此快照最后确认于
2025/12/03 05:44
3 个月前
查看原文
考察你是否记得 mex⁡\operatorname{mex} 的定义。
由定义，mex⁡\operatorname{mex} 就是补集 min⁡\min，于是可以发现 mex⁡(ql∼r)=min⁡(al−1,br+1)\operatorname{mex}(q_{l\sim r})=\min(a_{l-1},b_{r+1})，也就是说所有排列的权值都是一样的。所以你只需要算权值和方案数再乘起来。
老套路把 ∑l≤rmex⁡(ql,ql+1,⋯ ,qr)\sum_{l\le r}\operatorname{mex}(q_l,q_{l+1},\cdots,q_r) 拆成 ∑k∑l≤r[∀0≤i≤k,i∈{ql,ql+1,⋯ ,qr}]\sum_{k}\sum_{l\le r}[\forall 0\le i\le k,i\in \{q_l,q_{l+1},\cdots,q_r\}]。那么先找出所有确定的数，维护他们的逆排列，枚举 mex⁡\operatorname{mex} 的值，即可算出当前 mex⁡\operatorname{mex} 能填的位置范围、个数，以及哪些区间会对权值造成贡献。时间复杂度 O(n)O(n)。
CPP
#include <bits/stdc++.h>

using namespace std;

typedef long long ll; 

const int MAXN = 2e5 + 10;
const int mod = 998244353;

inline void cadd(int &x, int y) { x += y, x < mod || (x -= mod); }

int T, n, m, a[MAXN], b[MAXN], p[MAXN], q[MAXN], sum, tot;

int main() {
    for (scanf("%d", &T); T--; ) {
    	scanf("%d", &n), *a = b[n + 1] = -1, sum = 0, tot = 1;
    	for (int i = 1; i <= n; i++) p[i] = -1;
    	for (int i = 0; i < n; i++) q[i] = -1;
    	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]) p[i] = a[i];
    	for (int i = 1; i <= n; i++) if (b[i] != b[i + 1]) p[i] = b[i];
    	for (int i = 1; i <= n; i++) if (~p[i]) q[p[i]] = i - 1;
    	for (int i = 0, l = *q, r = *q; i < n; i++) {
    		if (~q[i]) l = min(l, q[i]), r = max(r, q[i]);
    		else tot = (ll)tot * (r - l + 1 - i) % mod;
    		cadd(sum, (ll)(l + 1) * (n - r) % mod);
		}
    	printf("%lld\n", (ll)sum * tot % mod);
	}
}

评论

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

正在加载评论...