【题解】2025 赛季 XCPC 金牌题鉴赏
这赛季又摄金失败了，写点题解来麻痹一下自己。
我自身还是比较迷茫的，不知道明年是否还需投入今年以来这么多精力。
很对不起队友，这赛季我没能有很亮眼的发挥。
原本这里应该有很多内容，但被我鉴定为批话就删掉了。
作为选手参与了 IC 西安，IC 武汉，CC 哈尔滨三个赛站，就线下体验来说哈尔滨 > 武汉 > 西安。
武汉的主要问题是食堂离赛场太远，校内没有任何供校外人员使用的交通工具，去一趟就走近半小时。西安的主要问题是学校周围都是荒地，酒店还没抢到校内，走路去赛场单程 50min，不幸中的万幸是外卖还能送到酒店门口。哈尔滨体验十分好，如果不是去年 nefu 闹的大瓜外加天寒地冻，应该会有很多强队来旅游罢。
下面大部分是金牌题，也混有少部分在我看来较为困难的银牌题。如果屏幕前的你对其中某一题有更为深刻的想法，欢迎 QQ 与我交流，我将不胜感激。
ICPC 西安
M. Mystique as Iris
结论题。若 \(\{a\}\) 中存在值在 \([2,n-1]\) 中的元素，\(\{a\}\) 必然是神秘的。
证明使用归纳法，若存在 \(a_i\ge 3\)，则可以将 \(a_i\) 减一，序列长度减一。故只用证 \(n\ge 3\) 且序列中存在 \(a_i=2\) 的情况。若 \(n=3\)，显然是神秘的。对于 \(n>3\)，可以狗咬狗转化为 \(n=3\) 或 \(n=4\)（注意序列中始终保留一个 \(2\)）。\(n=4\) 手玩一下发现也是必定神秘，就得证了。
将 \(\ge n\) 的元素看作 \(\infty\)，现在只剩 “序列由 \(1\) 和 \(\infty\) 构成” 的情况。首先若 \(a_1=1\) 或 \(a_n=1\)，\(\{a\}\) 也必定神秘，因为可以另一侧狗咬狗只剩 \(\{1,x\}\)。一种特殊情况是序列全为 \(1\)，且 \(n\) 为奇数，要特判掉。
接着，如果序列中有连续两个 \(1\)，可以在这两个 \(1\) 中间划一刀分成两个序列，两个序列要么头有 \(1\) 要么尾有 \(1\)，规约到上一段的情况，是神秘的。
容斥，对不神秘的序列计数，问题转化为：对每个 \(-1\)，填 \(1\) 有一种情况，填 \(\infty\) 有 \(\max(m-n+1,0)\) 种情况，问有多少个序列头尾为 \(\infty\) 且没有两个相邻的 \(1\)。
令 \(dp[i][0/1]\) 表示填完前 \(i\) 个数，最后一个数为 \(1/\infty\) 的方案数，容易转移。时间复杂度 \(O(n)\)。
C. Catch the Monster
手玩一下发现，怪物能逃脱当且仅当出现一个 “一个点挂三条长为 \(2\) 的链” 的结构，并且这个结构是极小的。而不含该结构的图一定是毛毛虫（存在一条链，图上的点到链的距离都 \(\le 1\)）。
令 \(f[x]=\sum\limits_{x\to y}[\text{deg}(y)\ge 2]\)，一张图是毛毛虫的充要条件是 \(\forall x\)，\(f[x]< 3\)。
同时，对于固定的 \(r\)，一定存在一个分界点 \(\text{mnL}[r]\)，满足当 \(l\ge \text{mnL}[r]\) 时，\([l, r]\) 的导出子图是毛毛虫；否则不是。于是，只用对每个 \(r\) 求出 \(\text{mnL}[r]\)，就能 \(O(1)\) 回答询问。因为 \(\text{mnL}[i]\) 单调增，尝试双指针。
考虑朴素的插入/删除一个点的过程，以插入点 \(x\) 为例。设当前双指针为 \(L,R\)，遍历 \(x\) 的每一个在 \([L,R]\) 里的邻居 \(y\)，将 \(\text{deg}(x)\) 和 \(\text{deg}(y)\) 自增，若 \(\text{deg}(x)/\text{deg}(y)\) 自增后为 \(2\)，则将 \(x/y\) 所有 \([L,R]\) 内的邻居 \(z\) 的 \(f[z]\) 自增。容易遗漏的是：若 \(\text{deg}(y)\) 自增后 \(>2\)，\(f[x]\) 也要自增。
由于每个点只会插入一次、删除一次，遍历 \(y\) 的过程为均摊线性。整个双指针过程，每个 \(x\) 的 \(\text{deg}(x)\) 先增后减最多两次会恰好 \(\text{deg}(x)=2\)，故遍历 \(z\) 的过程也均摊线性。总时间复杂度 \(O(n+q)\)。
K. Killing Bits
必要条件是 \(\forall i\)，\(a_i\) 是 \(b_i\) 的超集，且存在一个 \(0\sim n-1\) 的排列 \(p\) 使得 \(\forall i\)，\(p_i\) 是 \(b_i\) 的超集。
并且这个条件是充分的，感性上可以通过一些交换论证来证明。其中第一个条件可以直接判断，至于第二个条件，一个 naive 的想法是网络流，如果 \(x\) 是 \(y\) 的超集，就连一条 \(x\to y\)，容量为 \(1\) 的边，最后看是否满流。
一个明显的优化是对每个 \(x\)，只连一条 \(x\to x\text{\\}\{2^i\}\)，容量为 \(\infty\) 的边。
这样就能过了，时间复杂度并不会分析。
ICPC 成都
M. Meeting for Meals
先考虑在树上的情况，两个人分别在 \(i,j\)，最大陪伴时间显然是 \(t_\text{meet}-\dfrac{\text{dis}(i,j)}{2}\)，即在路径中点会合。放到图上也是类似的，我们从给定的 \(k\) 个关键点出发跑多源最短路，并为每个点 \(i\) 记录离它最近的关键点编号 \(c[i]\)，这样对于一条边 \((u,v,w)\)，如果 \(c[u]\neq c[v]\)，那这条边上才有可能存在路径中点。
设多源最短路跑出来的距离是 \(d[i]\)，枚举边 \((u,v,w)\) 为路径中点，答案就是 \(t_\text{meet}-\dfrac{d[u]+d[v]+w}{2}\)。
时间复杂度 \(O((n+m)\log m)\)。
I. Inside Triangle
对大凸包上的每个点 \(i\)，求出顺时针方向最远的点 \(p\) 满足 \(\overrightarrow{ip}\) 在小凸包左侧，设为 \(l[i]\)；以及逆时针方向最远的点 \(p\) 满足 \(\overrightarrow{ip}\) 在小凸包右侧，设为 \(r[i]\)。这一步可以用双指针线性求。
设三角形逆时针按顺序编号 \(i,j,k\)，那么 \(j\in [i+1,r[i]]\)，\(k\in [l[i],i-1]\) 且 \(k\in [j+1,r[j]]\)。也就是说 \[ \text{ans}=\frac{1}{3}\sum_{i=0}^{n-1}\sum_{j=i+1}^{r[i]}\{k\mid \max(l[i],j+1)\le k\le r[j]\} \] 至于优化，只用考虑 \(i\to i+1\) 的过程，算一下答案变化量。具体的，设当前 \(j\) 可选集合为 \(B=[B_l,B_r]\)，\(k\) 可选集合为 \(A=[A_l,A_r]\)。当 \(B_r\) 向前走一步，变化量是 \([B_r+1,r[B_r]]\) 与 \(A\) 的交集；当 \(A_r\) 向前走一步，变化量是 \([l[A_r], A_r-1]\) 与 \(B\) 的交集。\(B_l,A_l\) 向前走一步同理，只不过变化量是负的。
写代码的时候要十分小心。时间复杂度 \(O(n+m)\)。
ICPC 武汉
B. 77G Network
很裸的题。“线段树优化建图 + 2SAT” 几乎被出烂了，不再赘述。
唯一的难点是，如何建线段树使得 “\(x\) 的 \(k\) 级儿子” 是一段连续的区间？
bfs 序是很好的选择，那给定 \(x,k\)，如何定位到对应的区间？记录同一深度下所有点的 bfs 时间戳，那我们要找的就是深度 \(\text{dep}[x]+k\) 下，dfs 序在 \([\text{dfn}[x],\text{dfn}[x]+\text{sz}[x]-1]\) 的点对应的区间，二分即可。
时间复杂度 \(O(n+m\log n)\)。
A. Planting Trees
题目等价于求 \[ \sum_{i=0}^{n-1}[(f\cdot i+x)\bmod m< (g\cdot i+y)\bmod m] \] 然后题解就给出了一个神奇的公式（不清楚是否是 well-known 的 trick） \[ [u < v] = 1 + \left\lfloor \frac{v-u-1}{m} \right\rfloor\ \ (0\le u,v<m) \] 将该公式代入，用 \(x\bmod y=x-y\cdot \left\lfloor\dfrac{x}{y}\right\rfloor\) 展开，得到 \[ \text{ans}=\sum_{i=0}^{n-1}1+\sum_{i=0}^{n-1}\left\lfloor\frac{(g-f)\cdot i+(y-x-1)}{m}\right\rfloor+\sum_{i=0}^{n-1}\left\lfloor\frac{f\cdot i+x}{m}\right\rfloor-\sum_{i=0}^{n-1}\left\lfloor\frac{g\cdot i+y}{m}\right\rfloor \] 后三项为 floor_sum 结构，套个板子就好。时间复杂度 \(O(T\log m)\)。
ICPC 南京
H. Pen Pineapple Apple Pen
令 \(f[l][r]\) 表示第一个子串以 \(l\) 结尾，第四个子串以 \(r\) 开头的方案数，\(g[l][r]\) 表示 \([l,r]\) 里存在第二个子串和第三个子串的方案数。 \[ \text{ans}=\sum_{i=1}^{n}\sum_{j=i+1}^{n}f[i-1][j+1]\cdot g[i][j] \] 再令 \(h[l][r]\) 表示第三个子串以 \(r\) 结尾，且与第三个子串相同的第二个子串的后缀以 \(l\) 开头的方案数。
\[ g[l][r]=\sum_{i=l}^{r}\sum_{j=i+1}^{r}(i-l)\cdot h[i][j] \] 这个式子可以用前缀和优化，现在的任务是求出 \(f\) 和 \(h\)。
枚举 \(r\)，对 \(S[r,n]\) 用 KMP 求出 \(\text{nxt}\) 数组，再对 \(S[1,r-1]\) 进行匹配。匹配到 \(i\) 时，指针 \(p\) 表示当前以 \(i\) 结尾的后缀完全匹配了 \(S[r,p]\)。至此，\(S[r,p]\) 的 border 个数即为 \(f[i][r]\)。
至于 \(h[i][j]\)，等价于 \([i,j]\) 里长度不超过一半的 border 个数。对于一个长为 \(L\) 的串来说，长度大于 \(\frac{L}{2}\) 的 border 呈等差数列，且公差为最小周期 \(L-\text{nxt}[L]\)。由此我们枚举 \(l\)，对 \(S[l,n]\) 求出 \(\text{nxt}\) 数组。再枚举 \(r\)，利用等差数列的性质可以一步跳到 border 小于长度一半的位置，也就求出了 \(h\)。
时间复杂度 \(O(n^2)\)。
E. Cyan White Tree
先处理 \(c\ge w\) 的情况，\(c\le w\) 只用把每个点颜色取反再跑一遍就行。
当 \(c\ge w\) 时，路径价值是 \(3w-c\)。令 \(a[x]\) 表示路径 \(1\sim x\) 的 \(c-w\)，\(b[x]\) 表示路径 \(1\sim x\) 的 \(3w-c\)。对每个点 \(x\)，维护一个
set<array<int, 2>>，里面每一个元素 \((a[u],b[u])\) 表示当前从 \(x\) 向下位于另一头的最优路径端点 \(u\) 的集合。
考虑自底向上 small-to-large 的过程。现在有两条链，\(x\leftrightarrow u\) 和 \(x\leftrightarrow v\)，合并为一条路径后价值为 \((b[u]-b[x])+(b[v]-b[x])+(b[x]-b[fa])=b[u]+b[v]-b[x]-b[fa]\quad(*)\)。当然前提是合并后的路径满足 \(c - w\ge 0\)，也就是 \(a[u]+a[v]-a[x]-a[fa]\ge 0\quad(**)\)。
如果我们将这个 set
维护成第一维递增，第二维递减（像单调栈一样），那么对于当前 large 集合
\(A\) 和 small 集合 \(B\)，遍历 \(B\) 中每一个元素 \((a[v],b[v])\)，我们就能再 \(A\) 中 lower_bound 第一个大于等于 \((a[x]+a[fa]-a[v],-\infty)\) 的元素 \((a[u],b[u])\)，此时在满足 \((*)\) 的情况下做到了让 \(b[u]\) 最大，也就是 \((**)\) 最大。
时间复杂度 \(O(n\log^2n)\)，实际跑得飞快。
J. Trajan Algorithm
小清新图论题。首先对于一个点 \(x\)，一定有 \(\text{low}[x]\le \text{dfn}[x]\)。所以假算法只会把 \(\text{low}[x]\) 变小。
接着对于一个点 \(x\)，是割点当且仅当 \(\text{low}[y]\ge \text{dfn}[x]\)，假算法更难满足，所以割点只会被判漏。被判漏说明 \(\text{low}[y]<\text{dfn}[x]\)，而错误的 \(\text{low}[y]\) 是从 \(\text{low}[x]\) 传递过来的。说明满足条件的 \(x\) 满足 \(\text{low}[x]<\text{dfn}[x]\)，这说明 \(x\) 存在返祖边。
于是，\(x\) 被判漏当且仅当有返祖边指向 \(x\)，且也有从 \(x\) 离开的返祖边。换句话说如果 \(x\) 至少在两个点双中，且这两个点双各有至少两条边连向 \(x\)，且不存在 \(x\) 属于一个点双 \(v\) 但 \(v\) 只有一条边连向 \(x\)，那么 \(x\) 就是一个答案。
时间复杂度 \(O(n+m)\)。
CCPC 哈尔滨
M. 连通的正三角形
条件刻画题。不难发现题目等价于计数同时满足如下条件的三元组 \((i,j,k)\) 的数量。
- \(a_i=b_j=c_k\)
- \(i+j\ge n,\ j+k\ge n,\ i+k\ge n\)
- \(i+j+k\neq 2n\)
记这三个条件分别为 \(A,B,C\)。对于条件 \(A\)，可以分为 \(a_i=b_j=c_k=0\) 和 \(a_i=b_j=c_k=1\)，两种情况互斥，答案可以相加。以下将 \(A\) 改写成 \(a_i=b_j=c_k=0\) 为例。
经过观察，满足 \(\lnot C\) 的三元组一定满足 \(B\)。于是答案可以表示为 \(\text{cnt}(A\cap B)-\text{cnt}(A\cap \lnot C)\)。对于 \(\text{cnt}(A\cap \lnot C)\)，是一个经典的 ntt 问题，记数组 \(d_i=[b_i=0]\)，\(e_i=[c_i=0]\)，答案就是 \(\sum\limits_{a_i=0}\sum\limits_{j+k=2n-i}d_j\cdot e_k\)。
对于 \(\text{cnt}(A\cap B)\)，可以使用后缀和线性算。枚举 \(i\)，当 \(n-i\le j\le i\) 时，\(\max(n-i,n-j)=n-j\)，贡献是 \(c_{\ge n-j}\)；当 \(j>i\) 时，\(\max(n-i,n-j)=n-i\)，贡献是 \(c_{\ge n-i}\)。
时间复杂度 \(O(n\log n)\)。
H. 匹配
坏消息，题解完全不说人话。好消息，似乎是一道命题作文。
前置：IntoTheDusk - 鞅的停时定理 - 洛谷专栏，GhostLX - 鞅与停时定理 - 知乎。
以下表述可能有不妥之处。
设当前局面为 \(S=\{a_1,a_2,\ldots,a_n\}\)，我们希望定义一个 \(f(x)\)，使得系统总势能 \(\Phi(S)=\sum\limits_{i=1}^{n}f(a_i)\) 满足：在每一步操作中，总势能期望减少 \(1\)。也就是 \[ E[\Phi(S_{t+1})-\Phi(S_t) | S_t]=-1 \] 我们希望 \(n\) 个集合平均分配势能下降的任务，于是 \[ E[f(i')]-f(i)=-\frac{i}{2m} \] 其中 \(E[f(i')]\) 是下一时刻势能的加权平均，即 \[ \left(\sum_{i'}P(i\to i')f(i')\right)-f(i)=-\frac{i}{2m} \] 已经明显看出高斯消元的形式了，现在的任务只剩下求 \(P(i\to i')\)。
每一轮操作，等价于：选定 \(2m\) 个元素中的 \(m\) 个，删去没选中的 \(m\) 个，再将选中的 \(m\) 个原地复制一份。对于大小为 \(i\) 的集合，假设有 \(j\) 个元素被选中，那操作后集合大小变为 \(2j\)，因此 \[ P(i\to 2j)=\frac{\dbinom{i}{j}\dbinom{2m-i}{m-j}}{\dbinom{2m}{m}} \] 高斯消元对 \(i=1,2,\ldots,2m-1\) 求出 \(f(i)\)，根据停时定理 \[ \text{ans}=E(t)=E(\Phi(S_0))-\Phi(S_t)=\sum_{i=1}^{n}f(a_i)-0 \] 需要注意 \(f(0)=f(2m)=0\)。时间复杂度 \(O(m^3)\)。
ICPC 沈阳
F. The Bond Beyond Time
若 \(x, y\) 不是邻居，可以直接将与 \(x\) 相邻的边都指向 \(x\)，与 \(y\) 相邻的边都指向 \(y\)。
若 \(x,y\) 是邻居，分两种情况：
- \(x,y\) 同处一个环中，此时 bfs 找一个包含 \(x,y\) 的最小环，将所有非环点指向环，这样 \(x,y\) 只能一直绕圈圈。而不与环接触的边可以任意定向。
- 否则，若图中有环，我们也可以找一个离 \(x,y\) 最近的环。先将环上的点标记，再从环出发多源 bfs，标记环到 \(x,y\) 最短路径上的点。此时将所有非标记点指向标记点，\(x,y\) 沿着预定路径追逐到我们找的环中，亦是 Yes。
最后只剩下图中无环的情况，显然是 No。
如何找离 \(x,y\) 最近的环？从 \(x,y\) 出发 bfs，设走到的第一条非割边是 \((u, v)\)，再次 bfs 找包含 \(u,v\) 的最小环就行。时间复杂度依实现方式 \(O(n^2)/O(n)\)，码量略大。
D. LED Display Renovation
令 \(f[i][j][l=0/1]\) 表示前 \(i\) 个位置，翻新了 \(j\) 个段，最多能表示的数字数量。其中 \(l=1\) 代表允许前 \(i\) 个位置全是空，\(l=0\) 则是不允许。
转移的时候 \(2^7\) 枚举当前位置的 \(7\) 个段是否翻新。对于每个状态 \(t\)，算出当前状态下（即对应翻新后）能展示的数字个数 \(\text{cnt}\)，以及能作为最高位展示的数字个数 \(\text{high}\)。转移就是 \[ f[i+1][j+\text{popc}(t)][nl]\ \longleftarrow \ f[i][j][l]\cdot \text{cnt}+(l>0)\cdot \text{high} \] 其中 \(nl=1\) 当且仅当 \(l=1\) 且当前位置的所有常亮段均被翻新。
同样定义 \(g[i][j][l]\) 用于 \(f\) 取到最大值时的方案数。要注意对于当前位置一个数字都显示不了，但能显示空的情况，新的 \(g\) 值应该为 “前 \(i\) 个位置，翻新了 \(j\) 个段且前 \(i\) 个位置均为空” 的方案数。我们将其记作 \(h[i][j][l]\)，这样又能愉快的转移了！
时间复杂度 \(O(nk\cdot 2^7\cdot 10)\)。
CCPC 济南
真的好难，兄弟。真的好难…
A. Cipher
以下做法来自伟大的 lyc。
当 \(a\) 为偶数时，令 \(a=2\cdot c\)，则 \(2^x\cdot c^x\equiv b\pmod{2^{64}}\)，当 \(x\ge 64\) 时左侧模 \(2^{64}\) 恒等为 \(0\)，于是只用依次尝试 \(x\in [0,64)\)。而当 \(a\) 为奇数时，\(a\) 的幂也一定是奇数，接下来我们只用讨论 \(a,b\) 均为奇数的情况。
Conclusion. 在模 \(2^k\) 乘法群中，任何元素的阶都是 \(2\) 的幂。
Proof. 由群论中拉格朗日定理的推论，有限群 \(G\) 中每个元素的阶都整除群 \(G\) 的阶。因此对于任意 \(a\in (\mathbb{Z}/2^k)\)，其阶 \(d\) 一定有 \(d\mid \varphi(2^k)\)，也就是 \(d\mid 2^{k-1}\)。此时 \(d\) 一定是 \(2\) 的幂。
Conclusion. 令 \(x\) 为模 \(2^k\) 下 \(a\) 的阶，\(y\) 为模 \(2^{k+1}\) 下 \(a\) 的阶，那么 \(y\) 只可能是 \(x\) 或 \(2x\)。
Proof. 由 \(a^y\equiv 1\pmod{2^{k+1}}\)，则一定有 \(a^y\equiv 1\pmod {2^k}\)，又 \(x\) 是最小的满足 \(a^x\equiv 1\pmod{2^k}\) 的正整数，于是 \(x\mid y\)。令 \(a^x=1+2^kt\)，那么 \[ a^{2x}=(1+2^kt)^2=1+2^{k+1}t+2^{2k}t^2 \] 当 \(k\ge 1\) 时，\(2k\ge k+1\)，因此 \(2^{2k}t^2\) 能被 \(2^{k+1}\) 整除，故 \(a^{2x}\equiv 1\pmod{2^{k+1}}\)。
因此 \(y\mid 2x\)，结合 \(x\mid y\)，可得 \(y=x\) 或 \(y=2x\)。
考虑 \(a^{x_k}\equiv b\pmod {2^k}\)，其中 \(k=1,2,3,\ldots\) 一直递增到 \(64\)，该过程中 \(x_k\) 一定是 \(x_{k-1}\) 或 \(2\cdot x_{k-1}\)，分别尝试即可。若到某个 \(k\) 时两种情况都不能满足，那对于更大的 \(k\) 也必然不能满足，直接无解。时间复杂度 \(O(T\cdot 64)\)。
E. Tree and Subgraph Problem
\(\text{sub}(S)\) 和 \(\text{sub}(T)\) 不交，等价于存在一条连接 \(\text{sub}(S)\) 和 \(\text{sub}(T)\) 的最短路径，该路径上的内部点（不包括端点）和边均不属于二者。把贡献摊到点和边上，由该路径上 “边数 = 点数 + 1” 的巧妙性质，答案可以写成 \[ \text{ans} = \sum_{e\in E}g_e-\sum_{v\in V} f_v \] 其中 \(g_e\) 表示删除边 \(e\) 后，两个连通块中分别选 \(S,T\) 的方案数；\(f_v\) 表示删除点 \(v\) 后，在不同连通块中分别选 \(S,T\) 的方案数。
令 \(\text{in}_{x}\) 和 \(\text{out}_{x}\) 分别表示以 \(x\) 为根的子树内/子树外，选一个颜色相同的非空点集的方案数之和。于是 \(g_{(x, y)} = 2\cdot \text{in}_{y} \cdot \text{out}_{y}\)，乘 \(2\) 是因为计有序对。至于 \(f_v\)，设删去 \(v\) 后分成的若干连通块的 \(\text{in}\) 值分别为 \(p_1,p_2,\ldots,p_m\)，那么 \[ f_v=\sum_{i\neq j}p_ip_j=\left(\sum_{i}p_i\right)^2-\sum_{i}p_i^2 \] 问题转化为了对每个 \(x\) 求出 \(\text{in}_x\) 和 \(\text{out}_x\)。利用 dsu_on_tree 维护当前子树内各颜色 \(c\) 出现的次数 \(\text{cnt}_c\)，于是 \[ \text{in}_x = \sum_{c}(2^{\text{cnt}_c}-1)\qquad \text{out}_x=\sum_{c}(2^{\text{all}_c-\text{cnt}_c}-1) \] 其中 \(\text{all}_c\) 为颜色 \(c\) 在整棵树中的出现次数。
时间复杂度 \(O(n\log n)\)。
ICPC 上海
还没 VP。
CCPC 郑州
I. Dumb Problem II
对于某个特定的前缀最大值集合 \(S=\{g(p)\}\)，设它在一个排列中出现的概率是 \(P(S)\)。
在 \(k\) 个随机排列中，\(P(S \textbf{ 至少出现一次})=1-P(S \textbf{ 从未出现})=1-(1-P(S))^k\)。
列出答案式子，用二项式定理展开 \[ \begin{align} \text{ans}&=\sum_S\left[1-(1-P(S))^k\right]\\ &=\sum_S\left[1-\sum_{j=0}^{k}\binom{k}{j}(-1)^jP(S)^j\right]\\ &=\sum_{j=1}^{k}\binom{k}{j}(-1)^{j-1}\sum_{S}P(S) ^j\end{align} \] 我们的任务是对所有 \(1\le i\le k\) 求出 \(g_i=\sum\limits_SP(S)^i\)。从式子来看，\(g_i\) 就是这 \(i\) 个排列前缀最大值集合都相同的概率。
不同数字是否成为前缀最大值，是完全独立的事件。考虑从大到小依次插入 \(n,n-1,\ldots,1\) 构成排列的过程，一个数字 \(x\) 有 \(1\) 种方案成为前缀最大值（插到最前面），以及 \(n-x\) 种方案不成为。根据乘法分配律，所有可能的集合 \(S\) 的方案数之和，等于每个数字 \(x\) 所有可能贡献之和的乘积。 \[ g_i=\frac{\prod\limits_{x=1}^{n}(1^i+(n-x)^i)}{(n!)^i}=\frac{\prod\limits_{j=0}^{n-1}(1+j^i)}{(n!)^i} \] 时间复杂度 \(O(nk)\)。
D. Diameter of a Tree
先任意找一条直径，端点设为 \(L,R\)。对于一个点 \(i\)，若 \(\max(\text{dis}(i,L),\text{dis}(i,R))=\text{dis}(L,R)\)，那么 \(i\) 就是某一条直径的端点，这样的点我们称为关键点。
设共有 \(t\) 个关键点，显然标号 \(1\sim t\)，并考虑从标号为 \(t\) 的关键点开始向直径中点标号 \(t+1,t+2,\ldots\)。因为所有直径的中点（或者说中边，如果直径长度为奇数）都是相同的，所以我们没必要真的一路标过来。也就是说，如果直径长度为 \(L\)，答案的前缀一定是 \(t,t+1,t+1,\ldots,t+\lceil\frac{L}{2}\rceil\)。
设直径中点为 \(x_0\)（若两个中点，推荐在两个中点之间建一个虚点作为中点），中点的标号为 \(t_x\)，后半段直径为 \(x_0\to x_1\to x_2\to \ldots\)，那么 \(x_i\ (i\ge 1)\) 的标号应该是 \(t_x+\text{deg}(x_0)+\text{deg}(x_1)+\ldots+\text{deg}(x_{i-1})\)。其中 \(\text{deg}(x)\) 表示在以 \(x_0\) 为根的情况下，满足 \(x\to y\) 且 \(y\) 子树中存在关键点的出边数量。由此可见选择一个 \(\{\text{deg}(x_1),\text{deg}(x_2),\ldots\}\) 字典序最小的 \(\{x_i\}\) 链是最优的。方法是从 \(x_0\) 开始逐层 bfs。
注意直径末尾（也就是答案最后一项）需要特殊判。当只有一个中点时 \(\text{deg}(x_0)\) 也要排除来时的出边。时间复杂度 \(O(n\log n)\)，细节略多。
K. Parentheses and Swapping
题面很绕，等价于对 \(\{b\}\) 中每一对匹配的 \((i,j)\)，交换 \(a[i]\) 和 \(a[j]\)，要让 \(\{a\}\) 字典序最小。
在合法括号序列中，匹配的两个位置 \((i,j)\) 间的元素数量必须是偶数，因此 \(i\) 和 \(j\) 的奇偶性必然不同。
从左往右考虑每个位置 \(i\)，逐个判断
\(b[i]\) 填 ( 还是
)。我们用一个栈维护 \(i\)
之前已经确定的 (，设当前栈顶为 \(u\)，接着断言 \(b[i]\) 填 )，也就是和 \(b[u]\) 匹配，当且仅当：
- \(a[i]\) 是到 \(u\) 时 \(a[u+1\sim n]\) 中未被匹配的最小值。要不然选 \(i\) 后面更小的交换到 \(u\) 肯定更优。
- 在此基础上，若存在 \(j>i\) 满足 \(a[j]=a[i]\)，则需满足 \(a[u]\le t\)，其中 \(t\) 是 \(i\) 未来能匹配上的最优值。若不满足，说明 \(a[u]\) 较大，交换到 \(i\) 的位置肯定更劣。
用两个 ST 表分别维护奇数下标和偶数下标的 “元素+下标” 二元组。对于每个 \(i\)，我们先找到它未来能匹配到最优 \(j\) 的二元组，这样上面两个条件都是好判断的。
时间复杂度 \(O(n\log n)\)。
ICPC 香港
Wait for ucup end.
CCPC 重庆
Wait for ucup end.