模拟赛题解/2025.9.8 模拟赛

T1-入门题（basic）

题面

对于一个长度为 $k$ 的序列 ，我们称其是 $\text{mex}$ 序列当且仅当对于每一个 $1\leq i\leq k$，都满足 $|a_i-\text{mex}(a_1,a_2\cdots,a_i)|\leq1$。

给定一个长度为 $n$ 的序列 ，求其有多少个非空子序列是 $\text{mex}$ 序列，答案对 $10^9+7$ 取模。

$1\leq n\leq 10^6,1\leq a_i\leq 10^6$。

题解

注意到实际上一个点 $x$ 要出现在子序列中，加入前的 $\text{mex}$ 只有 $x+1,x,x-1$ 三种可能性。

于是设计状态 $f_i$ 表示 $\text{mex}=i$ 时，满足条件的非空子序列数量。

然后注意到从 $x-1$ 转移只可能出现一次，且之后只能从 $x-1$ 转移。

所以将状态更改为 $f_{0/1,i}$ 表示是否已经出现过该转移，转移式是显然的。

复杂度 $O(n)$。

T2-人门题（basis）

题面

给定一个长度为 $n$ 的序列 $a$，以及一个长度为 $m$ 的序列 $b$。

定义一次操作过程如下：

• 选择集合 $S\subseteq\{1,2,\cdots,n\}$。
• 对于每个 $x\in S$，令 $a_x\leftarrow a_{b_x}$。

问最少需要多少次操作才能使序列 $a$ 变为单调不降的序列，若无解输出 。

$1\leq n,m\leq10^6,1\leq a_i,b_i\leq m$。

题解

发现答案是最小化最大操作次数，考虑二分答案。考虑如何判断一个 $x$ 是否可以作为答案。

有一个显然的贪心策略，直接求出每个位置可以在 $x$ 步内变成哪些值，然后每次取出这些值里面比上一个位置大的最小值作为这个位置修改后的值，然后继续检查下一个位置。

考虑稍稍修改一下这个贪心，即我记一个指针表示当前这个位置至少要达到多少，若可以在 $x$ 步内达到，则继续检查下一个位置，若不可以，则指针的值加一，然后继续检查。

预处理一下即可做到 $O(n + m)$ 回答单个 $x$，于是总复杂度 $O((n + m)log_2m)$。

T3-

题面

给定一个长度为 $n$ 的序列 $a$。

定义一次操作过程为选择一个位置 $i \ (1 \leq i \leq n)$，令 $a_i \leftarrow a_i + 1$。

有 $q$ 次询问，每次给出一个区间 $[l,r]$，问至少需要多少次操作才能使得区间 $[l,r]$ 成为整个序列唯一的最大子段和。

如果无论如何操作，$[l,r]$ 都不可能成为整个序列唯一的最大子段和，输出 $-1$。

由于我们认为不选子区间是一种和为 $0$ 的方案，所以要求唯一的最大子段和最后是大于 $0$ 的。

$1\leq n\leq 5\times10^5,|a_i|\leq10^9$。

题解

考虑无解情况。

无解时，一定存在除去 $[l,r]$ 区间后一个前缀区间的后缀或一个后缀区间的前缀满足区间和为正数。

直接用线段树维护 $[1,l-1]$ 和 $[r+1,n]$ 的最大前/后缀即可。

记 $M$ 为原序列的最大子段和。

考虑区间内部，若存在一个区间 $[L,R]$ 满足 $l<L,R<r$，并且 $\sum_{i=L}^Ra_i=M$，则需要首尾各额外 $+1$，防止内部出现其他区间满足最大子段和，不满足唯一性。

如果外部有其他的区间，则额外 $+1$， 满足唯一性。

复杂度 $O(n\log n)$。

T4-

题面

定义作用于 $\{1,2,\cdots,n\}$ 上的满足结合律的运算 $\oplus$ 满足 $a\oplus b\in\{a,b\}$。

给定 $m$ 个限制，每个形如 $a\oplus b=x,x\in\{a,b\}$。

定义一个元素 $1\leq x\leq n$ 为交换子，当且仅当 $\forall1\leq y\leq n,x\oplus y=y\oplus x$。

对于每一个满足条件的运算 $\oplus$，记其交换子的数量为 $k$。求所有满足条件的 $\oplus$ 运算所对应的 $2^k$ 的和，对 $998244353$ 取模。

$1\leq n\leq17,1\leq m\leq n^2$。

题解

令 $U=\{1,\cdots,n\}$，定义如下二元关系：

• $a_1b$ 表示 $a\oplus b=a,b\oplus a=b$。
• $a\sim_2b$ 表示 $a\oplus b=b,b\oplus a=a$。
• $a\sim b$ 表示 $a\sim_1 b$ 或 $a\sim_2 b$。
• $a\preceq b$ 表示 $a\oplus b=a$ 或 $b\oplus a=a$。

引理 1.$\sim$ 是一个等价关系。进一步地，$\sim$ 划分出的每个等价类 $A$ 中，要么 $\forall a,b\in A,a\sim_1b$，要么 $\forall a,b\in A,a\sim_2b$。

证明. 自反性和对称性显然，下面验证传递性。设 $a\sim b,b\sim c$。不妨设 $b\not\in\{a,c\}$。

• 若 $a\sim_1 b,b\sim_1 c$，则 $a\oplus c=(a\oplus b)\oplus c=a\oplus (b\oplus c)=a$，同理 $c\oplus a=c$，因此 $a\sim_1 c$。
• 若 $a\sim_2 b,b\sim_2 c$，类似地可以证明 $a\sim_2 c$。
• 若 $a\sim_1 b,b\sim_2 c$，则 $(b\oplus c)\oplus (a\oplus b)=c\oplus a\in {a,c}$，但另一方向，$(c\oplus a)\oplus b$ 无 论 $c\oplus a$ 是 $c$ 还是 $a$，最终都得到 $b$，矛盾。
• 若 $a\sim_2 b,b\sim_1 c$，则 $c\oplus (a\oplus b)=b\sim_2 c$，矛盾。

注记 1. $a\sim b\Leftrightarrow a\preceq b and b\preceq a$。因此 $\preceq$ 可以被投影到 $U/\sim$ 上。

引理 2. $\preceq$ 是偏序，且 $U/\sim$ 上，$\preceq$ 定义了一个全序。

证明. 证明预序。自反性显然，考虑传递性。设 $a\preceq b,b\preceq c$。

• 若 $a\sim b,b\sim c$，则在 $\text{Lemma}\,1$ 中已被证明。
• 若 $a\sim_1 b,b\sim_2 c$（换言之，$b\oplus c=c\oplus b=b$）：

​ – 若 $a\sim_1 b,a\oplus c=(a\oplus b)\oplus c=a\oplus (b\oplus c)=a\oplus b=a$。

​ – 若 $a\sim_2 b,a\oplus c=c\oplus (b\oplus a)=(c\oplus b)\oplus a=b\oplus a=a$。

• 若 $a\sim_2 b,b\sim_1 c$：

​ – 若 $a\sim_1 b,c\oplus a=(c\oplus b)\oplus a=c\oplus (b\oplus a)=c\oplus b=c$。

​ – 若 $a\sim_2 b,c\oplus a=(b\oplus c)\oplus a=b\oplus (c\oplus a)=b\oplus a=a$。

• 若 $a\preceq b,b\preceq c$，则 $a\preceq c$。 证明 $\preceq$ 是序关系后，全序显然。

于是我们直接 $\text{DP}$ 即可，枚举每次加入的等价类，复杂度 $O(3^n)$，然后用 $\text{FMT}$ 优化 一下即可做到 $O(n^32^n )$。