CCPCO
看了一下比赛要求，怎么这么多事儿呢。
决定用 csy 的电脑打比赛。然而 csy 的新电脑连 vscode 都没有，只有 bug 奇多的 Dev 5.7，烂中烂。试机赛最后 qlr 写完 C 没保存就编译运行，然后 Dev 爆了代码没了，遗憾离场。
快进到开场 45 分钟（至于前面的时间哪去了？喜报：出错了。重新加载。）开题，看 G 发现是网络流板子，H 不会做，但是一直没有机时，就去开 B，结果忘记阶乘挂了一发，唐。此时 qlr 上机写 D，我口胡完 F 之后和 csy 研究 C，完全想不到怎么 hack 假做法，结果丢给 qlr 一下就叉掉并给出了正确做法，牛。qlr 过 C 之后我开始写 F，并实现了除 NTT 以外的所有部分，让 csy 写 NTT（忘记带板子了），因为我写太慢了。调了一会之后过了。此时他们两个早就胡出了 H 的做法并认为这场必须阿克（qlr 很早就声称他会 A）。H 丢给擅长 ds 的 csy 写，交上去 T 了。qlr 写 A，我和 csy 瞪眼调试。我提出试一下所有 \(a_i = 0\)，发现是因为复制节点导致 Treap 不完全随机，退化成 \(\mathcal O(n ^ 2)\)，改掉就过了，痛失一血。最后大家一起做巨大细节题 A，+0 AC，下班。
B. 军训 II
给定可任意排列的序列 \(a_i\)，求子区间极差和的最小值，以及取到最小值的排列个数模 \(998244353\)。
\(1\leq a_i\leq 10 ^ 6\)，\(1\leq n\leq 10 ^ 3\)。
和最小当且仅当 \(a\) 升序或降序。考虑：若不大于 \(a\) 的数有 \(c\) 个，则最多有 \(c - k + 1\) 个长度为 \(k\) 的区间的最大值不大于 \(a\)。若不小于 \(a\) 的数有 \(c\) 个，则最多有 \(c - k + 1\) 个长度为 \(k\) 的区间的最小值不小于 \(a\)。升序和降序取到了最大值之和的下界和最小值之和的上界，且易证任何非升序或非降序的序列都做不到这一点。
时间复杂度 \(\mathcal{O}(n\log n)\)。代码。
C. 种树
给定一棵至少有一个黑点的树，每次可以选至少有一个黑点的大小为 \(3\) 的连通块染黑，求最小操作次数。
\(3\leq n\leq 10 ^ 5\)。
最大化染黑两个白点的次数。因为两个白点之间的距离为 \(1\) 或 \(2\)，所以在距离不超过 \(2\) 的两个白点之间连边，树形 DP 求最大匹配即可。容易证明求出的匹配在调整后存在对应方案。
时间复杂度 \(\mathcal{O}(n)\)。代码。
D. 编码器-解码器
给定字符串 \(s, t\)，设 \(S_i = S_{i - 1} + s_i + S_{i - 1}\)，求 \(t\) 在 \(S_{|s|}\) 以子序列形式的出现次数模 \(998244353\)。
\(1\leq |s|, |t|\leq 100\)。
设 \(f_{i, l, r}\) 表示 \(t[l, r]\) 在 \(S_i\) 以子序列形式的出现次数 DP 即可。
时间复杂度 \(\mathcal{O}(|s||t| ^ 3)\)。代码。
F. 包子鸡蛋 III
给定字符串长度 \(n\) 和每个小写字母的出现概率 \(p_i\)，求恰有 \(m\) 个
egg子序列的子串数量的期望值模 \(998244353\)。\(1\leq n\leq 5\times 10 ^ 5\)，\(1\leq m\leq 1500\)。
一个串是否是好串只和其 eg 序列的具体内容有关。
设 eg 序列的权值为 \(p_e ^ {cnt_e} p_{g} ^ {cnt_g}\)，求长度为 \(i\) 且恰有 \(m\) 个 egg 子序列的 eg 序列的权值和 \(a_i\)，则 \(i\) 的长度为 \(\mathcal{O}(n)\) 级别。去掉开头的 g 和最后一个 g 及其两侧的 e，从后往前的每个 e 让子序列数量至少增加 \(1\)，每个 g 让子序列数量的增加值至少增加 \(1\)，所以这部分长度不超过 \(m\)。设 \(f_{i, j, k}\) 表示处理后长度为 \(i\)，处理前子序列数量为 \(j\) 且 g 的数量为 \(k\) 的 eg 序列权值和，因为 \(k\) 是 \(\mathcal{O}(\sqrt m)\) 级别，所以总复杂度 \(\mathcal{O}(m ^ 2 \sqrt m)\)。
求出 \(f\) 之后容易 \(\mathcal{O}(n)\) 算出 \(a_i\)。设 \(P = 1 - p_e - p_g\)，对于长度为 \(j\) 的子串，其 eg 序列长度为 \(i(i\leq j)\) 且合法的概率为 \(P ^ {j - i} a_i \binom j i\)。NTT 算出 \(c_j = \sum_{i = 1} ^ j P ^ {j - i} a_i \binom j i\)，由期望的线性性，答案为 \(\sum_{j = 1} ^ n c_j (n - j + 1)\)。
时间复杂度 \(\mathcal{O}(n + m ^ {2}\sqrt m)\)。代码。
标签：leq,csy,qlr,2024,2025,XCPC,长度,序列,mathcal From： https://www.cnblogs.com/alex-wei/p/18412247/2024-2025_XCPC