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

明显是嘲讽水平不及他的选手。
简略题解
A – 计数
每一次遇到排列问题,我都试着建出一张 n 个点 n 条边的图(x→px)后在上面思考。遗憾的是本题不能这样做。
记排列 p 的逆为 p−1,则有 p=p−1∨(p=p−1∧(p−1)−1=p)。
这是显然的:一个置换的逆元就是将其上下两行交换。故而我们可以计算出有多少个 n 阶排列 p=p−1,则 n! 减去计数再除以二即为所求。
易得 p=p−1 的充要条件是 ppx=x,则可以视作每两个元素一对构成 px=y,py=x 的形式,或者 px=x。记 f(n) 表示 p=p−1 的 n 阶排列数量,易得转移 f(n)=f(n−1)+(n−1)f(n−2),边界有 f(1)=1,f(2)=2。时间复杂度 O(n)。
注意:本题条件下不一定存在 2 的乘法逆元,故而记 f′(n) 表示 2f(n) 来转移。
B – 点分治
可以发现这棵树就是树状数组展开后的样子。有 x (x∈(0,2n)) 的父亲为 x−lowbit(x)。则两节点 x,y 的 lca=x and 2log2(x⊕y)+1,即 n 位二进制表示的最长公共前缀后补零。则统计固定距离的节点个数,可以钦定给定节点 x 二进制表示的某一以 1 结尾前缀作为最近公共祖先,后边选若干位置任填 1 即可(应当减去非法情况)。
时间复杂度 O(n+∑ki)。
C – 博弈
记 L=∑i=1nli。可知任何一种填完恰好 k 个格子后游戏结束的方案,出现的概率均为 Lk1。
我们枚举在哪一行结束了游戏,记其编号为 i。假若 1∼i−1 行填写了 k1 个格子(每一行均未填满),记有 f(i−1,k1) 种选择;i+1∼n 行填写了 k2 个格子,记有 g(i+1,k2) 种选择。则一共填写了 s=k1+k2+li 格;又因为本题权值为拼接字符串表示的十进制数,且是“按照顺序依次填写”,则记 h′(s,k) 表示按序填写 s 个字符串,择取其中 k 个以任意顺序摆放拼接,且第 s 个字符串一定选中的权值总和,答案即为
i=1∑nk1=0∑∑j=1i−1lj−1k2=0∑∑j=i+1nlj−1Lli+k1+k2f(i−1,k1)g(i+1,k2)(k1+k2)!h′(li+k1+k2,li)
f,g 的计算都是简单的背包,复杂度 O(n3);思考如何快速计算 h’。
场上我试图维护“所有可能的结果字符串”的各项信息,同时直接计算暴力插入一个字串 ti 的贡献(记 ti 表示的十进制数为 ai,则插入后的数可以拆分成 原数更高位×10∣ti∣+∣原数更低位∣+ai×10∣原数更低位∣+原数更低位,维护每个串在所有位置劈开得到的“高位”和“低位”权值和),但发现式子首项无法用线性方式维护插入 ai 之后的贡献。
何钒佑教给我们一更聪明的贡献方法:将每一个字串的贡献独立,写作 ∑ai×10∣结果串更低位∣。具体地,对于一个由 j 个串拼接而成的的结果串,我们将其复制成 j 份;对于第 k 份,我们预留第 k 位作为一个“窗口”。若要将串 ti 填入,我们既可以填入窗口右侧,此时对权值积的贡献为 10∣ti∣;也可以占用窗口本身而计算 ai×∑低位权值积;也可以填入窗口左侧,贡献不变。容易验证,它的和不重不漏地计算了每一个串的每一位代价;指数相加结果相乘,它具有结合律。于是记 h(i,j,k,b) 表示考虑了 t1,⋯,ti,择其中 j 个拼接,且在窗口下方已经填入 k 个串,窗口是否被占用(b)的权值总和;转移时做些处理,就能计算 h′(i,j)。
时间复杂度 O(n3),常数大。
D – 最优化
最小费用增广流。
