随机浏览

idea by GeZhiyuan, solution by GeZhiyuan, shr, std by shr, data by GeZhiyuan

算法 I

考虑必定是存在一些页面，如果到达了这些页面，就回到页面 $1$。可以直接枚举会回到 $1$ 的页面集合 $S$，然后暴力进行高斯消元，复杂度 $O(2^n \times n^3)$，预计通过 $12$ 分。

算法 II

考虑假设 $m$ 轮后，即使没有到达 $n$ 也不会继续操作，只要 $m$ 取到足够大误差就可以接受，复杂度 $O(m \times n^2)$。预计通过 $48$ 分。

通过精细卡常可能能通过 $72$ 分。

算法 III

考虑先强制让所有页面都不会按红色按钮，然后记 $f_i$ 表示目前在页面 $i$，要到页面 $n$ 期望要随机选择几次。每次找出最大的 $f_i$，如果最大的 $f_i$ 不为 $f_1$，则令到达这个页面后会点击红色按钮回到 $f_1$，每次消元复杂度 $O(n^3)$，又至多只会 $n$ 次让页面点击红色按钮，因此复杂度 $O(n^4)$。预计通过 $72$ 分。

算法 IV

考虑利用动态高斯消元优化 算法 III，复杂度 $O(n^3)$。预计通过 $100$ 分。

动态高斯消元的方法可以参考 [集训队互测2015] 最大异或和 的题解。

数字生命

idea by dead_X, solution, std by zhoukangyang, data by zhoukangyang, Rainbow_sjy

小故事

这题是三年前 dead_X 看错一道题后给我报的题意。听完题后我很快就想出了做法！而且感觉这个做法很趣味！之前没怎么见到过这种思路！

后来又在其他题/博客里面发现了这类做法，感觉有点错！但查询了一些选手的看法，他们认为即使见过这些也不简单！

WC2025 中我自己又讲了相关的内容，就当是抹平技术差距了（雾）

算法一

首先，我们差分 $a$ 序列，设差分结果为 $c$。

一次操作就是将 $c$ 的第 $p$ 个位置 $-1$（需要保证 $c_p\ge 1$），将 $c$ 的第 $p+len$ 个位置 $+1$。

此时我们可以将问题看成是，第 $i$ 个位置有 $c_i$（$c_i$ 可以为负） 个石子。每次我们可以将一个石子向前移动 $len$ 步，最终我们要让每个位置的石子数清零。我们可以把这里的 "正 $c_i$" 看成一个石子移动的起点，一个 "负 $c_i$" 看成一个石子移动的终点。

容易发现，起点个数等于终点个数，且如果想要有解，则最多只会有 $m$ 个起点。

根据这个转化，我们可以写出 DP：从往后加入起点，记录此时已经匹配的终点和使用的操作。维护这个 DP 大约要 $\mathcal O(4^m)$ 的复杂度。

根据算法的复杂度和减枝程度，可以获得 $30\sim 75$ 分。

算法二

设 $G_{i,j}$ 表示从第 $i$ 个起点走到第 $j$ 个终点，可以使用哪些操作集合来进行操作。我们给每个 "操作集合" 随机赋值，并将其看成一个集合幂级数。

而我们想要求的是 $\sum_{p} \prod_{i} G_{i,p_i}$，其中集合幂级数的乘法是子集卷积。

注意到我们其实并不关心每个排列带的系数是什么，所以我们要求的也可以是 $\sum_{p} sgn(p) \prod_{i} G_{i,p_i}$。

这就是一个对集合幂级数求 det 的问题了。但是如果使用子集卷积，复杂度带的 $m$ 因子会过多。

我们发现我们可以直接使用或卷积。因为如果或卷积中有重的元素了，那么我们使用的操作的子集和一定和原序列的总和对不上，因此只需再对总和做限制即可。

算答案的每个点值需要 $\mathcal O(m^3)$ 的复杂度，总复杂度 $\mathcal O(2^mm^3)$。

人机验证

idea by xyf007, data, std by zhoukangyang, solution by zhoukangyang, EntropyIncreaser

小故事

这是 NOI2023 后的暑假时给出的做法。

当时 xyf007 找我问这个题。我看了一下发现就是求带深度限制的有根树计数，然后思考了一下，发现有些困难。感觉这是典题，所以咨询了 EI，EI 告诉我他也很好奇这题能不能做。

而 xyf007 告诉我这题能做，而且我之前说出过正确做法。我隐约感觉有些印象，就又开始思考这个问题。断断续续想了几天，我终于想出了一个低于平方的做法！而这题之前的做法并不正确。我把这个做法告诉了 EI，EI 提出用特征多项式优化的做法，能做到 $\mathcal O(n\sqrt n\log n)$。

近几天准备这道题的时候，我重新思考了一下这个问题，发现有了快速的多项式复合后又有另一种 $\mathcal O(n\sqrt n\log n)$ 做法，以及【数据删除】。

题解

显然，问题的难点在于求 $n$ 个点深度不超过 $k$ 的有标号有根树个数。

首先容斥，钦定一些元素的深度恰好为 $k+1$，然后把这些点和他们的祖先都标记了（即保留”虚树“上的点）。

真实的树就是在每个”虚树“上的点上长出一颗新的树，所以答案只和虚树上的点数有关。

可以据此写出一个看起来没啥变化的 DP 来统计虚树上的点数：

$$F_0=-x$$

$$F_i=x(\exp(F_{i-1})-1)$$

求出 $F_k$ 即可得到答案。

接下来我们考虑另一种 DP：

设 $dp_{d,r}(x)$，其中 $[x^c]$ 表示离叶子高度为 $d$ 的恰好有 $r$ 个点，且总点数恰好为 $c$ 的方案数。其中，有 $r \le \lfloor \frac{n}{d} \rfloor$。

从 $dp_{i-1}$ 到 $dp_i$ 的转移系数是个第二类斯特林数。我们要求的是 $dp_{k+1}$。

注意到 $dp_{d,r} = \frac{F_d^r}{r!}$。所以我们可以定一个阈值 $B$，用第一种 DP 算出 $dp_{B}$。

此时考虑如何用 $dp_{B}$ 获得 $dp_{2B}$。这里设 $m = \lfloor \frac{n}{B} \rfloor$

注意到第二维大小不大，因此可以考虑矩阵快速幂。如果直接使用矩阵快速幂，需要对一个 $len$ 维护 $m \times m$ 的矩阵 $G$，其中 $[x^c] G_{i,j}$ 表示第 $0$ 层有 $i$ 个点，第 $len$ 层有 $j$ 个点，总共有 $c$ 个点的有标号有根树个数。

接下来有两种做法。

做法1

把整个矩阵记下来很浪费。考虑设 $H_i(x) = \sum_j G_{i,j}y^j$，可以发现 $H_{i} = H_1^i$。因此只需记录 $H_1$。

接下来考虑如何"翻倍"，即 $len\to len\times 2$。这无非计算 $\sum_i [y^i]H_i H^i$，对 $x$ 这一维插值，对 $y$ 这一维就是多项式复合。

使用 $\texttt {2log}$ 的多项式复合，我们可以做到 $\mathcal O(m^2len\log^2 n)$ 计算长度为 $len$ 的转移矩阵。而对于一个多项式 $F_x$，我们通过其计算 $F_{x+len}$ 可以做到 $\mathcal O(nm)$。

因此复杂度是 $\mathcal O(\frac{B}{len}\times nm+m^2len\log^2 n) = \mathcal O(\frac{n^2}{len}+m^2len\log^2 n)$。取 $len=\frac{n}{m\log n}$ 即可得到 $\mathcal O(nm\log n)$ 的复杂度。

$B$ 最初取 $\sqrt n$，总复杂度 $\mathcal O(n\sqrt n\log n)$。

做法2

这个转移矩阵是对角矩阵，有特征多项式 $f(y) = \prod_{i=1}^{m}(y-x^i)$。

由于 $F_i = dp_{i,1}$，序列 $F_i$ 有线性递推 $f$。我们计算出 $F_B,F_{B+1},F_{B+2},...,F_{B+m}$，然后只要计算出 $y^{B}\bmod f(y)$ 即可知道如何用 $F_{B},F_{B+1},...,F_{B+m}$ 线性表示出 $F_{2B}$。

考虑倍增计算 $y^{B}\bmod f(y)$。注意到 $y^k \bmod f(y)$ 在 $x$ 上的多项式次数是 $\mathcal O(km)$ 的，总大小是 $\mathcal O(km^2)$，因此需要的复杂度是 $\sum_{i} \frac{B}{2^i}m^2\log n = \mathcal O(\frac{n^2}{B}\log n)$。你也可以通过对对 $x$ 这一维插值、对 $y$ 这一维取模来计算这个式子。

$B$ 最初取 $\mathcal O(\sqrt n)$，总复杂度 $\mathcal O(n\sqrt n\log n)$。

一年接一年，又到了 UOJ 管理员的换届时刻！

我们这一届管理员（1kri, huahua, JohnVictor, zhoukangyang）在过去的一年中举办了一场 UR，一场UR，以及年度活动 Goodbye Round 与 UNR。多亏了为我们提供指导与帮助的 vfk vfleaking 与前管理 qingyu 和 skip2004，帮我们上传了大量题目的 Rainbow_sjy, 以及这一年来为 UOJ 分享自己有趣的题目的 command_block, cmll02, Kubic, tzc_wk, Ecrade_, zjy0001 和 myee。在无数的命题、造题、传题与修锅的过程中，是这个大家庭对 UOJ 共同的热爱，指引着我们又走过了一年。

当我是刚学 OI 的小朋友时，我便与 UOJ 第一次邂逅。当时我参加了 UOJ Long Round #1，鏖战四个小时终于通过了 T1，而在这题之后还有五道更难的题目，我感受到了这个 OJ 的深不可测。后来我在做 UOJ 比赛题的时候，我发现这些题目的质量普遍较高。这些题目常常蕴含着一些独特而惊艳的思想，这些思想让我受益匪浅。一代一代的管理员用自己纯粹的热情传递着 UOJ 的精神，打造着属于一代一代选手的思维乐园。

在 NOI 2023 结束前，青鱼与 127 找到了我，问我有没有兴趣来当 UOJ 管理员。出于对这个伟大 OJ 的热爱，我毅然决定接下了这个大锅。回顾当管理的一年，许多事情让我记忆犹新。UR26 比赛时我发现 T2 的一个子任务数据范围配错了，好在样例没问题，没对比赛造成影响；在 UR27 前，为了让这场比赛的 T3 不被浪费（我计划在 APIO 讲这道题）且让尽可能多的选手能参赛，我们反复地商讨比赛时间；还记得 UNR Day2 的前一天我还在参加 AWTF 的现场活动，而我还没完全造完我的题目，因此我没去最后的 KTV 活动，而是回到酒店造题造到凌晨；今天我试着将自己的账号封禁再用其他超管的账号把自己解封，却发现自己已经不再是超管了，这给我的我的 UOJ 管理任期画上了一个滑稽的句号。

我们相信下一届管理员能够比我们做的更好，将 UOJ 的这份精神继续发扬光大，建设这一算法竞赛的圣地。在接下来的一年中担任 UOJ 的管理员的四位分别是：

Rainbow_sjy, shr, yaoxi_std, Melania

祝你们四位一切顺利，祝 UOJ 有更光明的未来！

D2T1

idea,solution,data,std by zhoukangyang

这题有很多做法，欢迎大家在评论区交流。

考虑设 $t_i$ 表示 $i$ 被删除的时间。

考虑从前往后依次确定 $t_i$。如果 $i$ 时刻在 $t_i$ 时刻被删掉，那么 $i$ 前面的第一个 $\ge t_i$ 的 $t$ 上的字符一定和 $i$ 不同。而 $t_i$ 是满足条件的值中最小的一个。

所以可以考虑对于每个 $j$ 记录 $i$ 前面第一个（下标最大的一个）满足 $t_{pos}\ge j$ 的 $s_{pos}$。

考虑记录该字符串。初始状态就是整个字符串均为 $s_1$。

加入位置 $i$ 的时候，修改即为在字符串中找到第一个 $\neq s_i$ 的字符 $p$，将其修改为 $s_p$。如果找不到则说明该位置不会被删除。

直接用动态规划维护是 $\mathcal O(n2^k)$ 的。

注意到我们其实只关心字符串中 $1$ 的个数！这样就能做到 $\mathcal O(nk)$ 了。

思考题：如果 $s_1$ 也会被删除该怎么做？（这题也能做到 $\mathcal O(nk)$。）

D2T2

idea,solution,data,std by zhoukangyang

致歉

本来这题是 $n\times n$ 矩阵找第 $n$ 小，只允许比较，要求次数 $\mathcal O(\sqrt n)$，放 Day2T3 的。

但是后来因为常数太大，卡不掉暴力，就改成了现在这个版本。

结果这题之前在一些地方的模拟赛里面出现过了，赛前没有查到一样的题，向大家道歉！！

题解

考虑提取所有偶数列，然后求出其中第 $(k-n)/2$ 小值。我们发现最后的答案一定大于等于这个值，所以前 $k$ 小的元素中我们已经确定出了 $(k-n)/2\times 2$ 个了，还差 $n$ 个。

现在我们只需要接下来再取出 $n$ 个元素即可。这个可以把每行第一个没被选的元素丢到 priority_queue 实现。

行列交替地做，操作次数是 $T(n,m) = T(m,n/2) + 2n$，有 $T(n,n)=6n$，还不能通过（然而数据较弱，部分选手直接实现了这个算法也通过了）。

我们发现如果 $(x-1,y)$ 和 $(x,y-1)$ 还没被选进前 $k$ 小，$(x,y)$ 就暂时不会被选。事实上，加上这个优化操作次数就是 $5n$ 的了。

我们证明从 $T(n/2,n/2)$ 的答案推到 $T(n,n)$ 的过程中我们最多只会问 $2.5n$ 次。

证明：考虑 $T(n/2,n)$ 到 $T(n,n)$ 的过程。设第 $i$ 行刚开始去了 $a_i$ 个元素（$a_i$ 是偶数），最终取了 $b_i$ 个元素，那么最终我们会问 $n+|\{b_i\}|$ 次。在 $T(n/2,n/2)$ 中，我们询问了 $n/2 + |\{a_i\}|$ 次。；

我们先假装总询问次数是 $3n/2 + n + |\{a_i\}|$ 次，接下来观察我们会在什么情况下少问一些。

在做 $T(n/2,n)$ 时，如果 $a_i\neq a_{i-1}$，那么 $(i,a_{i}+2)$ 一定被问过了。

此时，如果 $a_i\neq b_i$，那么我们就利用上了 $(i,a_i+2)$ 的信息，询问次数 $-1$；而如果 $a_i = b_i$，那么 $b_i$ 中一定不会出现 $a_i+1$ 这个数，询问次数 $-1$。

综上，我们一定少询问了 $|\{a_i\}|$ 次，也就是说我们只会询问 $5n/2$ 次。所以总询问次数不会超过 $T(n,n) = T(n/2,n/2) + 5n/2$，即 $T(n,n) = 5n$。

D2T3

idea,solution,data,std by Kubic

$O(n\log^2 n)$

分治。处理所有跨过分治点的贡献。只需 $O(\log n)$ 代价即可转化到原问题。

离线，扫描值域。令当前扫描到 $x$。对于每个 $i$，维护 $p_i$ 表示第 $i$ 时刻分治中心左边距离中心最近的 $\le x$ 的数的距离，$q_i$ 表示右边的距离。

$x$ 增大时对 $p,q$ 的修改均为区间取 $\min$，用 $\text{segbeats}$ 维护即可。

还需要维护每个时刻的答案 $w_i$。第 $i$ 时刻 $\min\ge x$ 的区间数量即为 $p_i\times q_i$。因此 $x$ 增大时，需要令 $w_i\leftarrow w_i+p_i\times q_i$。

每个 $i$ 处维护四维向量 $(p_i,q_i,p_i\times q_i,w_i)$，用矩阵表示修改即可。时间复杂度为 $O(n\log n)$。

加上外层分治，总时间复杂度为 $O(n\log^2 n)$。

$O(n\sqrt n)$

可以把要求的东西转化为 $\sum\limits_{i=1}^n(suf_i-i)(i-pre_i)a_i$。

其中 $pre_i$ 表示 $i$ 前面第一个 $< a_i$ 的位置，$suf_i$ 表示 $i$ 后面第一个 $\le a_i$ 的位置。

考虑询问分块，将 $B$ 个询问分入同一个块中。

在进入每个块之前先将这个块中所涉及到的 $B$ 个位置设为 $+\infty$，然后计算 $pre$ 和 $suf$。

此时序列被这 $B$ 个位置分为了 $O(B)$ 段。

对于一个询问，我们分析填上这 $B$ 个位置的数对 $pre$ 和 $suf$ 的影响。只考虑 $pre$，$suf$ 的分析是类似的。

可能有一些 $pre$ 会变为这 $B$ 个位置之一。每个段内只有所有非严格前缀最小值的 $pre$ 可能改变。

我们用类似于求 $pre$ 的过程，对这 $B$ 个位置以及每个段内的最小值做单调栈。

到达一个段时，我们可以用当前的单调栈刻画出这个段中所有数的 $pre$ 的变化情况：对于一个当前段中的前缀最小值 $a_i$，我们找到单调栈中第一个 $< a_i$ 的数 $a_t$。如果 $t$ 是 $B$ 个位置之一，那么 $pre_i$ 会变为 $t$，否则 $pre_i$ 不变。

于是我们可以把一次询问转化为在序列上的 $O(B^2)$ 次询问，每次询问一个段中有多少个 $\le w$ 的数。

这样做的时间复杂度为 $O(\dfrac{n^2}{B}+nB^2)$，取 $B=n^{\frac{1}{3}}$ 可以得到 $O(n^{\frac{5}{3}})$ 的时间复杂度。

但我们可以进一步优化，可以发现，单调栈中有很多不变的数，我们可以在单调栈改变的时候将后面的数因为这次改变所产生的贡献全部计算出来。每次询问形如在第 $x$ 个段及之后的所有数中有多少个 $\le w$ 的数。

因为段只有 $O(B)$ 个，并且询问的 $w$ 也只有 $O(B)$ 种，所以我们可以用在每个段内双指针，并用二维前缀和预处理出每一种可能的询问的答案。

这 $O(B)$ 个点的贡献容易在过程中同时进行计算，这里不再赘述。

这样做的时间复杂度为 $O(\dfrac{n^2}{B}+nB)$，取 $B=n^{\frac{1}{2}}$ 可以得到 $O(n\sqrt n)$ 的时间复杂度。

D1T1

idea,sol,data,std from Kubic

别急。

D1T2

idea from cmk666，solution from cmk666。

记区间 $[l,r]$ 中颜色 $i$ 出现 $c_i(c_i>0)$ 次，如果 $i$ 只出现在 $S$ 中，那么有 $1$ 种选择方法，如果只出现在 $U/S$ 中，那么有 $1$ 种选择方法，否则有 $2^{c_i}-2$ 种选择方法。

考虑构造形式幂级数 $F_i(x)=(x-1)^2+2^{c_i}x,F(x)=\prod_i F_i(x)$ ,如果有 $K$ 种不同的颜色在区间 $[l,r]$ 中出现，那么答案就是 $[x^K]F(x)$。

考虑记 $y=(x-1)^2$ 那么 $F(x)$ 每一项的指数和是固定的 $K$，于是我们可以设 $G_i(x)=1+2^{c_i}x$，求出 $G(x)=\prod_i G_i(x)$，那么答案就是 $[x^K]\sum_i(x-1)^{2(K-i)}x^i[x^i]G(x)=\sum_i(-1)^{K-i}\binom{2(K-i)}{K-i}[x^i]G(x)$。

接下来观察模数的性质，因为$G_i(x)=1+2^{c_i}x,c_i>0$，所以有 $\forall i\ge 64,[x^i]G(x)\equiv 0\pmod{2^{64}}$，于是我们只需要求出 $G$ 的前 $64$ 项即可。

对于 $c_i\ge 64$，我们不用关心，因为 $G_i(x)\equiv 1\pmod{2^{64}}$，对 $G$ 的求解没有影响。

否则，对于 $1\le k\le 63$，依次统计出 $d_k=\sum_i[c_i=k]$，于是 $G(x)=\prod_{k=1}^{63} (1+2^kx)^{d_k}$，容易用组合数预处理出 $(1+2^kx)^{d_k}$ 的每一项系数，并且对于每一个 $k$，其只有前 $\lfloor \dfrac{63}{k}\rfloor$ 的值在模意义下不为 $0$，如果我们从大到小依次枚举 $k$ 乘起来，它依然保持这个性质，于是单次计算 $G(x)$ 的复杂度就是 $\Theta(\log^2 P)$ 的了。

如果用扫描线配合树状数组求出 $d_k$，那么总时间复杂度就是 $\Theta((n+q)\log n\log P+q\log^2 P)$ 的。

D1T3

idea,data,std from unputdownable, solution from unputdownable,zhoukangyang

$n \le 2$

一个点只有两个出边。

如果两者字符不一样，那么直接走对应字符的出边就行。

难处理的是两条出边字符相等的情况。

但是 $n \leq 2$，注意到向右走一定不劣，所以贪心先匹配第一行，然后再往第二行匹配即可。

总复杂度 $O(L+nm+q\log m)$，也可以做到单组查询 $O(1)$。

$n \leq 3$

贪心失效了！真的失效了吗？

考虑我们的贪心什么时候会挂。 $$ S=\text{xxxxxxxxxxxxxxxxxxxxx}\\ \\ \begin{aligned} T=\ &\color{red}\texttt{xxxxxxxxxxxx}\color{black}\texttt{aaaaa}\\ &\color{blue}\texttt{aaaax}\color{black}\texttt{aaaaaaaaaaaa}\\ &\texttt{aaaa}\color{blue}\texttt{xxxxxxxxxxx}\color{black}\texttt{aa}\\ \end{aligned} $$ 考虑选择一个位置提前往下拐。

注意到如果在蓝色分支之前就往下拐，一定不比蓝色优，否则蓝色一定能接到那个路径上去。

所以应该选择最后一个能往下拐的位置往下拐，然后就是 $n=2$ 的部分了。

注意到能往下拐的位置一定满足 $T_{2,x}=T_{1,x+1}$，或者在末尾，而这个是好维护的

记得在两种贪心中取较大的一个。

总复杂度仍是 $O(L+nm+q\log m)$，也可以做到单组查询 $O(1)$。

$n \leq 4$

贪心还有救吗？ $$ S=\text{xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx}\\ \\ \begin{aligned} T=\ &\color{red}\texttt{xxxxxxxxxxxxxxxxxx}\color{}\texttt{aaaaaa}\\ &\texttt{a}\color{green}\texttt{x}\color{}\texttt{aa}\color{blue}\texttt{x}\color{}\texttt{a}\color{blue}\texttt{x}\color{}\texttt{a}\color{blue}\texttt{x}\color{}\texttt{a}\color{blue}\texttt{x}\color{}\texttt{a}\color{blue}\texttt{x}\color{}\texttt{a}\color{blue}\texttt{x}\color{}\texttt{a}\color{blue}\texttt{x}\color{black}\texttt{aaaaaaa}\\ &\texttt{a}\color{green}\texttt{x}\color{}\texttt{aaaaaaaaaaaaaaaaaaaaaa}\\ &\texttt{a}\color{green}\texttt{xxxxxxxxxxxxxxxxxxxxxxx}\\ \end{aligned} $$

这样子可以把上述贪心卡死。

但是如果能找到一个直达第三排的位置，从那个位置往下拐贪一下，就还有救。

因为考虑所有从第二行转移到第三行的列，如果这一列的第一行无法到达，那么可以被走完第一行再接 $n=3$ 的贪心；

而当我们找到一个能直达第三行的位置，和 $n=3$ 的情况就差不多了，可以证明这是最优的决策之一。

观察到能到第三排的位置应该满足 $T_{2,x}=T_{1,x+1}，T_{3,x}=T_{1,x+2}$；或者 $x$ 在第一行贪心匹配部分（上图红色）末尾两个字符（需要特判）。

将走完第一行再接 $n=3$；第一行走到剩下一个再接 $n=3$；选择最后一个能往下拐的位置往下拐；找到最后一个能直达第三行的位置往下拐四种贪心拼起来即可通过 $n=4$。

总复杂度仍是 $O(L+nm+q\log m)$，也可以做到单组查询 $O(1)$。

$L,m,q \leq 1000$

对于询问暴力跑一个朴素的 DP，记 $f_{i,j}$ 表示能否走到 $(i,j)$ 这个点，单次询问复杂度 $O(nm)$，

总复杂度 $O(L+nm+qnm)$。

$L,m,q \leq 10^4$

注意到 DP 状态只有 $01$，直接压位用位运算做 DP，单组询问复杂度 $O(m)$；

总复杂度 $O(L+nm\sum+qm)$。

$n \leq 7$

贪心彻底没救了，因为此时路径的形态会变得相当复杂。

注意到 $n$ 很小，考虑想办法维护上述动态 DP。

首先将矩阵转换为斜矩阵以方便理解（第 $i$ 行向右平移 $i-1$ 个字符），这样每一步是向右或者向右下走，即第 $i$ 步一定走到第 $i$ 列。

维护 DP，第 $i$ 列的状态只和第 $i-1$ 列的状态以及需要匹配的字符有关。

难点在于转移矩阵会随着询问的字符串而改变。

想办法固定每个位置的转移矩阵。

注意到如果先贪心在第一行匹配，那么在和第一行匹配上的这个区间内，转移矩阵是固定的。

直接动态 DP 维护此时的 DP 状态；如果下面的行已经没有可达的位置了，那么贪心匹配第一行一定是最优的；否则跳到下方第一个可以到达的行，然后递归。

预处理动态 DP 矩阵，查询时只需要做至多 $n$ 遍向量乘区间的转移矩阵。

视实现的不同复杂度大约 $O(L \log L+n^3m\log m+qn^3)$。

$n \leq 10$

注意到矩阵很小，可以压位，单次矩乘 $O(n^2)$。

上猫树，注意到每次乘的是单个转移矩阵，而不是若干转移矩阵的积，其中非 $0$ 元素只有 $O(n)$ 个。

这样预处理时单次矩乘 $O(n)$。

复杂度 $O(L \log L+n^2m \log m+qn^2)$。

由于实测时间瓶颈在 $SA$ 预处理上，所以即使你的询问多一个 $n$ 或者多一只 $\log$，如果卡常较为精细也能通过。

谢罪

部分乱搞获得了 $84$，复杂度错误的 $O(m2^{\frac n 2})$ 以及 $O(m2^n)$ 也通过了。

转眼间又是一年 NOI 了，为了帮大家备战 NOI，延续 UOJ 的传统保留项目，UOJ NOI Round #8 将在 7 月 12 号到 7 月 14 号隆重举行！

为了方便阅读，同时也因为管理员比较鸽，这次的 UNR 没有特别的主题。

比赛时间

笔试模拟将于 7 月 12 日晚 19 点开始，将进行半个小时。

Day 1 的比赛将于 7 月 13 日上午 8 点半开始，将进行五个小时，共三道题。

Day 2 的比赛将于 7 月 14 日上午 8 点半开始，将进行五个小时，共三道题。

比赛难度

比赛的难度将和 NOI2023 相近，相信对绝大部分选手来说题目是具有一定的挑战性的。

题目中可能拥有若干道非传统题（可能包括但不限于交互题、提交答案题、通信题），大家可以放心食用。

出题阵容

拯救这一年度的 UNR 的出题人将在稍后公布。各位可以先行无奖竞猜出题人的名单。

这场比赛除笔试外将计入 rating。

比赛奖项

这次比赛将会根据三次比赛的总分进行排序（如果存在同分将以两天的罚时总和作为第二关键字），其中比赛的前三十名将成为这次训练的金牌得主，第三十一名到第一百二十名将获得银牌，第一百二十一名到第二百名将获得铜牌。（得奖人数将根据参赛人数进行调整）

总分前三名将获得 UOJ 萌萌哒的撕烤熊抱枕一只。

景点观光

idea, data, solution, std from Ecrade_

引理 1：不移动到子树内没有黑点的结点一定不劣。

我们的目标是遍历到所有黑点，而移动到子树内没有黑点的结点只会徒增操作次数。

引理 2：当移动到结点 $u$ 的子树内时，遍历完 $u$ 子树内的所有黑点再移动到 $u$ 的子树外一定不劣。

若未遍历完 $u$ 子树内的所有黑点就移动到了 $u$ 的子树外，则后面仍需再次移动到 $u$ 子树内遍历剩下的黑点，而这显然只会徒增操作次数。

引理 3：去除子树内没有黑点的结点后得到一棵新树，那么沿着新树的某种欧拉序移动一定不劣。

不妨令红点表示当前未遍历完子树内所有黑点的结点，绿点反之。

根据引理 1，去除子树内没有黑点的结点不会造成任何影响。

根据引理 2，若当前棋子在红点处，则棋子只能往下移动（即移动到深度更大的结点处）。

若当前棋子在绿点 $u$ 处，则考虑离 $u$ 最近且为红点的祖先结点 $r$。

根据引理 2，棋子接下来只能移动到 $r$ 子树内的某个黑点。

观察到在移动的过程中，棋子必然会经过 $r$ 或 $r$ 的某个子结点。

那么在从 $u$ 移动到 $r$ 或 $r$ 的某个子结点的过程中，由于路径上除了 $r$ 为红点，其余均为绿点，故一直往上移动是最优的。

接着，在到达 $r$ 或 $r$ 的某个子结点后，棋子必然又在红点处，这时只能往下移动了。

移动到最后一个黑点后，显然我们一直往上移动至根节点即可。

所以，在整个过程中，我们发现棋子是不会走“回头路”的，其实这也是沿着欧拉序移动的充要条件。

引理 4：沿着新树的欧拉序移动一定是所有移动路径中总路程最短的。

显然，我们必须要经过所有新树的叶结点。

所以，每条边都需要被经过至少两次，而沿着欧拉序移动恰能达到这个理论下界。

注意到总路程 $l$ 为定值（新树边数的两倍），若第二种操作进行了 $x$ 次，则总操作次数为 $x+(l-2x)=l-x$。

所以，我们仅需知道 $x$ 在无限制的情况下的最大值 $x_{\text{max}}$ 即可，这样对于每个询问，答案即为 $l-\min(k,x_{\text{max}})$。

考虑使用动态规划计算出 $x$ 取到最大值时的操作次数。

定义 $f_{u,0/1,0/1}$ 表示进入结点 $u$ 的子树内时，棋子处在 $u/u$ 的某个子结点处；遍历完 $u$ 子树内所有黑点后，将要从 $u/u$ 的某个子结点移动到 $u$ 子树外的操作次数。

由于 $f_{u,0,1}$ 和 $f_{u,1,0}$ 的情况是对称的，故我们仅考虑 $f_{u,1,0}$。

对于 $u$ 的所有子结点，我们需找到一个合适的遍历顺序，使得依次拼接后操作次数最少。

容易发现，相邻两个子结点分别是 $0$ 出和 $0$ 进时，则中间只需进行一次操作，而其余情况则需进行两次操作，故一个直观的想法是 $0$ 越多越好。

考虑贪心。

一般情况下，当 $f_{v,0,0}\le f_{v,0,1}$ 时，取 $f_{v,0,0}$ 不劣。

一般情况下，当 $f_{v,0,0}>f_{v,0,1}$ 时，取 $f_{v,0,1}$ 不劣。

$f_{v,0,1}$ 和 $f_{v,1,1}$ 同理。

所以我们得出结论：一般情况下，对于 $f_{v,0,0},f_{v,0,1},f_{v,1,0}$，哪个最小就取哪个，若有多个最小值，则哪个含 $0$ 越多就取哪个。

至于这里的结论为什么只适用于一般情况下，后续会提及。

子结点与子结点之间的拼接情况已处理完，最后仅剩下首尾两处根结点与子结点之间的情况了。

显然，当根结点 $u$ 和子结点 $v$ 分别满足 $1$ 进和 $0$ 进或是 $1$ 出和 $0$ 出，即进/出 $u$ 子树时处在的结点恰为 $v$ 时，便不需要进行操作，而其余情况则需进行一次操作。

仍考虑贪心。

• 当 $u$ 满足 $0$ 进 $0$ 出时：

首尾两处与子结点均需进行一次操作，而中间相邻子结点之间分别满足 $0$ 出和 $0$ 进的数量越多越好。

当没有 $0$ 进 $1$ 出或 $1$ 进 $0$ 出的子结点时，只能将所有 $0$ 进 $0$ 出的子结点紧挨着排，后跟着所有 $1$ 进 $1$ 出的子结点；

否则将一个 $1$ 进 $0$ 出的子结点排在首位，后跟着所有 $0$ 进 $0$ 出的子结点，再跟着 $0$ 进 $1$ 出、 $1$ 进 $0$ 出的交替排列，最后跟着所有 $1$ 进 $1$ 出的子结点。

• 当 $u$ 满足 $1$ 进 $0$ 出时：

将所有 $0$ 进 $0$ 出的子结点紧挨着排，后跟着 $0$ 进 $1$ 出、 $1$ 进 $0$ 出的交替排列，最后跟着所有 $1$ 进 $1$ 出的子结点。

• 当 $u$ 满足 $1$ 进 $1$ 出时：

若 $u$ 仅有一个子结点，暴力考虑所有情况即可；

否则将所有 $0$ 出 $0$ 进的子结点紧挨着排，后跟着 $0$ 出 $1$ 进、 $1$ 出 $0$ 进的交替排列，再后跟着所有 $1$ 出 $1$ 进的子结点，最后跟一个 $1$ 出 $0$ 进的的子结点。

注意这里需要再考虑强制将所有子结点变为 $0$ 进 $0$ 出的子结点的情况，因为这时的贪心可能就不奏效了。注意此时若 $u$ 为黑点则需中途再进行一次操作去遍历 $u$。

至此，我们便用 $O(\sum n+\sum q)$ 时间复杂度解决了本题。

509 号迷宫

idea, data, solution, std from JohnVictor

算法一（暴力）

直接 $\text{DP}$，复杂度 $O(n^2)$，可以通过第一个子任务。

算法二（部分分）

输出 $0$ 可以通过第二个子任务。第三个子任务的答案可以用一些组合数简单表示。对于第四个子任务，可以看做 $O(np)$ 个点加一个下三角，下三角部分的贡献可以简单反射容斥计算，剩下部分暴力即可。第五个子任务留给小常数 $O(n\sqrt {n \log n})$ 的直接分块 $\text{NTT}$ 和大常数正解。

算法三（正解）

下面的分析中，令块长 $B=p$。

考虑平移指数基。具体地，对于每一列，考虑维护一个形如 $P(x)/(1-x)^k$ 的多项式表示一整列的 $\text{DP}$ 值构成的生成函数。

我们要支持的操作是加一个单项式，查询一项系数（这两个操作足以解决每一列有一个不能走的点的问题），将 $k$ 加上 $1$（也就是一次前缀和）。

考虑定期重构。我们维护 $P(x)(1-x)^k$ 的形式。每一次将 $k$ 减小 $1$，变成了 $0$ 就重构。这样，对于这个形式查询一项系数是 $O(B)$ 的。

利用 $1-x^p=(1-x)^p$，重构的时候只用除以 $(1-x^B)$，这个相当于隔 $B$ 个做一次前缀和，复杂度 $O(n)$。

主要的问题是加一个单项式之后再除以 $(1-x)$ 怎么办。这个只用额外维护成 $P(x)(1-x)^k+Q(x)/(1-x)^k$ 即可。注意这里的系数还是可以 $O(k)$ 来计算的，因为 $Q$ 不超过 $k$ 个非零系数，单个贡献可以 $O(1)$。

所以现在的复杂度为 $\mathcal O(np+\frac {n^2}{p})$，可以通过所有子任务。

算法四

考虑每 $p$ 条斜线（即 $i+j=t\times p$ 的位置 $(i,j)$）算一次 dp 值。转移的时候可以考虑对障碍点容斥，钦定一些障碍点被经过了，并对可能产生转移的两个障碍点之间计算贡献。

斜线 -> 斜线的贡献可以 $\mathcal O(\frac{n^2}{p})$ 处理；障碍点 -> 障碍点，斜线 -> 障碍点和 障碍点 -> 斜线的贡献均可以 $\mathcal O(np)$ 处理。

时间复杂度 $\mathcal O(np+\frac {n^2}{p})$。

红场阅兵

idea, data, solution, std from zhoukangyang. sol-114514,-1919810 from bulijiojiodibulido

APIO2024 会讲的。大家可以提前复习一下积性函数相关知识。UPD：apio 讲课的核心内容放在了 这里

算法 -114514,-1919810 是 bulijiojiodibulido 老师验题时用的做法，算法一、算法二是官方题解做法。

算法 -114514

令 $t=\gcd(i, j)$，如果我们提取 $i$ 和 $j$ 中与 $t$ 相关的所有因子，即令 $i = t_is_i, j =t_js_j$，其中 $\gcd(t_i, s) = \gcd(t_j, s) = 1$。那么有 $f(ij) = f(s_i) f(s_j) f(t_i t_j)$。

所以可以考虑枚举 $t_i, t_j$，满足它们有相同的素因子分布（即 $\text{rad}(t) = \text{rad}(t_i) = \text{rad} (t_j)$，其中 $\text{rad}(n) = \prod_{p|n} p$），然后计算上式。这个时候我们还有 $\gcd(s_i, t) = \gcd(s_j, t) = 1$ 的条件，如果直接反演，那么复杂度比较高。

类似构造系数 $g(y_i, y_j)$，满足 $\sum_{x_i|y_i, x_j | y_j, \text{rad} (x_i) = \text{rad} (x_j)} g(x_i, x_j) = f(x_ix_j)$。令 $F(n) = \sum_{i=1}^n f(i)$。那么答案为 $$\sum_{t_i,t_j ,\text{rad}(t_i) = \text{rad} (t_j)} g(t_i, t_j) F(\lfloor{n/t_i\rfloor}) F(\lfloor{n/t_j\rfloor})$$。因为我们能保证每对 $t_i, t_j$，前面加的总系数为 $f(t_i t_j)$。

对于函数 $g$，在上面等式中，右侧是积性，也就是关于每个素因子是独立的，所以 $g$ 的取值也是对于每个素因子都是独立的。所以只需要对于所有素数，预处理出 $g(p^i, p^j)$ 的值（事实上是一个次数为 $2(i+j)$ 的多项式），那么对于任意两个数，可以快速算出上述的 $g$ 值。

这个时候直接枚举 $t_i, t_j$，也就是从小到大枚举每个素数，以及在 $t_i, t_j$ 中的指数就能快速计算答案。枚举代价为 $1$ 到 $n$ 内所有 $\text{rad}$ 相同的数字的对数，好像是 $O(n)$ 级别的，可以通过 $3\times 10^7$ 的数据。

算法 -1919810

考虑如何加速这个过程，我们希望能快速计算出比较大的素数的贡献。

$dp_{n_1, n_2, p}$ 表示从大到小枚举因子到 $p$，$n_1 = \lfloor{n/t_i\rfloor}, n_2 = \lfloor{n/t_j\rfloor}$，$g$ 的乘积。对于大于 $\sqrt{n}$ 的素数，它一定是从 $(n, n)$ 转移向 $(\lfloor n/p \rfloor, \lfloor n/p \rfloor)$，并且乘上的是一个四次多项式。

那么我们只需要预处理 $\lfloor n/p \rfloor$ 相同的每段的素数的四次多项式的值，就可以快速完成这些素数的转移。对于剩下的素数，我们枚举它们的指数，从大到小转移即可。

如果使用记忆化，当 $n=10^9$ 的时候，状态数大概在 $2\times 10^6$ 级别，转移大概在 $2\times 10^8$ 级别，使用精细的实现卡常数就可以通过。

实际大部分的状态都是在小素数的地方，所以可能可以从小素数枚举然后 meet in the middle，但是没编出来。

算法一

考虑把积性函数推广至二维，如果函数 $f(x,y)$ 是二维积性函数，假设 $p_i$ 是从小到大第 $i$ 个质数，$x=\prod_i p_i^{a_i}$，$y=\prod_i p_i^{b_i}$，那么 $f(x,y) = \prod_{i} f(p_i^{a_i},p_i^{b_i})$。容易发现我们要求的是二维积性函数前缀和。

考虑设计积性函数 $g(x,y)$ 满足 $g(p^{a},p^b) = f(p^a,1) f(1,p^b)$。对于这个函数，其前缀和 $\sum_{i\le n_1} \sum_{j\le n_2} f(i,1)f(1,j)$ 是相当容易计算的。观察 $h=f/g$。我们发现 $h(p^k,1) = h(1,p^k) = 0$。

暴力枚举 $h$ 有值的位置，可以证明复杂度是 $\mathcal O(n)$。期望得分 $70$ 分。

算法二

考虑优化之前的算法，设计二维积性函数 $g_3$ 满足 $g_3$ 只在 $g_3(x,x)$ 处有值且值为 $h(x,x)$，接下来令 $h' = h/g_3$。

此时有值的 $h'(p^a,p^b)$（$p\in \mathbb{P}, a,b\ge 0$，$a+b\neq 0$）就满足 $a,b\ge 1$ 且 $a\neq b$ 了。

接下来暴力枚举 $h'$ 中的有值元素 $(x,y)$，计算 $\sum_{u \le n/x,v\le n/y} (g * g_3) (u,v)$，把这些答案带上系数加起来就能得到最终答案了。

而 $\sum_{i=1}^A \sum_{j=1}^{B} (g * g_3)(u,v) = \sum_{k=1}^{\min(A,B)} g_3(k,k) \sum_{i=1}^{A/k}\sum_{j=1}^{B/k} g(i,j)$。暴力整出分块计算答案。

我们当然要筛 $f(x,1)$ 和 $g_3(x,x)$ 的块筛前缀和。可以证明，除此之外的复杂度不超过 $\mathcal O(n^{2/3}\log n)$。

其实还可以更快一点，不过没必要了。

UPD：为了凑整，跳蚤国王决定交换比特，将比赛时间更改至五月十二日。

UOJ Round #27 将于 5 月 12 日星期日晚上 19：00 举行！比赛将进行 3 个小时，共三道题。

这是 UOJ 第二十七场 UOJ Round，还是一如既往的省选及以上难度，欢迎大家来玩！

公元 330 年 5 月 11 日，罗马帝国定都君士坦丁堡。

最近，跳蚤国正式定都跳蚤利亚。为了纪念这一历史性的时刻，跳蚤国的居民们欢歌载舞，共同庆祝。跳蚤国王更是举办了一系列的庆祝活动。而你作为跳蚤国王的得力助手，能帮助他举办这些活动吗？

比赛链接：https://uoj.ac/contest/88

出题人：zhoukangyang, Ecrade_, JohnVictor

参加本次比赛将有机会获得 UOJ 抱枕！获奖条件的 SHA256 码是（ba6ecb293c29dfb375e7ce19bbf4022686a7aa16ee872529ddc289db2bed0dad）。比赛结束后将公布条件。 再次提醒大家比赛中途只测样例，最后会进行最终测试，把所有提交记录重测。

再次提醒大家比赛中途只测样例，最后会进行最终测试，把所有提交记录重测。

再次提醒大家比赛时间是五月十二日。

UPD: 恭喜前5名的选手！

1. _LHF_
2. tricyzhkx
3. dead_X
4. JohnAlfnov
5. Nesraychan

Qingyu@mainhost:~$ echo -n "三题得分异或和最大的，如果有多个取排名最高的。" | sha256sum
ba6ecb293c29dfb375e7ce19bbf4022686a7aa16ee872529ddc289db2bed0dad  -

恭喜 shr 获得 uoj 抱枕！

龙门对决

idea, solution, data, std from 1kri.

将 $1$ 定为树的根。

考虑一棵怎样的树满足最大独立集大小恰为总点数的一半。

将树黑白染色，奇数层的点染成黑色，偶数层的点染成白色，则所有黑点和白点都构成独立集，且它们至少有一个大小为总点数的一半。如果树满足条件，则它们大小都为总点数的一半。

假设树满足条件，我们考虑深度最深的点，可以证明它没有兄弟节点。

假设它是黑点，那么我们取出白点集合，将它的父亲删去并将它和它的所有兄弟加入，依然能得到一个独立集。如果它有兄弟节点，则这个独立集的大小就大于总点数的一半了，树也就不满足条件了。

那么我们将这个点和它的父亲节点划为一组，在每个最大独立集中，一组内都恰会选择一个节点。将这一组节点从树中删去，得到一棵新的树。容易发现如果原树满足条件则新树也满足条件。

对新树不断重复找最深点、划分组、删去组的操作，一定能将树删空，并得到 $\frac{n}{2}$ 组节点。

不难发现，能划分出 $\frac{n}{2}$ 组是树满足条件的充分必要条件。

在上述的叙述中，组其实就是匹配，我们找到的条件就等价于树存在完美匹配。可以直接将树看作二分图，如果知道二分图最大独立集等于点数减去最大匹配，那么直接就能得到这个条件了。

接下来考虑怎么计数。

发现树的完美匹配（划分组）方案唯一，那么可以直接计数完美匹配数量。

我们设 $f_{i,0/1}$ 表示 $i$ 子树内选择了一个连通块，且 $i$ 是否被划分进组里（$1$ 表示被划分进去）。最后的答案就是所有 $f_{i,1}$ 之和。

$\text{dp}$ 直接转移是简单的，我们依次枚举儿子，并与当前节点的状态合并。

但是一些做法可能会遇到计算 $0$ 的逆元的情况，需要特殊处理。感谢 JohnVictor 和 skip2004 指出这种情况并构造了相应数据卡掉。

时间复杂度：$O(n)$。

龙门题字

idea, solution, data, std from tzc_wk.

解法一

暴力枚举执行的计划的集合及顺序，时间复杂度 $O(m!L)$，期望通过 subtask 1。

解法二

考虑按位贪心，问题转化为如何 check 一个前缀是否合法，即，是否能够得到一个序列 $b$ 满足 $b$ 的前 $i$ 位分别是 $c_1,c_2,\cdots,c_i$。

考虑把操作过程倒过来，可以变成这样的过程：维护另一序列 $d$，初始 $d_j=\begin{cases}c_j&(j\le i)\\-1&(j>i)\end{cases}$，每次选择一个操作 $k$，满足 $\forall l_k\le j\le r_k$，要么 $d_j=-1$，要么 $d_j=x_{k,j-l_k+1}$，并将 $l_k\le j\le r_k$ 都改成 $-1$。如果最终 $\forall 1\le i\le n$ 都有 $d_i=-1$ 或 $d_i=a_i$，那么这个前缀就是合法的，否则就是不合法的。

直接模拟上面的过程可以实现 $O(nL)$ 地检验一个前缀是否合法，而因为最终每一位可能的取值的个数之和是 $O(n+L)$ 的，所以最多进行 $O(n+L)$ 次检验，总复杂度 $O(nL(n+L))$，期望通过 subtask 1,2。

解法三

考虑在解法二的基础上优化检验的过程。对于每一种计划我们动态地维护当前状态下失配位置的个数并用一个队列维护失配位置个数为 $0$ 的操作集合，每次取出队列中的某个操作 $k$ 并将 $[l_k,r_k]$ 的位置改成 $-1$。将一个位置 $j$ 改为 $-1$ 的时候我们直接遍历所有 $l_k\le j\le r_k$ 的所有操作并更新其失配位置数，如果变成 $0$ 了就加入队列。这样更新总次数为 $O(\sum\limits r_i-l_i+1)=O(L)$，即可实现 $O(L)$ 进行单次检验，总复杂度 $O(L(n+L))$，期望通过 subtask 1,2,3。

解法四

考虑 subtask 4 怎么做。观察到一个性质是，我们在检验 $c_1,c_2,\cdots,c_i$ 这个前缀是否合法时，我们逐位确定的过程已经保证了 $c_1,c_2,\cdots,c_{i-1}$ 这个前缀已经是合法的了，换句话说，如果仅仅只将 $d_i$ 改成 $-1$ 就必定可以到达合法状态。于是问题转化为我们能否想方设法执行一次 $l_k\le i\le r_k$ 的操作将 $d_i$ 改为 $-1$。

可以发现我们的过程是这样的：先不断执行 $r_k < i$ 的操作直到没有多余的 $r_k < i$ 的操作可以进行为止，然后看看现在能不能执行某个 $l_k \le i \le r_k$ 的操作，如果这时候还不行那就没办法了。因此考虑动态地维护不断执行 $r_k < i$ 的操作以后的 $d$ 并按照解法三的方式维护每个操作的失配位置数。因为 $a_i=0$ 且 $x_i > 0$，所以如果存在经过 $i$ 的操作，我们必然会执行至少一次经过 $i$ 的操作，否则答案第 $i$ 位必然是 $0$。因此我们考虑枚举执行了哪个经过 $i$ 的操作，设为 $k$，如果该操作目前失配字符数为 $0$ 则说明答案第 $i$ 位可以是 $x_{k,i-l_k+1}$。这样可以求得答案第 $i$ 位的值。之后我们遍历所有 $r_k=i$ 的操作看看能不能执行，这个过程中可能会产生连锁反应，即执行某些 $r_k=i$ 的操作以后让之前不能执行的操作变得可执行，不过用解法三的方式仍然可以做到 $O(n+L)$ 地维护这个过程。

总时间复杂度 $O(n+L)$，期望通过 subtask 4。

解法五

subtask 5 相较于 subtask 4 多了初值，因此在解法四的基础上，我们只用考虑如何检验在前缀固定的情况下能否不执行经过 $i$ 的操作。这等价于只进行 $r_k < i$ 的操作能否到达合法状态，即是否最终所有 $d_k\ne -1$ 的 $k$ 都有 $c_k=a_k$。在解法四中我们已经维护出不断进行 $r_k < i$ 的操作后的 $d$，因此我们只需顺便维护 $d_k\ne -1$ 且 $c_k\ne a_k$ 的 $k$ 的个数即可。时间复杂度 $O(n+L)$，期望通过这道题。

龙门考古

idea, data, std, from cmll02, solution from cmll02 zhoukangyang.

subtask 1

枚举集合 $S$，check 生成出的 $b$ 是否正确。

如何生成 $b$？从左往右一个一个填，如果是非前缀最大值肯定填剩余数中的最小值；对于是前缀最大值的那些位置，我们肯定是要填一个尽量小的能填进去而不至于让后面无法复合要求的数。

一个可能的实现方法是：填一个数进去之后，把剩余没填的数中最大的那些分配给剩下没填的前缀最大值，然后把剩下的数从小到大填到非前缀最大值的位置，并检查此时是否每个位置都满足 $c$ 的限制。

时间复杂度 $O(2^n\operatorname{poly}(n))$。

期望得分 $5$。

subtask 2

留给可能存在的 $O(n^3)$ 或者奇怪的 $O(n^2\log n)$。

subtask 3

留给可能存在的复杂度依赖前缀最大值个数 $cnt$ 的做法（如 $O(n^2cnt)）$。

这档分 $n$ 开的有些过大，使得场上写这一部分分的选手 TLE 了，在此谢罪>_<。

subtask 4

在这个 subtask 中我们现在知道整个序列中唯一的前缀最大值是第一个元素，显然这意味着一定有 $a_1=n$，所以 $1$ 这个位置是否无法辨认是不重要的（也就是对答案有一个 $\times 2$ 的贡献）。

考虑先鱼如何从无法辨认的 $a$ 和 $c$ 还原出 $b$？只要保证 $b_1=n$ 则不管后面的数怎么填，都符合古籍记载。其中字典序最小的方案，就是将剩余未出现的数从小到大排序后从左往右依次填入每个位置。

这就说明 $2\sim n$ 中无法辨认的位置满足这些位置对应的子序列一定是单调上升的！dp 计算上升子序列个数并乘上 $1$ 位置的两倍贡献即可得到答案。

时间复杂度 $O(n^2)$ 或 $O(n\log n)$（使用树状数组等优化 dp）。

期望得分 $10$。

subtask 5

我们沿用 subtask 4 的分析，可以发现对于非前缀最大值，对应的无法辨认位置仍然需要满足上升，否则存在逆序对，交换这个逆序对一定仍然符合古籍记载，且字典序更小。

如何分析前缀最大值位置呢？注意到一个必要条件，对于前缀最大值位置 $i$，如果它不可辨认，就不能存在一个不可辨认的位置 $j$ 满足 $j > i\land b_j < b_i$，且交换 $b_i,b_j$ 后仍然符合古籍记载。

记 $i$ 右侧的第一个前缀最大值位置是 $x$，$b_{1,\cdots,x-1}$ 中的次大值为 $v$（最大值显然就是 $b_i$）。

若 $b_j\ge b_x$，交换完之后 $b_i > b_x$，$x$ 位置不再是前缀最大值，所以这样的 $j$ 一定没用。

若 $b_j\le v$，交换后 $i$ 位置要么不在是前缀最大值，要么 $v$ 所在位置不应是前缀最大值而交换后变成了前缀最大值，不符合古籍记载，所以这样的 $j$ 也没用。

若 $v < b_j < b_x\land j\neq i$，此时 $j > x$，交换 $b_i,b_j$ 后一定符合古籍记载！

也就是说如果 $i$ 无法辨认，则满足 $v < b_j < b_x\land j\neq i$ 的 $j$ 必须可以辨认。

这个条件是充分的：从左往右每次填一个最小的能填的数时容易证明，满足上面两个条件时，$b$ 一定是字典序最小的方案。

接下来考虑计算方案数。对于前缀最大值来说，他们是否遗失是互相独立的。可以理解为每个前缀最大值划定了一个代表区间，当确定了非前缀最大值无法辨认位置的集合 $T$ 之后，如果一个代表区间里不包含 $T$ 中的任何元素，那么他会带来 $\times 2$ 的系数。

设计 $dp_i$ 代表当前最后一个无法辨认的非前缀最大值位置为 $i$，则转移有 $dp_i2^{f(b_i,b_j)}[b_i < b_j]\to dp_j$，其中 $f(i,j)$ 代表区间 $(i,j)$ 里包含了多少个代表区间。

时间复杂度 $O(n^2)$。

期望得分 $65$。

subtask 6

留给可能的 $n\times cnt$ 做法。

subtask 7

注意到代表区间两两不交。

使用树状数组优化 dp，转移时分类讨论一下当前位置是否在某个代表区间上。

时间复杂度 $O(n\log n)$，期望得分 $100$。

龙门探宝

idea from huahua.

std, data, solution from Kubic

方便起见，我们不妨令路径长度不重复。有重复的情况只需在此基础上加一些判断。

令 $P(u,v)$ 为 $u$ 与 $v$ 之间的路径经过的点集，$M(u,v)$ 为 $u$ 与 $v$ 的路径中点（可能在一条边中间，此时新标一个点）。

扫描区间右端点 $r$，维护所有左端点 $l$ 对应的 $f(l,r)$。

令 $(u,v)$ 为关键点对当且仅当 $u < v$ 且 $dis(u,v)=f(u,r)$，令一个点为关键点当且仅当它在至少一个关键点对中。

将所有关键点对按照 $u$ 从小到大排序，令第 $i$ 个点对为 $(u_i,v_i)$，则有：

• $v_{i-1}\le v_i$。

• 若 $v_{i-1} < v_i$，则 $u_i=v_{i-1}$。

这可以通过考虑固定 $r$ 移动 $l$ 的过程进行说明。

令一段 $v_i$ 相等的关键点对组成一个 block，令其中 $u_i$ 的最小值为 block 的开头，$v_i$ 为 block 的末尾。

由上述结论，对于一个 block，上一个 block 的末尾等于它的开头。

考虑从 $r$ 移动到 $r'=r+1$ 时关键点对结构如何变化。先找到最小的 $p$ 满足 $(p,r')$ 为关键点对。

结论 $1$：若 $u$ 在 $r+1$ 处为关键点，则 $u=r+1$ 或 $u$ 在 $r$ 处也为关键点。

证明：$u$ 在 $r$ 处为关键点当且仅当 $f(u,r)>f(u+1,r)$，则结论显然。

结论 $2$：$p$ 一定为某个 block 的开头。

证明：

显然存在唯一的 $i$ 满足 $u_i=p$，且关键点对 $(u_i,v_i)$ 所在的 block 开头结尾分别为 $a,b$。

若 $p\neq a$，则可以发现 $a,p$ 均在 $M(p,b)$ 同侧（$dis(a,b)>dis(p,b)$），$b,r'$ 在另一侧（$dis(p,r')>dis(p,b)$）。由此可以导出 $dis(a,r')>dis(a,b),dis(a,r')>dis(p,r')$，这与 $p$ 的最小性矛盾。

因此 $p=a$。

假设我们已经得到 $p$。

考虑以 $p$ 为末尾的 block，令 $a$ 为这个 block 的开头。可以发现若 $a$ 不为第一个关键点，则 $(a,p)$ 依然为关键点对。证明方法与结论 $1$ 类似。因此 $a$ 前面的部分均不变。只需要在当前 block 中删除所有 $dis(u_i,v_i) < dis(p,r')$ 的关键点对。

$p$ 后面的部分会合并为一个开头为 $p$，末尾为 $r'$ 的 block。由结论 $1$，我们只需要删除其中的一部分关键点，剩余关键点均与 $r'$ 形成关键点对。

保留的关键点对应了与 $r'$ 距离的后缀最大值。

结论 $3$：关注 $p$ 后面的一个 block，一定是删除一段后缀的关键点（不包括 block 的末尾）。

证明：

令这个 block 的开头和末尾分别为 $a,b$，令 $a$ 与 $b$ 的路径上离 $r'$ 最近的点为 $c$。

从后往前依次考虑这个 block 中的每个关键点对 $(u_i,b)$，由直径性质可得 $M(u_i,b)\in P(a,b)$，且 $dis(M(u_i,b),b)$ 递增。

若 $M(u_i,b)\in P(b,c)$，则 $dis(b,r')=dis(b,M(u_i,b))+dis(r',M(u_i,b))=dis(u_i,M(u_i,b))+dis(r',M(u_i,b))>dis(u_i,r')$。因此这些 $u_i$ 一定全部被删除。

删除这段后缀之后，剩余的 $u_i$ 一定满足 $M(u_i,b)\in P(a,c)$。此时 $dis(u_i,r')-dis(u_i,b)=dis(c,r')-dis(b,c)$，为与 $i$ 无关的常数。

之前的结构保证了 $dis(u_i,b)$ 递增，因此 $dis(u_i,r')$ 递增，被删除的一定为一段后缀。

这些有关两点间距离的式子看起来很可怕，但实际上画个图毛估估一下就很好理解（

考虑直接暴力执行上述算法，即：

• 求 $p$ 的过程中暴力从后往前扫，一但不合法就停止。

• 对于末尾 $\ge p$ 的每个 block 暴力地从后往前依次判断每个关键点是否删除。

• 对于一个 block，其中没有被删除的部分增加量均一致，因此可以 $O(1)$ 得到对答案的影响。

每次判断均需要 $O(1)$ 次询问。

其询问次数复杂度正确的关键原因在于 $p$ 后面的部分均会被合并到同一个 block 中。

直接暴力地实现即可做到时间复杂度 $O(n^2)$，询问次数 $O(n)$。用链表维护即可将时间复杂度优化到 $O(n)$。

在本题中，为避免重复询问增大常数，需要对询问进行记忆化。

关于常数的分析，目前 std 可以估计出一个非常粗略的上界 $8n$。但笔者造了许多类型的数据测试下来均不超过 $5n$。

同时，std 的常数也有一些优化的空间。比如 $[1,r]$ 的任意子区间直径长度均可以通过之前的结构求出，std 为了实现方便，可能会在 $r$ 移动到 $r+1$ 的过程中再调用一些此类询问。

一些题外话：

在给定树结构的情况下，我们将区间直径扫描右端点 $r$，维护每个左端点 $l$ 对应的 $f(l,r)$ 的过程刻画为了 $O(n)$ 次区间加。若使用 $O(n)-O(1)$ RMQ，则我们在 $O(n)$ 的时间复杂度内解决了区间直径和。从区间直径问题的角度来说这是一个相对令人满意的结果。

龙门奇械

idea, data from command_block, solution from command_block zhoukangyang, std from zhoukangyang.

题外话：cmd 老师投这题的时是 $m\le 300,n\le 10^{18}$ 的版本。但是我发现如果数据范围是 $n,m\le 2.5\times 10^5$，那么就需要有更多的观察，而且还不需要 FFT，很优雅！于是就改成了现在的版本。

为了方便，在时刻 $0$ 前面加一秒，这一秒等待不会改变沙漏的状态。

令 $n\leftarrow n+1$，这样就转化为 $n$ 秒，时刻 $1,2,\dots,n$ 末尾各可以翻转或不翻转。

算法一

我会暴力！

$O\big(2^n\big)$ 枚举 $s_{1\sim n}$，然后 $O(nm)$ 模拟龙门的行为即可。复杂度 $O(nm2^n)$。

期望通过子任务 $1$，得分 $8$。

算法二

我会状压 DP！

记 $X=(x_1,x_2,\cdots,x_m)$ 表示某一时刻大小为 $1\sim m$ 沙漏的状态。

记 $dp[i][X]$ 表示第 $i$ 个时刻沙漏们状态为 $X$ 的方案数，枚举下一个时刻翻转与否，容易得到 $X$ 的变化，也就容易得出转移。

直接做复杂度是 $O(n(m+1)!)$ 的，如果观察 DP 数组的取值，可以发现只有 $2^m$ 种 $X$ 是有用的，复杂度可以改进为 $O(n2^m)$。

期望通过子任务 $2$，得分 $15$。结合算法一，得分 $23$。

算法三

我会分析性质！

当 $s$ 确定时，记 ${\rm calc}(M)$ 为机器放入容量为 $M$ 的沙漏时的输出。观察其性质。

任取 $s$ 打表观察（或观察样例）可以发现，${\rm calc}(M)$ 是关于 $M$ 的折线，斜率为 $0$ 或 $1$。

这容易用归纳法证明。

考虑用更简明的方式描述折线。将其差分，记 $w_i={\rm calc}(M)-{\rm calc}(M-1)$（不妨设 ${\rm calc}(0)=0$），则 $w$ 是一个从 $w_1$ 开始的无穷 $01$ 串。

初始时 $w_{1\sim m}$ 为全 $1$。观察机器的操作对 $w_{1\sim m}$ 的影响。

• 等待一秒，会将 $w_{1\sim m}$ 的第一个 $0$ 变为 $1$。

• 将沙漏翻转，会将 $w_{1\sim m}$ 的 $0,1$ 翻转。

给出的 $x_{1\sim m}$ 相当于确定了 $w_{1\sim m}$ 的末状态。

可以发现，$w_{1\sim m}$ 中 01 连续段的交替之处（即折线的拐点）具有重要地位。假设 $w_{1\sim m}$ 中有若干 01 连续段，某个段的末尾位置是 $t$。

• 引理：对 $w_t$ 的最后一次操作完成后（称作“锁定 $w_t$”），$w_t$ 及之后的位置都不会再被操作。

  证明：因为 $w_t$ 是连续段的结尾，目标中 $w_{t+1}\neq w_t$。

  若此时 $w_t=w_{t+1}$，需要想办法修改 $w_{t+1}$，然而因为两者相等且 $w_t$ 在 $w_{t+1}$ 之前，只能先修改 $w_t$，这与“最后一次修改”矛盾。

  若此时 $w_t\neq w_{t+1}$，想要修改 $w_{t+1\sim+\infty}$，需要操作时 $w_{1\sim t}=1$，则 $w_{t+1}=0$。只能翻转 $w_{t+1}$，转化为 $w_{t_i}=w_{t+1}$ 的情况。$\square$

记 $w$ 中第 $i$ 个 01 连续段的末尾为 $t_i$。

锁定 $w_{t_i}$ 时，必须保证之后的 $w$ 都已经正确，且根据修改的规则，锁定后必然有 $w_{1\sim t_i}=1$。（锁定后必须瞬间翻转，否则下一秒会改动 $w_{t_i+1}=1$）

这表明，锁定 $w_{t_i}$ 后（包括最后一次翻转后），$w$ 的状态居然是唯一的！具体地，$w_{1\sim t_i}=0$，且后面的部分不能再修改。

于是，我们可以把操作过程分成若干个阶段考虑。

具体地，设 $E$ 为初始状态，$S_i$ 为锁定 $w_{t_i}$ 后的状态，整个操作过程可以分成下列阶段

$$[E,S_k],(S_k,S_{k-1}],\dots(S_2,S_1]$$

其中阶段 $(A,B]$ 表示从状态 $A$ 出发到达状态 $B$，且其中不再回到状态 $A$（可以多次经过状态 $B$）。

对于第 $i$ 个阶段，记花费 $k$ 秒（时刻 $1,2,\dots,k$ 可选择是否翻转）的方案数为 $F_i[k]$。将各个 $F$ 数组加法卷积，即可得到答案。

• 如何计算 $(S_{i+1},S_{i}]$

在 $S_{i+1}$ 中，$w_{1\sim t_{i+1}}$ 都是 $0$。在 $S_i$ 中，$w_{1\sim t_i}$ 是 $0$，$w_{t_i+1}\sim w_{t_{i+1}}$ 是 $1$。

因为 $w_{t_{i+1}}$ 已经锁定，假设我们污染了 $w_{t_i+1}\sim w_{t_{i+1}-1}$ 中的某个 $w_p$，只能再操作一次 $w_p$ 把它改回来。为了这样做，我们会将 $w_{1\sim p}$ 修改到完全一样（都为 $1$）。

取 $p$ 是最右侧被污染的位置，不难发现，一旦产生污染，只能回到初始状态 $S_{i+1}$，故不能有任何污染。所以我们能操作的只有 $w_{1\sim t_i}$。

记 $R=t_i$，记 $x$ 为 $w_{1\sim R}$ 中的 1 的个数，初始时 $x=0$。最终目标是 $x=0$，且翻转次数为奇数。

容易列出 DP：

记 $g[k][c][0/1]$ 为共 $k$ 秒，$x$ 取值为 $c$，翻转次数的奇偶性为 $0/1$ 的方案数，边界是 $g[0][0][0]=1$，有转移

$$ \begin{aligned} g[k][c][e]&\to g[k+1][c+1][e]&(c< R)\\ g[k][c][e]&\to g[k+1][R-c-1][\neg e]&(c< R) \end{aligned} $$

（第二行是先再等一秒再翻转）

其中要 BAN 掉 $g[k][0][0]$，因为这回到了初始状态。最终需要的答案是 $g[k][0][1]$。

• 特殊处理 $[E,S_k]$

假设最右侧的连续段是 $w_{t+1\sim m}$，想要从初始状态到锁定 $w_t$。区别在于，可以随意污染 $w_{m+1\sim +\infty}$。

可以分为两个阶段。

一阶段：从 $w$ 全 $1$ 出发，到达 $w_{1\sim m}=0$，期间允许污染 $w_{m+1\sim +\infty}$。

二阶段：从 $w_{1\sim m}=0$ 出发到锁定 $w_t$，不允许回到 $w_{1\sim m}=0$。

一阶段的 DP 如下：

记 $x$ 为 $1\sim m$ 中 $1$ 的个数，初始时 $x=m$。

记 $g[k][c]$ 为共 $k$ 秒，$x$ 取值为 $c$ 的方案数，边界是 $g[0][m]=1$，有转移

$$ \begin{aligned} g[k][c]&\to g[k+1][\min(c+1,m)]\\ g[k][c]&\to g[k+1][m-\min(c+1,m)] \end{aligned} $$

最终需要的答案是 $g[k][0]$。

二阶段中，若要修改 $w_{m+1\sim +\infty}$，需要 $w_{1\sim m}=1$，而这早晚会变成 $w_{1\sim m}=0$，于是 $w_{t+1\sim +\infty}$ 都不能修改，和上文相同。

（若目标的 $w_{1\sim m}=1$，可以不经过 $w_{1\sim m}=0$ 的阶段，但凑巧不需要特殊处理）

• 复杂度分析

易知 $\sum t_i\leq n$，故连续段个数是 $O(\sqrt{n})$ 的。

求各个 $g$ 的复杂度总和是 $O(n\sum t_i)=O(n^2)$，将它们暴力卷积的复杂度是 $O(n^{2.5})$。

期望通过子任务 $1,3$，得分 $45$。结合算法二，得分 $60$。

算法 $\pi$

$n\leq 10^{18}$ 怎么做？

承接算法三的思路。根据线性递推的结论，$g$ 的 DP 可以看做大小为 $O(R)$ 的矩阵的幂构成的数列，是一个 $O(R)$ 阶线性递推。

使用 BM 算法，可以在 $O(\sum t_i^2)\leq O(m^3)$ 的时间里求出各个 $g$ 的分式形式 $P_i(x)/Q_i(x)$。

将所有分式相乘（用分治 FFT 将分子分母分别相乘），总复杂度 $O\big((\sum t_i)\log(\sum t_i)\big)\leq O(m^2\log m)$。

然后，我们可以得到答案的分式 $P(x)/Q(x)$（上下各有 $O(m^2)$ 项），其远处项系数可以 $O(m^2\log m\log n)$ 求出。

总复杂度 $O(m^3+m^2\log m\log n)$。可以承受 $n\leq 10^{18},m\leq 300$ 的数据范围。

算法四

上面的题解都是 cmd 写的，下面的题解是我写的。所以我们从头开始考虑问题。

我菜，所以很多地方都是毛估估的，毛估估的地方应该也不会影响正确性啥的。

首先，除去最后一步操作，我们可以把沙漏看成是 一个点在数轴上面走，每次 $+1$ 或 $-1$，走的时候对 $0$ 取 max 并对 $m$ 取 min。加上最后一步操作后，需要把所有 $x_i$ 变成 $i-x_i$ 再做一遍。

如果翻转这个 $+1/-1$ 的操作序列，并对操作做前缀得到数组 $a$。画出所有 $(i,a_i)$，我们将得到一张折线图。

考虑给定沙漏的大小 $m$ 时，怎么算沙漏最终的数：从前往后算出 $a$ 的前缀最小值 $premin_i$ 和前缀最大值 $premax_i$。找到第一个 $premax_i-premin_i=m$ 的位置 $i$（没有则取 $n$ 位置），可以发现答案是 $premax_i$。

利用 $v_m=x_m-x_{m-1}$ 的值，我们讨论 $m$ 找到的位置相对 $m-1$ 找到的位置有哪些变化：

如果 $v_i=0$，那么可以是

• $m$ 的 $premax_i$ 被更新了。
• 没有 $premax_i-premin_i=m$ 的位置了。

如果 $v_i=1$，那么只能是

• $m$ 的 $premax_i$ 被更新了。

根据给定的答案序列，除去最后一段 $v_i$ 的全 $0$ 段（这一段 $0$ 可能是没有 $premax-premin=m$ 的位置），我们可以知道这个折线前若干次更新 $premin$ 和 $premax$ 的顺序。最后一个全 $0$ 段可以按 $premax_n-premin_n$ 和 $m$ 的大小关系进行分讨。

注意到一次更新 $premin$ 和一次更新 $premax$ 都是走一段有起点终点高度、带上下边界的折线，最终的答案就是将这些折线拼接起来，也就是关于步数的 $\rm OGF$ 相乘。

暴力算可以得到 $\mathcal O(nm^2)$、$\mathcal O(n^2m)$ 或 $\mathcal O(nm\log n)$ 的时间复杂度。以此为基础还能得到一些形如 $\mathcal O(n \sqrt n\log n)$ 的复杂度。

先考虑每一步的 $\rm OGF$ 怎么算。

考虑利用反射容斥，把终点按照边界线反射。反射容斥会将终点反射成很多很多的高度不同的带权终点，并去掉上下边界的限制。

对于一个终点，设其和起点的高度差的绝对值是 $h$，那么其贡献的 $\rm OGF$ 就是 $\sum_{i=0} \binom{2i+h}{i} x^{2i+h}$。利用 广义二项级数 刻画之，得到其 OGF 为 $\frac{(x\mathcal{B}_2(x^2))^h}{-1+2\mathcal{B}_2(x^2)^{-1}}$。

下面的那些锤子是不变的，变的只有上面的东西。我们发现，把这些 OGF 乘起来的时候，其实只用在意这些 $h$ 的总和（而且还只用求前 $n$ 项）。

所以说，我们只需要将这些 $\sum_{h} w_i x^{h_i}$ 乘起来就行了。这个 OGF，其实一定是一些 $x^r(1-x^{a})^{b}$（$b$ 是可以为负的整数） 的乘积。

而在分母中，$\frac{1}{-1+2\mathcal{B}_2(x^2)^{-1}}$ 可以被视作是 $\frac{\mathcal{B}_2(x^2)}{-\mathcal{B}_2(x^2)+2}=\frac{\mathcal{B}_2(x^2)}{1-(x\mathcal{B}_2(x^2))^2}$，可以被写成 $\frac{1}{1-x^2}$ 复合 $x\mathcal{B}_2(x^2)$ 和一些额外的 $\mathcal{B}_2(x^2)$。

乘这些 OGF 当然可以用 $\ln-\exp$ 的方法做到 $\mathcal O(n\log n)$，但是实际上 FFT 是可以被避免的！

有结论：最终的 $x^r\prod_i (1-x^i)^{v_i}$ 的 $\sum |v_i|$ 是 $\mathcal O(\sqrt n)$ 级别（含分母中的 $(1-x^2)^{-1}$）。

这是为什么呢？我们发现，对于连续的一段 $0$ 或 $1$，他们贡献的多项式乘起来事实上只有 $\mathcal O(1)$ 项。这里还有一个更直观的理解：一段连续的 $0/1$ 可以被合起来，合成一个反射容斥。

而新连续段开启的时候，即 $v$ 数组 $01$ 交替的时候，设交替位置为 $t$，那么一定需要 $t$ 的时间来交替，所以有解时交替的次数只有 $\mathcal O(\sqrt n)$。

在处理最后一段 $0$ 的时候，分 $premax_{n}-premin_n\ge m$ 和 $premax_{n}-premin_{n} < m$ 分开计算。第一类就是按前面的做法做整个字符串，随后乘 $\frac{1}{1-2x}$ 的生成函数。这个东西也可以看成成终点任意的 GF，也可以写成一个多项式复合 $x\mathcal B(x^2)$，处理方法和反射容斥类似；第二类的最后一段则相当于是乘 起点固定、终点不固定、有上下界的反射容斥。仍然可以类似终点固定地做，通过一些精细的观察也可以线性加入其贡献。

最后我们需要求的是 $[x^n]\sum_{i} v_i x^{i+b} \mathcal B(x^2)^{i+a}$ 状物，利用一些广义二项级数的结论就可以简单计算。

时间复杂度 $\mathcal O(n \sqrt n)$（不需要 FFT） 或 $\mathcal O(n \log n)$ 或 $\mathcal O(n\log^2 n)$，期望得分 $100$。

再见，癸卯！

转眼间，魔幻的 2023 就结束了，龙年到来了。

小青鱼敏锐地发现了这一点，于是决定越过高高的龙门，成为大青龙。但是仅凭小青鱼的力量是越不过龙门的。你能帮帮他吗？

我们将于 2 月 8 日下午 13:00 到 18:00 举办一场 Goodbye Guimao 比赛。比赛时间为 5 小时，共 5 道题。

赛制采取 OI 赛制，这也意味着只计入最后一次提交结果。这场比赛有很多很趣味的题目，大家一定不要错过！

再次提醒大家比赛中途只测样例，最后会进行最终测试，把所有提交记录重测。

出题人：1kri，command_block，huahua，cmll02，tzc_wk，Kubic。

这场成绩将计入 rating。

参加本次比赛将有机会获得 UOJ 抱枕！获奖条件的 SHA256 码为 9599bd93780fb9f736281be425b0ba0e92a74fbceb0dc2dfdb9069c186b2524a。比赛结束后将公布条件。

UPD: 恭喜前5名的选手！

1. gyh20
2. 275307894a
3. JohnAlfnov
4. Nesraychan
5. shr

Qingyu@mainhost:~$ echo -n "非零得分倒数模998244353最大，如果有多个取罚时最大的" | sha256sum
9599bd93780fb9f736281be425b0ba0e92a74fbceb0dc2dfdb9069c186b2524a  -

恭喜 paul2008 获得 uoj 抱枕！

石子合并

idea, data, solution from myee

萌萌出题人给大家带来了一道萌萌签到题！

$n\le4$，$m\le8$

直接 $O(n^m)$ 暴力枚举所有石子放到各个石堆的情况，然后暴力 check 就好啦！

注意处理相同元素时不要计重。

$n=2$，$m\le20$

做法同上，但是 check 部分的常数要写的好一点。

$n\le100$，$m\le300$，$o=1$

对于 $o=1$ 的情况，我们容易发现所有初始石堆内的石子编号都是不降的！

我们不妨考虑 dp，从小到大依次加入石子。

每次加入一段相同的石子时，我们可以选择给已有的石堆往末尾分别加入若干，或者加入某些还没有出现过的石堆。

dp 时需要记录当前已经考虑到哪个石子，以及已经有多少个石堆已经非空了。

复杂度容易做到 $O(n^2m)$。

$n\le100$，$m\le300$，$o=0$

现在有下降的石子编号了，我们咋办？

我们考虑一下归并的过程：如果第一个石堆里的某个石子 x 后面有一堆比当前石子小的石子，那么当合并时加入 x 后，x 后面一堆编号比 x 小的石子会跟着一起加入，而且仍然保持跟在 x 后面。

因此，我们可以把这些 x 后面比 x 小的石子“归附”到 x 上，容易发现合并过程是不变的！

对于最后合成的序列，当一个石子比前面的任意某个石子小的时候，其一定归附在前面的某个石子上，因此删除其不影响答案！

这样我们就转化成了石子编号不降的情况，直接采用 $o=1$ 时的算法即可。

$n\le1000$，$m\le3000$

同样我们只考虑 $o=1$ 的情况。

之前我们的 dp 没有前途，考虑有没有什么比较优秀的做法。

我们观察到，之前的做法复杂度比较高是因为题目里这个「非空」的限制很棘手。

如果没有这个非空的限制，那我们怎么计数呢？

我们假设有 $c_j$ 个石子编号为 $j$，当前有 $n$ 个石堆，而石堆可以为空，那么答案 $f_n$ 为

$$ f_n=\prod_{j=1}^m\binom{c_j+n-1}{c_j} $$

理由是显然的：只用对每种编号的石子考虑插板法即可。

然而答案要求每个石堆均非空，我们设这样的答案为 $g_n$。

我们尝试考察 $f_n$ 和 $g_n$ 的关系，容易发现

$$ f_n=\sum_k\binom nkg_k $$

理由是，我们可以枚举当前哪些石堆是非空的，而剩下的石堆都是空的。

那么很自然的考虑二项式反演（不会？可以去 vfk 的博客里学）：

$$ g_n=\sum_k(-1)^{n-k}\binom nkf_k $$

因此我们只用求出 $f_0\sim f_n$，就可以解出 $g_n$ 辣！（你也可以直接使用组合意义容斥得到一样的结果）

直接按照第一个公式暴力处理就是 $O(nm)$ 的了。

$n\le2\times10^5$，$m\le5\times10^5$

我们发现问题的关键在于要快速算出 $f_0\sim f_n$。这咋办？

我们考虑观察一下特殊性质。

特殊性质：$a_i\le20$

这种情况下我们只用枚举 $j\le20$ 的情况，更大的情况因为 $c=0$ 而不用考虑。

特殊性质：$c_j\le5$

我们考虑到对于同样的 $c$，$\binom{c+n-1}{c}$ 是相同的，我们不妨考虑统计有多少个数 $j$ 对应的 $c_j=k$，即记

$$ t_k=\sum_{j=1}^m[c_j=k] $$

那么我们就有

$$ f_n=\prod_k\binom{k+n-1}{k}^{t_k} $$

直接处理即可。

一般情况

实际上有多少 $k$ 满足 $t_k>0$ 呢？

我们注意到

$$ \sum_{k>0}kt_k=\sum_jc_j=m $$

因此实际上满足 $t_k>0$ 的 $k$ 不会多于 $O(\sqrt m)$ 个！

直接暴力计算所有 $f$ 即为 $O(n\sqrt m)$ 的。

总复杂度 $O(m+n\sqrt m)$，可以通过本题。

快速幂的 $\log$ 去哪了

那肯定有同学要问了：快速幂部分的 $\log$ 怎么没有进入复杂度呢？

其实是因为，我们计算 $f$ 的复杂度实际上为

$$ O(n\sum_{t_k\ge1}\log t_k) $$

而

$$ \sum_{t_k\ge1}(1+\lfloor\log_2t_k\rfloor)=\sum_{p\ge0}\sum_k[t_k\ge2^p]=\sum_{p\ge0}\sum_k[\lfloor\frac{t_k}{2^p}\rfloor>0] $$

而我们显然有

$$ \sum_kk\lfloor\frac{t_k}{2^p}\rfloor\le\frac m{2^p} $$

因此

$$ \sum_{p\ge0}\sum_k[t_k\ge2^p]=O(\sum_{p\ge0}\sqrt{\frac{m}{2^p}})=O(\sqrt m) $$

从而计算 $f$ 的复杂度仍然为 $O(n\sqrt m)$。

一个更优的做法

我们考虑到

$$ f_{n+1}/f_{n}=\frac{1}{n^m}\prod_{j=1}^m(n+c_j) $$

因此问题的关键在于对 $k=1,2,\dots,n$，计算出

$$ \prod_{j=1}^m(k+c_j) $$

使用多项式多点求值算法或者多项式连续点值平移可以直接做到 $O(m\log^2m)$。

能不能再给力点啊？

我们注意到 $0 < k+c_j\le n+m<\textbf{Mod}$，其中 $\textbf{Mod}=998244353$，因此我们设在以原根为 $g=3$ 意义下 $j$ 的离散对数为 $s_j$，满足 $g^{s_j}\equiv j\pmod{\textbf{Mod}}$，那么我们就只用对 $k=1,2,\dots,n$ 求出

$$ h_k\equiv\sum_{j=1}^ms_{k+c_j}\pmod{\textbf{Mod}-1} $$

很显然我们有

$$ h_k\equiv\sum_{j=1}^ms_{k+j}t_j\pmod{\textbf{Mod}-1} $$

这就是一个差卷积的形式，使用 MTT 即可在 $O(m\log m)$ 的时间内解决。

问题来到计算 $s_{1\sim n+m}$ 上，我们使用线性筛的方法，只用计算质数处的 $s_p$ 值，然后直接套用 Pohlig–Hellman algorithm 即可。由于 $998244353$ 的优秀性质，计算单个离散对数的复杂度可以近似认为是 $O(\log\textbf{Mod})$ 的。

总复杂度不会超过 $O(m\log\textbf{Mod})$。

街头庆典

idea, data from 1kri, solution from 1kri, zhoukangyang

分析

考虑找到一组割掉边数最少的最优解，去分析这种最优解的结构。在这组最优解中，每条割掉的边都是不能省去的。

那么对于每条被割掉的边，它的两个端点一定是所在连通块中某条直径的端点。否则如果不割掉这条边，直径长度和也不会变大。

进一步分析，对于一个连通块，找到它的中心（直径的中点，有可能在某条边中间），那么它外围的所有端点（除了原树中的叶子节点）与这个中心的距离一定相等。换言之，每个连通块都恰包含了到某个中心距离不超过一个定值的所有节点。

我们考虑以某个原树的直径端点为根，这时我们发现，对于最终的每个连通块，都有一条直径以其深度最浅的点为端点。

算法一

以某个直径端点为根。

考虑 $\text{dp}$，设 $f_u$ 表示 $u$ 到父亲的边被割掉，$u$ 子树内的最小代价。然后设 $s_{u,d}$ 表示 $u$ 子树内，割掉所有与 $u$ 距离为 $d$ 的边，代价之和。

我们记 $g_{u,i}$，它的含义是 $u$ 号点所在连通块的中心在 $u$ 子树内，且到其所在连通块内深度最浅点的距离为 $i$，最小贡献。显然 $g_{u,0}$ 表示的就是 $f$。

对于 $g$ 数组，分三种情况转移：中心是 $u$，中心在 $u$ 到某个儿子的边上，中心在 $u$ 的某个儿子的子树内。

对于三种情况，都容易写出 $g$ 的转移式。

以第三种情况为例，$g_{u,i} = \min\limits_v g_{v,i+1}+s_{u,i}-s_{v,i-1}$。其含义是，因为连通块是满的，所以 $u$ 子树中除 $v$ 子树以外要割掉恰好某个深度的所有边。

直接转移，时间复杂度 $O(n^2)$，可以得到 $40$ 分。

算法二

我们对树进行长链剖分，对于每条长链同时处理答案。

假设现在处理的是包括根的长链，对于其余长链都已计算得到答案。

考虑一种特殊的情况，这条长链上的点所在的所有连通块的中心都在长链上。不难发现，这个限制等价于每个连通块都有直径完全在长链上。

我们设 $val_{l,r}$ 表示长链上第 $l$ 到第 $r$ 个节点构成了一个连通块直径。那么 $val_{l,r}$ 大约形如 $\sum\limits_{i=l}^r s'_{i,\min(i-l,r-i)}$。其中 $s'_{i,d}$ 为长链上第 $i$ 个节点，割掉长链外所有距离其为 $d$ 的边的贡献。

改令 $f_l$ 表示长链上第 $l$ 个节点的原 $f$ 值。那么 $f_{l}$ 形如 $\min\limits_{r=l}^t f_r+val_{l,r}$ 再加上一些只与 $l$ 和 $r$ 有关的简单贡献（其中 $t$ 为长链上的节点个数）。

我们从大往小处理每个 $l$，类似扫描线，动态更新每个 $r$ 的 $val_{l,r}+f_r$。考虑从 $l$ 处理到 $l-1$，在所有 $val_{l,r}$ 计算的过程中有哪些 $i$ 的贡献会发生变化。

当 $r-i \leq i-l$ 或 $i-l > \text{mx}_i$ 时，$i$ 就不会再发生变化了（$\text{mx}_i$ 表示 $i$ 下挂的短子树的最大深度）。

又由于每条长链下挂的短子树最大深度和是 $O(n)$ 的，所以发现每个 $i$ 的贡献发生变化的时刻一共只有 $O(n)$ 个。

对于每次 $i$ 的贡献发生变化，它恰会同时影响一段后缀的 $r$ 的 $val$ 值。这是不难理解的，因为它只会影响 $i-l < r-i$ 的 $r$，且影响只会与 $l$ 有关而与 $r$ 无关。

长剖维护 $s'$ 的值，用线段树优化 $\text{dp}$，能做到 $O(n \log n)$ 的复杂度。

然而这个算法是建立在只处理包括根的长链且这条长链上的点所在的所有连通块的中心都在长链上的假设上的，无法获得什么分数。

算法三

还是考虑只处理包括根的长链，而允许长链上的点所在的连通块的中心在短子树内（或下挂短子树的边中）。

再重新考虑算法一中的 $g$ 数组。发现 $g$ 的第二维范围不能超过 $u$ 子树中的最大深度，那么就自然想到长链剖分。

而这里不能直接长链剖分，是因为当中心在长链上时，第一、二种转移需要数组对位取 $\text{min}$，而且位数是整个子树而非短子树的最大深度，长链剖分无法保证时间复杂度。

而对于只考虑连通块中心在每条长链下挂的短子树内（或连接其的边上）时，就可以规避掉影响时间复杂度的部分了。

发现长链剖分可以解决所有中心不在长链上的转移，而算法二中的扫描线可以解决所有中心在长链上的转移，这两部分拼在一起就得到了所有可能的转移！

那么我们直接同时施加两种方法，就可以得到所有正确的 $f$ 值了！

这个算法只考虑了处理包括根的长链的情况，而没有考虑对于其它长链怎么计算 $g$ 的值，因而也无法获得什么分数。

算法四

现在唯一的问题是要求出 $g$ 值，并且我们发现，在计算过程中，只用到了链顶的 $g$ 值。

我们假设长链上的节点是从 $0$ 编号的，并在长链上新增 $t$ 个虚点，由深至浅标号为 $-1,-2,...,-t$。

那么我们发现，$g_{0,i}$ （这里 $g$ 的第一维同样用点在长链上的位置表示）的含义与 $f_{-i}$ 的含义几乎相同！

唯一的区别是，$-i$ 所在连通块的直径中心不能在 $0$ 以上。这等价于，要么中心在短子树上，要么直径下端点（$r$）不小于 $i$。前者和之前是完全一样的，后者只要改一改原来线段树查询的区间，而对于其它过程都是一样的！

这样，我们通过类似求 $f$ 的过程就可以求出所有的 $g_{0,i}$ 了。

这时，我们的算法不建立在任何假设之上，可以以 $O(n \log n)$ 的时间复杂度通过所有数据。

更进一步，发现线段树的部分是可以由并查集替代的，就能做到 $O(n\alpha(n))$ 甚至是线性！

由于时间限制十分宽裕，只要复杂度正确的做法都能通过。如果不会写复杂的长剖，甚至可以全部用线段树和线段树合并替代。

铁轨回收

idea, data, solution from zhoukangyang

算法 1

我会观察数据范围！

发现有 $B_n = 0$ 的分，输出 $1$ 即可。期望得分 $10$ 分。

算法 2

我会暴力！

模拟题意，时间复杂度 $\Theta((n-1)!)$，拼上算法 1 期望得分 $20$ 分。

算法 3

从前到后 DP，记录一个长度为 $B_n+1$ 的数组 $c$。$c_i$ 代表了后面的点中被加了 $i$ 的有 $c_i$ 个（如果被加了超过 $B_n$ 那就认为加了 $B_n$）。

期望得分 $50$ 分。

算法 4

留给实现得不好的正解。

而 Melania 同学用厉害 DP 过掉了 $B_n \le 10$，在这里向他献上真挚的膜拜！

期望得分 $70 \sim 80$ 分。

算法 5

在后面的描述中，我们记题面里的 $A_i$ 为 $A'_i$，执行完 $1 \sim i - 1$ 的操作后第 $i$ 个仓库有的铁轨长度为 $A_i$。

假设第 $i$ 个仓库选择了第 $j$ 个仓库放铁轨放置，我们就连一条 $i \to j$ 的边。显然这些边形成了一颗以 $n$ 为根的有根树。

我们考虑统计执行完 $1 \sim i - 1$ 的操作后，$A_i=j$ 的方案数：

• 对于 $j < B_i$，我们只要统计 $[A'_i + \sum_{t \in son_j} A_t = j]$ 的方案数即可。
• 对于 $j = B_i$，我们用总方案数减去 $j < B_i$ 的方案数。

这样，我们可以枚举答案 $i$，然后从后往前做 DP：

记 $dp_{pos,S,k}$ 表示在第 $pos$ 个位置之后的点中，需要被连的 $A$ 之和 的集合为 $S$ ，且有 $k$ 个点可以任意接受边（对于一个选择了统计 “总方案数” 的点，他的子树是什么值不重要，因此他前面的任意点都可以向他连边）。

转移可以考虑以下几种情况：

• $fa_{pos}$ 为那 $k$ 个点中的一个，此时 $k \leftarrow k+1$。
• 统计 $A_{pos} = B_{pos}$，并选择”统计总方案数“：此时 $k \leftarrow k+1$，并选择 $S$ 中的一个元素减去 $B_{pos}$。
• 统计 $A_{pos} = B_{pos}$，并选择”减去 $j < B_{pos}$ 的方案“，即做 $-1$ 的贡献。此时选择 $S$ 中的一个元素减去 $B_{pos}$，然后在 $S$ 中加入一个 $t < B_{pos}$ 的 $t-A'_{pos}$。
• 统计 $A_{pos} < B_{pos}$ 的贡献。此时选择 $S$ 中的一个元素减去 $A_{pos}$，然后在 $S$ 中加入 $A_{pos}-A'_{pos}$ 。

注意到 $S$ 中的元素和是单调不升的，因此状态数只有分拆数级别！

我们再把 DP 倒过来做（或者说，转置原理），就可以用一遍 DP 求出答案了。

预处理一下状态之间的转移，时间复杂度上界为 $O(n^2 \pi (B_n) B_n^{1.5})$，期望得分 $100$ 分，其中 $\pi(B_n)$ 是 $B_n$ 的分拆数。