今年的管理员们 djq_cpp, he_____he, hehezhou, QAQAutoMaton 在过去的一年中，成功举办了两场 UR，两场国家候选队互测，一场 UER，还有一切如常的 Goodbye Round & UNR。和以前的鸽子们相比业绩也不算太差。

一年 NOI 过去，今年的管理员们也该到站下车了。从很早很早以前，早在我还不敢尝试做 UOJ 题的时候，我就十分敬佩 UOJ。vfk，邓老师，还有所有的管理员都满怀对 OI 的热情，承担着 UOJ 管理的职责，尽自己的力量去改善和帮助 OIer 这个大家庭。他们无私奉献的精神让我钦佩。也许正因如此，作为 OIer，这里让我感受到了难得的归属感。只不过当时的仰望天空的我从来没有想过有一天自己也能站在这个位置。

一年来，中规中矩，办了若干场比赛，传了一些题目。在上届管理 skip2004 的指导下，我们这一年的管理工作做得也不算太糟。我们管理员群的群名叫 “咕”，群头像则是 UOJ 的标识上放一只鸽子。在群里一声声 "@he_____he 暂别" 中，这不能再咕下去的暂别也即将揭晓下一任的 UOJ 管理员。他们仍将继续奋斗，传承这无比纯粹而炽热的 UOJ 精神。

他们是：

ix35, 127, qingyu, csy2005

真诚地祝愿 UOJ 越办越好。UOJ 永不落幕！

国家候选队互测 2022 Round #1 & #2 将于 1 月 8 & 9 日下午 13：00 举行！每场比赛将进行 5 个小时，共三道题。

有一些候选队员在冬令营之前站了出来，想要在选拔国家队（交论文）之前再给 uoj 投一些题，于是就有了这两场比赛，希望大家玩得开心！

本次比赛将采取 IOI 赛制。每题最多提交 32 发，可以实时查看成绩，最终取分数最高的提交，若有多发分数最高的提交，则取时间最早的，且可以查看排行榜。

Round #1 出题人：he_____he, hehezhou, djq_cpp

Round #2 出题人：127, sslz_fsy

这两场比赛计入 rating，涨跌幅度为正常比赛的 $\frac{1}{4}$。

民意调查

idea from skip2004, solution, data from he_____he.

算法一

我会暴力！枚举所有子集并计算平均数和中位数，复杂度 $O(2^{n}n)$，期望得分 $20$ 分。

算法二

先把整个序列从小到大排序。将子集看为一个排序后序列的子序列 $a_{b_1},a_{b_2}\dots ,a_{b_{2k+1}}$，中位数看做 $a_{b_{k+1}}$ 这一项。

这样就可以枚举中位数在序列中的位置，再枚举 $k$ 的大小，对于平均数和中位数关系的限制可以对两边分别进行背包，就可以求出答案。

时间复杂度 $O(n^{4}V)$，空间复杂度 $O(n^{2}V)$，可以通过前三个子任务，期望得分 $60$ 分。

算法三

注意到每次的背包一定是一个前缀和一个后缀，所以我们可以预处理出每个前缀和每个后缀的背包并对一边做前缀和。这样每次枚举完中位数和 $k$ 之后只需枚举某一边选出数字之和即可。

时间复杂度 $O(n^{3}V)$，空间复杂度 $O(n^{3}V)$，可以通过前四个子任务，期望得分 $90$ 分。

算法四

注意到我们可以以从前到后的顺序枚举中位数，这时对于前缀的背包就可以自然地每次加入一个数，而不用保留之前那些前缀的背包。

对于后缀的背包，我们可以先处理出所有数的背包，每次从前到后扫中位数时，将一个数从背包中移出，就可以得到当前想要求出的后缀的背包了。

时间复杂度仍为 $O(n^{3}V)$，空间复杂度 $O(n^{2}V)$，可以通过所有子任务，期望得分 $100$ 分。

地铁规划

from wlzhouzhuan.

算法一

对于每个左端点，暴力扫右端点直至 check 为零，然后 undo 回去即可。

操作次数 $\frac{n^2}{2}$，可以通过子任务 1，期望得分 $10$ 分。

算法二

由于可撤销 dsu 能撤销最近一次的操作，而我们需要撤销最远一次的操作，不难想到采用一种“双栈结构”来维护它。

具体地，我们加入 dsu 的边可以用一个栈维护。其中已经翻转过的边用 0 表示，未翻转过的边用 1 表示。我们只要时刻保证栈顶为 0 边即可直接进行 undo 操作。

对于当前左端点的查询，它会使得栈顶加入若干个 1 边。考虑暴力弹栈顶直至弹出来的 0 边和 1 边数量相等，然后把 1 边按原顺序加回栈，再把 0 边按原顺序加回栈，这样就满足栈顶为 0 边，可以直接 undo 了。特殊情况是把栈弹空了仍然不满足 0 边和 1 边数量相等，此时如果栈中压根没有 0 边，我们就把所有 1 边倒着加回栈中，这样所有 1 边变成了 0 边；否则我们仍按照上述方式加回栈中即可。

出题人只会把它卡到根号量级，可以通过前两个子任务，期望得分 $40$ 分。

算法三

subtask2 的根号做法、不会证操作次数的乱搞做法以及单 $\log$ 的大常数写法均可能通过子任务 3。

算法四

结合二进制位去考虑该问题。

我们每次额外加一个计数器 $\text{top}$，表示栈内有多少个已经翻转过的边（即 0 边）。

• 如果栈的头未被 $\text{rev}$ 过，则一直弹，然后再弹 $\text{lowbit(top)}$ 个 $\text{rev}$ 过的边；
• 如果栈的头被 $\text{rev}$ 过，啥事都不干。

执行完上述流程后，可以发现栈一定 $\text{rev}$ 过，并且一定是左端点 $l$ 对应的边，因此直接 undo，并 top-- 即可。

考虑分析该做法的复杂度。

我们定义一个点的位前进表示它在未 $\text{rev}$ 状态时击败了一个位的状态，位后退表示它在 $\text{rev}$ 状态时回退一个位的状态。不难发现，我们记一个点的势能为它被位前进+位后退的总次数，即为 $\mathrm{\Phi }(u)$，则总操作次数为 $\mathcal{O}(\sum _{i=1}^n\mathrm{\Phi }(i))$。

对于未被 $\text{rev}$ 的边，它在自身位于栈尾连续段内才会被执行位前进，而想要进行挪动的代价是击败一个 $\text{top}$ 的位，即它至多进行 $\log n$ 次位前进。

对于已被 $\text{rev}$ 的边，它需要在被 $\text{rev}$ 的边中处于末 $\text{lowbit}(top)$ 条边里才会被执行位后退，并且在后退以后，$\text{top}$ 从 $\text{lowbit}$ 处被摊平成若干个 $1$ （例如原来 top=1010000 ，则 top-- 后末尾的位均被摊成了 $1$，即 top=1001111），所以它至多进行 $\log n$ 次位后退。

因此 $\mathrm{\Phi }(x)=\log n+\log n=\mathcal{O}(\log n)$，可以通过所有子任务，期望得分 $100$ 分。

国王出游

from ezoilearner.

算法一

答案即为 $\frac{n!m!}{4^T}[x^n{y}^m](e^{Ax}+e^{-Bx}+e^{Cy}+e^{-Dy}{)}^T$。有

$$[x^n{y}^m](e^{Ax}+e^{-Bx}+e^{Cy}+e^{-Dy}{)}^T=T!\sum _{i+j+k=T}\frac{4^k}{k!}[x^n]\frac{(e^{Ax}+e^{-Bx}-2{)}^i}{i!}[y^m]\frac{(e^{Cy}+e^{-Dy}-2{)}^j}{j!}$$

令

$$a_i=[x^n]\frac{(e^{Ax}+e^{-Bx}-2{)}^i}{i!},b_j=[y^m]\frac{(e^{Cy}+e^{-Dy}-2{)}^j}{j!}$$

注意到 $[x^0](e^{Ax}+e^{-Bx}-2)=0$，所以有 $\mathrm{\forall }i>n,a_i=0$，同理 $\mathrm{\forall }j>m,b_j=0$。

令 $M(x)=\left(\sum _{i=0}^n{a}_i{x}^i\right)\left(\sum _{j=0}^m{b}_j{x}^j\right)$，所求即为 $n!m!\sum _{i=0}^{n+m}{4}^{i-T}(\genfrac{}{}{0ex}{}{T}{i})i![x^i]M(x)$，只需快速求出 $M(x)$ 即可。

所以问题变成了快速计算 $\{a\}$ 与 $\{b\}$，用 $n$ 次多项式乘法可以在 $O(n^2\log n)$ 内完成，或使用多项式复合在 $O(n^2+n\sqrt{n}\log n)$ 的复杂度内完成。

可以通过子任务 1，期望得分 $20$ 分。

算法二

在满足 $A=B=C=D=1$ 时，我们可以做变换 $(x,y)\to (x+y,x-y)$ 使两维独立。

令 $x_T^{\prime }=x_T+y_T,y_T^{\prime }=x_T-y_T$，答案即为 $E(x_T^n{y}_T^m)=E\left({\left(\frac{x_T^{\prime }+y_T^{\prime }}{2}\right)}^n{\left(\frac{x_T^{\prime }-y_T^{\prime }}{2}\right)}^m\right)$。

由于两维独立，将上式展开，答案可写为 $\sum _{i=0}^{n+m}{h}_{i}E({x_T^{\prime }}^i)E({y_T^{\prime }}^{n+m-i})$ 的形式。由于两维对称，我们以求解 $c_l=E({x_T^{\prime }}^l)$ 为例。

因为有

$$\sum _{l=0}^{n+m}{c}_l{x}^l=e^{(x_0+y_0)x}{\left(\frac{e^x+e^{-x}}{2}\right)}^T$$

所以我们可以使用多项式快速幂即可在 $O(n\log n)$ 的复杂度内算出所有 $c_l$ ，从而求出答案。

可以通过子任务 2，结合算法一可以得到 $40$ 分。

算法三

此时考虑 $x_0=y_0=0,A\ne B,C\ne D$ 时的情况。

我们需要对于 $0\le i\le n$ , 算出 $[x^n](e^{Ax}+e^{-Bx}-2{)}^i$（另一侧同理）。

使用扩展拉格朗日反演，令 $F(x)=e^{Ax}+e^{-Bx}-2$，$H(x)=x^i$。

则有 $[x^n]H(F(x))=\frac{1}{n}[x^{n-1}]H^{\prime }(x){\left(\frac{x}{G(x)}\right)}^n=\frac{i}{n}[x^{n-i}]{\left(\frac{x}{G(x)}\right)}^n$，其中 $G(x)$ 是 $F(x)$ 的复合逆。

注意到 $A\ne B$，所以 $G(x)$ 存在，由于 $F(x)$ 有简单的封闭形式，求 $G(x)$ 简单牛顿迭代即可。

时间复杂度 $O(n\log n)$ ，可以通过子任务 3 和子任务 4，结合前两个算法可以得到 $60$ 分。

算法四

考虑只有 $A\ne B,C\ne D$ 条件时怎么做。同样需要对于 $0\le i\le n$，算出 $[x^n]e^{sx}(e^{Ax}+e^{-Bx}-2{)}^i$。同样定义出 $F(x),G(x)$ 。

此时有 $[x^n]e^{sx}(e^{Ax}+e^{-Bx}-2{)}^i=[x^n]e^{sG(F(x))}F(x{)}^i$。令 $y=F(x)$ , $[x^n]e^{sG(F(x))}F(x{)}^i=e^{sG(y)}{y}^i$。

定义 $D(x)={\left(\frac{x}{G(x)}\right)}^n$，$H(x)=e^{sG(x)}{x}^i=L(x)x^i$，其中 $L(x)=e^{sG(x)}$。

使用扩展拉格朗日反演，有 $[x^n]H(F(x))=\frac{i}{n}[x^{n-i}]D(x)L(x)+\frac{1}{n}[x^{n-i-1}]L^{\prime }(x)D(x)$，直接计算即可。

时间复杂度 $O(n\log n)$ ，可以通过子任务 3、4、5，结合前两个算法可以得到 $70$ 分。

算法五

我们已经解决了 $A\ne B$ 的情况，现在只需考虑 $A=B$ 时如何做。

注意到 $[x^1]e^{Ax}+e^{-Bx}-2=0$，所以 $e^{Ax}+e^{-Bx}-2$ 不存在复合逆，我们需要令 $F(x)=\sqrt{e^{Ax}+e^{-Bx}-2}$ ，此时 $[x^1]F(x)=A$ ，在 $A=0$ 时需要特殊处理。

现在就有 $(e^{Ax}+e^{-Bx}-2{)}^i=F(x{)}^{2i}$ 了，后续处理与算法四相同。

时间复杂度 $O(n\log n)$ ，与算法四结合可以通过所有子任务，期望得分 $100$ 分。