民意调查

idea from skip2004, solution, data from he_____he.

算法一

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

算法二

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

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

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

算法三

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

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

算法四

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

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

时间复杂度仍为 $O(n^3V)$，空间复杂度 $O(n^2V)$，可以通过所有子任务，期望得分 $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}$ 状态时回退一个位的状态。不难发现，我们记一个点的势能为它被位前进+位后退的总次数，即为 $\Phi(u)$，则总操作次数为 $\mathcal O(\sum\limits_{i=1}^{n}\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$ 次位后退。

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

国王出游

from ezoilearner.

算法一

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

$$[x^ny^m](e^{Ax}+e^{-Bx}+e^{Cy}+e^{-Dy})^T=T!\sum\limits_{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$，所以有 $\forall i>n,a_i=0$，同理 $\forall j>m,b_j=0$。

令 $M(x)=\left(\sum\limits_{i=0}^n a_ix^i\right)\left(\sum\limits_{j=0}^m b_jx^j\right)$，所求即为 $n!m!\sum\limits_{i=0}^{n+m} 4^{i-T}{T\choose 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)\rightarrow (x+y,x-y)$ 使两维独立。

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

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

因为有

$$\sum\limits_{l=0}^{n+m} c_lx^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\neq B,C\neq D$ 时的情况。

我们需要对于 $0\leq i\leq 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'(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\neq B$，所以 $G(x)$ 存在，由于 $F(x)$ 有简单的封闭形式，求 $G(x)$ 简单牛顿迭代即可。

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

算法四

考虑只有 $A\neq B,C\neq D$ 条件时怎么做。同样需要对于 $0\leq i\leq 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'(x)D(x)$，直接计算即可。

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

算法五

我们已经解决了 $A\neq 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$ 分。