MOCK NOIP+ 20221203 日志

还是张隽恺一如既往的恶趣味。

明显是嘲讽水平不及他的选手。

简略题解

A – 计数

每一次遇到排列问题，我都试着建出一张 $n$ 个点 $n$ 条边的图（$x\rightarrow p_x$）后在上面思考。遗憾的是本题不能这样做。

记排列 $p$ 的逆为 $p^{-1}$，则有 $p=p^{-1}\lor (p\neq p^{-1}\land (p^{-1})^{-1}=p)$。

这是显然的：一个置换的逆元就是将其上下两行交换。故而我们可以计算出有多少个 $n$ 阶排列 $p=p^{-1}$，则 $n!$ 减去计数再除以二即为所求。

易得 $p=p^{-1}$ 的充要条件是 $p_{p_x}=x$，则可以视作每两个元素一对构成 $p_x=y,p_y=x$ 的形式，或者 $p_x=x$。记 $f(n)$ 表示 $p=p^{-1}$ 的 $n$ 阶排列数量，易得转移 $f(n)=f(n-1)+(n-1)f(n-2)$，边界有 $f(1)=1,f(2)=2$。时间复杂度 $\newcommand\bigO{\operatorname{O}}\bigO(n)$。

注意：本题条件下不一定存在 $2$ 的乘法逆元，故而记 $f'(n)$ 表示 $\frac{f(n)}{2}$ 来转移。

B – 点分治

可以发现这棵树就是树状数组展开后的样子。有 $x\ (x\in(0, 2^n))$ 的父亲为 $x-\operatorname{lowbit}(x)$。则两节点 $x,y$ 的 $\operatorname{lca}=x\ \operatorname{and}\ 2^{\log_2(x\oplus y)+1}$，即 $n$ 位二进制表示的最长公共前缀后补零。则统计固定距离的节点个数，可以钦定给定节点 $x$ 二进制表示的某一以 $1$ 结尾前缀作为最近公共祖先，后边选若干位置任填 $1$ 即可（应当减去非法情况）。

时间复杂度 $\bigO(n+\sum{k_i})$。

C – 博弈

记 $L=\sum_{i=1}^{n}l_i$。可知任何一种填完恰好 $k$ 个格子后游戏结束的方案，出现的概率均为 $\frac{1}{L^{\underline{k}}}$。

我们枚举在哪一行结束了游戏，记其编号为 $i$。假若 $1\sim i-1$ 行填写了 $k_1$ 个格子（每一行均未填满），记有 $f(i-1,k_1)$ 种选择；$i+1\sim n$ 行填写了 $k_2$ 个格子，记有 $g(i+1,k_2)$ 种选择。则一共填写了 $s=k_1+k_2+l_i$ 格；又因为本题权值为拼接字符串表示的十进制数，且是“按照顺序依次填写”，则记 $h'(s,k)$ 表示按序填写 $s$ 个字符串，择取其中 $k$ 个以任意顺序摆放拼接，且第 $s$ 个字符串一定选中的权值总和，答案即为 $$\sum_{i=1}^{n}\sum_{k_1=0}^{\sum_{j=1}^{i-1}l_j-1}\sum_{k_2=0}^{\sum_{j=i+1}^{n}l_j-1}\frac{f(i-1,k_1)g(i+1,k_2)(k_1+k_2)!h'(l_i+k_1+k_2,l_i)}{L^{\underline{l_i+k_1+k_2}}}$$

$f,g$ 的计算都是简单的背包，复杂度 $\bigO(n^3)$；思考如何快速计算 $h’$。

场上我试图维护“所有可能的结果字符串”的各项信息，同时直接计算暴力插入一个字串 $t_i$ 的贡献（记 $t_i$ 表示的十进制数为 $a_i$，则插入后的数可以拆分成 $\text{原数更高位}\times 10^{|t_i|+|\text{原数更低位}|}+a_i\times 10^{|\text{原数更低位}|}+\text{原数更低位}$，维护每个串在所有位置劈开得到的“高位”和“低位”权值和），但发现式子首项无法用线性方式维护插入 $a_i$ 之后的贡献。

何钒佑教给我们一更聪明的贡献方法：将每一个字串的贡献独立，写作 $\sum a_i\times10^{|结果串更低位|}$。具体地，对于一个由 $j$ 个串拼接而成的的结果串，我们将其复制成 $j$ 份；对于第 $k$ 份，我们预留第 $k$ 位作为一个“窗口”。若要将串 $t_i$ 填入，我们既可以填入窗口右侧，此时对权值积的贡献为 $10^{|t_i|}$；也可以占用窗口本身而计算 $a_i\times \sum \text{低位权值积}$；也可以填入窗口左侧，贡献不变。容易验证，它的和不重不漏地计算了每一个串的每一位代价；指数相加结果相乘，它具有结合律。于是记 $h(i,j,k,b)$ 表示考虑了 $t_{1},\cdots,t_i$，择其中 $j$ 个拼接，且在窗口下方已经填入 $k$ 个串，窗口是否被占用（$b$）的权值总和；转移时做些处理，就能计算 $h'(i,j)$。

时间复杂度 $\bigO(n^3)$，常数大。

D – 最优化

最小费用增广流。