MOCK quasi-PTS 20230209 日志

近一个月来第一次赛时通过一道题。真是可喜可贺。

A – 单调

一开始以为与网络流相关；后来考虑 DP；结果是个贪心或者乱搞。

题意简述

给定长为 $\newcommand\bigO{\operatorname{O}}n\ \ (n\leq 10^5)$ 的序列 $\langle a_i\rangle,a_i\in\{1,2,3\}$。匹配尽可能多的子序列，每个子序列均为 $\langle 1,2,3\rangle$ 或 $\langle 3,2,1\rangle$，且一个位置最多被一个子序列占用。求最大匹配数。

解一

经过了奇妙转化后的贪心。

可以发现，任意位置匹配出两个不交的子序列 $\langle 3,2,3\rangle$ 和 $\langle 1,2,1\rangle$，总是能够合并成为两个合法的子序列并计入答案；同时 $\langle 1,2,1\rangle$ 可以合并任意位置的 $3$ 产生一合法子序列，$\langle 3,2,3\rangle$ 之于 $1$ 亦然。可以分类讨论简单证明。

我们把 $3$ 视作 $1$，并令合法序列为 $\langle 1,2,1\rangle$，匹配尽可能多的子序列。设实际上我们匹配了 $a$ 个 $\langle 1,2,3\rangle$，$b$ 个 $\langle 3,2,1\rangle$，$c$ 个 $\langle 1,2,1\rangle$，$d$ 个 $\langle 3,2,3\rangle$。我们最大化了 $s=a+b+c+d$，实际上我们需要最大化 $$a+b+2\times \min\{c,d\}+\begin{cases} \min\{|\text{实际未被匹配的 3}|,c-d\},&(c\geq d)\\ \min\{|\text{实际未被匹配的 1}|,d-c\}&(d>c) \end{cases}$$

考虑条件语句内的取值情况。以 $c\geq d$ 时为例。若取 $c-d$ 为 $\min$，说明我们将 $\langle 1/3,2,1/3\rangle$ 形式的子序列匹配数量最大化，这是将 $\langle 1,2,3\rangle,\langle 3,2,1\rangle$ 匹配数量最大化的充分条件；若取“实际未被匹配的 $3$ 的数量”为 $\min$，则说明我们已经使用完了本序列中所有 $3$ 元素，而一个合法子序列至少需一个 $3$，故亦达到上限。故我们取 $\min\{\text{cnt}(3),\text{cnt}(1),1\}$，就是最终答案。

我们二分转化后匹配了多少个 $\langle 1,2,1\rangle$。若匹配了 $s$ 个，则选取序列首 $s$ 个 $“1”$ 和末 $s$ 个 $“1”$ 分别作为子序列的头和尾，易得此时 $2$ 的选取具有完全的决策包容性。最后构造方案时按照上文方法合并、转化即可。时间复杂度 $\bigO(n\log n)$。

解二

反悔贪心，正确性难以证明且不易在赛场上正确实现，故此处略去。

B – 期望

题意简述

下文约定质数常数 $p=10^9+7$，$\newcommand\ZmpZ{\mathbb{Z}/p\mathbb{Z}}\ZmpZ$ 即整数模 $p$ 域。

给定一棵以 $1$ 为根的大小为 $n$ 的树。有一未知的权值序列 $\langle a_1, a_2,\cdots,a_n\rangle,{\color{red}a_i\in \ZmpZ}$。现给定整数常数 $k,0\leq k<p,{\color{red}2\nmid k}$。我们生成一长为 $k$ 序列 $\langle b_i\rangle$，满足 $b_i$ 在 $1,\cdots,n$ 中等概率随机选取。定义一长为 $n$ 的序列 $\langle c_x\rangle$，满足 $$c_x=\begin{cases} \prod_{i=1}^k a_{b_k},&(x=\operatorname{lca}(b_1,\cdots,b_k))\\ 0&(\text{otherwise}) \end{cases}$$

现在，给定 $\langle E(c_x)\rangle$，即 $c_x$ 的期望构成的序列。请求出在整数域意义下 $a_1$ 的最小值，或报告无解。

题解

离考试结束还有半小时的时候瞟了一眼。

不难得到，$c_x$ 是 $k$ 个权相乘的形式，当且仅当选择的这 $k$ 个节点全部在 $x$ 的子树中（含 $x$），且没有聚集在同一个儿子的子树内。那么，对于节点 $x$，所有情况下 $c_x$ 之和具有了组合意义：我们任意选取 $k$ 个可重的节点，将其权值之积累加，其等于 $(a_{v_1}+a_{v_2}+\cdots+a_{v_t})^k=S_x^k$，其中 $v$ 取遍 $x$ 子树中所有节点，$S_x$ 为 $x$ 子树内所有节点的权值之和；再减去不合法方案权值总和——枚举 $x$ 的儿子 $y$，同理可得应减去 $S_y^k$。再将“期望”序列转化成所有情况的权值和，得到 $$E(c_x)n^k=S_x^k-\sum_{y\text{ is a son of } x\text{’s}}S_y^k$$

于是我们可以由上述递推关系求出所有节点 $x$ 的 $S_x^k$。

然后我傻眼了。我记得当 $k>1$ 时，在 $\ZmpZ$ 上 $a^k\equiv b$ 是多解……于是似乎并不能递归求出 $a_x$（先求出叶子结点；再向父亲的 $S_{\text{fa}}$ 合并）。遗憾地打了 $\text{10 pts}$ 暴力跑路。

引理 1 – $k$ 次剩余

若有变量 $a$ 及常数 $b$，$a,b\in(\ZmpZ)^{\color{red}\times}$，则 $a^k\equiv b$ 或者无解，或者有 $\gcd(k,\varphi(p))=\gcd(k,p-1)$ 个不同根。

证明

记 $(\ZmpZ)^{\times}$ 的生成元为 $g$。将上式转写为 $(g^c)^k\equiv g^f$，于是要求 $ck\equiv f\pmod{p-1}$。若 $\gcd(k,p-1)\mid f$，则由线性同余方程相关知识得到共有 $\gcd(k,p-1)$ 个解；否则该方程无解。$\square$

对 $p-1$ 分解质因数，发现它等于 $2\cdot (5\times 10^8+3)$。又由于 $2\nmid k$，于是当 $k\neq 5\times 10^8+3$ 时，必然有 $\gcd(k,p-1)=1$，由上文结论可知此时任意元素 $a,a\in\ZmpZ$ 均有唯一的 $k$ 次方根！

当 $k\neq 5\times 10^8+3$

我们不必每次都用大步小步算法计算 $k$ 次方根：由于其唯一，故我们直接对两边取 $\frac{1}{k}$ 次方，得到 $a_x\equiv b^{\frac{1}{k}\bmod{p-1}}$（注意指数在 $\mathbb{Z}/(p-1)\mathbb{Z}$ 上）。之后从叶子向根依次合并即可。使用快速幂和扩展欧几里得算法，时间复杂度 $\bigO(n\log p)$。

当 $k=5\times 10^8+3$

我们改写 $S_1$ 的递归定义式子，得到 $a_1=S_1-\sum_{y\text{ is a son of }x\text{’s}} S_y$。

若有 $k=\frac{p-1}2$，则由上文可得，当且仅当 $b\equiv \pm 1\quad (1\equiv g^{p-1}, -1\equiv g^{\frac{p-1}2})$（由欧几里得引理可以得到，$m$ 为奇素数时 $\mathbb{Z}/m\mathbb{Z}$ 上 $a^2\equiv 1$ 有且仅有 $a\equiv\pm 1$ 两个解，于是必然有 $(-1)^2\equiv 1\iff -1\equiv g^{\frac{m-1}2}$）时，$a^k\equiv b$ 才有解；特别地，若 $b\equiv 0$，则 $a\equiv 0$。

当 $b\equiv 1\equiv g^{p-1}$ 时，引理 1 中的线性同余方程可以写作 $c\frac{p-1}2\equiv 0\pmod{p-1}$。于是 $c$ 可以取任意偶数，使得 $a\equiv g^c, a^k\equiv b$；同理，$b\equiv -1$ 时，可取任意奇数 $c$ 使得 $(a=g^c)^k\equiv b$。

现在回到 $a_1=S_1-\sum_{y\text{ is a son of }x\text{’s}} S_y$ 上来。我们剔除所有 $S_v^k=0$ 的项，检查是否存在 $S_v^k\neq \pm 1$。若是，则该组数据无解。否则我们试图在整数域上最小化 $a_1$。

以下所有证明，感谢李枨夏（L7-56）点拨思路。

引理 2

对于 $a,a\in(\ZmpZ)^{\times}$，若 $a\equiv g^c$，且 $-a\equiv g^d,a^{-1}\equiv g^e$，则 $c\equiv e\pmod{2},c\not\equiv d\pmod{2}$。

容易由 $-1\equiv g^{\frac{p-1}2},1\equiv g^{p-1}$ 且 $\frac{p-1}2=5\times 10^8+3\equiv 1\pmod{2}$ 得证。

引理 3

对于任意常数 $z\in(\ZmpZ)^{\times}$（注意 $z$ 非 $0$）、$u,v\in\{0,1\}$，以及变量 $c,d$，且满足 $c\equiv u\pmod{2},d\equiv v\pmod{2}$，总能找到合适的 $c,d$，满足 $g^c+g^d\equiv z$。

证明

设 $\alpha$ 为任意不为 $1$ 的 $(\ZmpZ)^{\times}$ 内元素。令 $z\equiv g^e$，我们试图构造 $g^c\equiv \alpha g^e\equiv g^{e+t},g^d\equiv(1-\alpha) g^e\equiv g^{e+r}$。

如果 $c,d$ 均与 $e$ 奇偶性相异，则需要满足 $\alpha\equiv g^t,-\alpha\equiv g^r,-\alpha+1\equiv g^s$，其中 $t\equiv s\equiv 1\pmod{2}$，由引理 2 得到 $2\mid r$。于是我们要求 $-\alpha$ 和 $-\alpha+1$ 由原根次幂表示时，指数奇偶性依次为偶、奇；又由于 $g$ 的偶次幂、奇次幂分别生成 $\frac{p-1}2$ 个 $(\ZmpZ)^{\times}$ 中元素，且 $1=g^{p-1},2\mid p-1$，则由抽屉原理得到一定存在该 $\alpha$。

同理，如果 $c,d$ 中有一个与 $e$ 奇偶性相异，则要求存在次幂为“偶/偶”或“奇/奇”的邻项 $-\alpha,-\alpha+1$；若 $c,d$ 均与 $e$ 奇偶性相同，则要求存在“奇/偶”式的邻项。在 $p=10^9+7$ 的条件下，这两种分界都是存在的（$1,2,3,4$ 均是 $g$ 的偶次幂，故“偶/偶”分界存在；而有最小原根 $g=5$，所以再次应用抽屉原理得到“奇/偶”分界存在）；故而我们总是可以构造出合法的方案，使得原式成立。$\square$

那么，假设存在 $l,l\geq 3$ 个及以上的非零 $S_v^k$（对于 $v\neq 1$，我们根据引理 2 反转其符号，得到 $(-S_v)^k=-S_v^k$），我们取其中 $l-2$ 个求出其任意根求和（并使和不为 $0$。由于每个 $S_v$ 的根的多样性，这是一定存在的），然后将剩余 $2$ 个 $S_v^k$ 按照引理 3 构造一组解，使得其和为前述和的相反数即可；

当 $l=2,1,0$ 时，我们根据 $S_v^k$ 的符号分类讨论，求出最优解即可。时间复杂度 $\bigO(n+\log p)$。

C – 背包

题意简述

给定 $n$ 件物品，体积分别为 $v_1,v_2,\cdots,v_n$；现要恰好装满一容量为 $m$ 的背包（$n,m\leq 5000$）。求在使用物品数 $c$ 最少的方案中，以下各项数据的最小值：

1. $c$ 件物品体积平均值；
2. 按体积从小到大排序，第 $\lfloor\frac{c+1}{2}\rfloor$ 件物品的体积（中位数）；
3. $c$ 件物品体积的极差；
4. 记该 $c$ 件物品的体积的众数为 $t$，$t$ 出现的次数。

题解

第一问答案为 $\frac{m}{c}$。

考虑将 $n$ 件物品排序后依次转移。我们设 $f(i,x)$ 为一个二元组 $(d,s)$，表示考虑了前 $i$ 件物品的取舍，体积和为 $x$ 的所有方案中，满足 $d$ 最小的情况下，首个放入背包的物品的大小 $s$ 为何。转移时以 $d$ 为第一关键字，$s$ 为第二关键字。每当我们成功从 $f(i,m-v_{i+1})=(d,s)$ 转移到 $f(i+1,m)=(d+1,s)$ 时，若全局答案 $c$ 产生更新，则直接采用 $v_{i+1}-s$ 作为新的最小极差；否则若 $d+1=c$，尝试更新极差为 $v_{i+1}-s$。第三问解完。

若第二问的答案为 $v_i$，则一定存在至少一个最优解的转移路径，经过了 $f(i-1,x-v_i)\rightarrow f(i,x)$（$x$ 取任意体积），同时有 $f(i,x)=(\frac{c+1}2,?)$。则我们以 $\bigO(nm)$ 的空间记录转移路径，由所有最优解作为起点逆推回去即可。第二问解完。

至此我们以 $\bigO(nm)$ 的时间和空间解完前三问。我们发现“存在一条最优解转移路径，对于不同的体积大小，均使用不超过 $t$ 个物品”关于 $t$ 有0/1单调性。于是二分 $t$，使用多重背包结合单调队列快速进行带线性限制的转移。时间复杂度 $\bigO(nm\log n)$，但由于内存访问连续性、局部性强（可以 $\bigO(m)$ 逐层存储状态），实际表现非常优秀。