题解：[[2024.10.7 模拟赛]] ## 我是 A 题 #容斥 #三维偏序 #排序 给定 $A,B,C$，有一些不重复三元组 $(a,b,c)$ 满足 $a\in [1,A],b\in[1,B],c\in[1,C]$。定义三元组 $(a,b,c)$ 不大于 $(u,v,w)$ 当且仅当 $a\le u,b\le v,c\le w$。有 $n$ 次操作，每次给出三元组 $(u,v,w)$，将现存三元组当中不大于 $(u,v,w)$ 的删除。输入方式如下： $ \begin{aligned} & \textbf{function }Rand(\textbf{arg: }k1(\text{reference}),k2(\text{reference})): \\ & ~~~~\textbf{var }k3\gets k1,k4\gets k2 \\ & ~~~~k1\gets k4 \\ & ~~~~k3\gets k3\oplus(k3\operatorname{\textbf{shl}}23) \\ & ~~~~k2\gets k3\oplus k4\oplus(k3\operatorname{\textbf{shr}}17)\oplus(k4\operatorname{\textbf{shr}}26) \\ & ~~~~\textbf{return }k2+k4\\ & \\ & \textbf{procedure }GetData(\textbf{none}): \\ & ~~~~\textbf{var }x,y \\ & ~~~~\textbf{read } n,A,B,C,x,y \\ & ~~~~\textbf{for }\textbf{var }i\in[1,n]:\\ & ~~~~~~~~u_i\gets Rand(x,y)\bmod A+1 \\ & ~~~~~~~~v_i\gets Rand(x,y)\bmod B+1 \\ & ~~~~~~~~w_i\gets Rand(x,y)\bmod C+1 \\ & ~~~~~~~~u_i\gets A\textbf{ if }Rand(x,y)\equiv0\pmod 3 \\ & ~~~~~~~~v_i\gets B\textbf{ if }Rand(x,y)\equiv0\pmod 3 \\ & ~~~~~~~~w_i\gets C\textbf{ if }u_i\ne A\textbf{ and }v_i\ne B\\ \end{aligned} $ ## 我是 B 题 #概率dp #概率与期望 有 $n$ 个质量分别为 $1\sim n$ 的物品需要经过 $n$ 道质检工序。 每一轮工序会收到上一轮传过来的所有物品并开始质检，第 $i$ 道工序流程如下： - 如果此时该道工序处只剩下一个物品，那么机器会将其粉碎。 - 如果此时该道工序处剩下了不止一个物品，那么机器会将质量最小的物品挑出来，以 $p_i$ 的概率将其粉碎，$1-p_i$ 的概率放过它并将其传给下一道工序。如果 机器放过了本次选择的物品，那么重新执行该流程直到粉碎某一个物品。 求最后剩下的物品质量的期望，答案对 $10^9+7$ 取模。 ## 我是 C 题 #递归 #分治 有长度为 $n$ 的整数数列 $a,b$，需要求出最大的 $k$，满足序列 $a$ 当中存在区间 $[i,i+k-1]$，使得区间内出现过的所有数出现次数都不小于 $b_k$。 ## 我是 D 题 #线段树 若有一个长度为 $n$ 的数列 $a$ 满足 $\forall a_i \in[1,m]$，定义 $f(a)$ 为数列中所有极长相等子段长度的平方和。 现在给出长度为 $n$ 的数列 $b$，满足 $\forall b_i\in [0, m]$，$b_i=0$ 表示 $b_i$ 的取值在 $[1,m]$ 中均匀随机。 有 $q$ 次操作，每次修改数列 $b$ 中的一个值，或者询问 $f(b_l\sim b_r)$ 的期望对 $998244353$ 取模后的结果。