rushcheyo的博客从 UOJ 管理员卸任了。
学 OI 的时经常一天一大半的时间都在看着前人留下的痕迹，神往着七年以前 OI 的黄金时代，想象着写下那些文字的人在创造更大的传奇，想象着我是不是也会拥有这样的生活。
然而想到如今的世界，疫情、气候变化肆虐，年轻人的机遇越来越少，欢乐纯粹的 OI 圈也在滑向阴郁和焦虑。相比于只生活在我印象中无忧无虑、单纯友善的研究者样板，真实的人和人际关系是这么脆弱又这么复杂。常常被加深的这些反差对我有很深的打击，以至于常常泪下，发出「再也回不到过去了啊」的感慨。
这个任期里我一直在想 UOJ 的意义是什么（这就是你摸鱼的原因吗）。UOJ 的题难度很大，集训队以下的选手鲜少在上面训练，似乎没什么教育意义。然而这些屁话在选手与出题人如火的热情面前又是这么的无力。我后来就想至少一定不能辜负这些人，不能让 UOJ 凉掉，也不想再看到别人失望或信仰崩塌的样子。我在 UOJ 上投射了我的一种信念：不管再怎么魔幻的事情再怎么动摇人心，那些我们想象中最美好的东西、自己和别人都真实存在，而且还将会一直保留下去。
Idea, data, std, solution from command_block
直接按照定义递归计算，复杂度递归式为 $T(n)=O(n)+\sum_{d \ge 2}d\times T(n/d)$。
解得 $T(n)=O \left (n^{2.73} \right)$ ，过 $800$ 不是问题。
期望得分 $30$。
感谢 ezoilearner 的帮助。
先特判 $n=1$ 的情况。
考虑贡献，设 $S(n,m)$ 为长为 $n$ 的序列的第 $m$ 个位置的贡献系数。
我们的目标是求出 $S(n,0)\sim S(n,n-1)$。然后答案可以这样计算 ：
$$ {\mathrm{ans}}=\sum\limits_{m=0}^{n-1}S(n,m)A_m $$
考虑如何计算单个 $S(n,m)$。
将一种筛选记为 $(c,k)$ ，表示保留了所有模 $k$ 余 $c$ 的位置。
筛选是可以叠加的。 两次筛选 $(c_1,k_1),(c_2,k_2)$ 叠加，则等效于筛选 $(c_1+k_1c_2,k_1k_2)$。
$S(n,m)$ 相当于计数有多少种筛选序列叠加后最终得到单一的 $\{A_m\}$。
注意到我们总是可以根据 $m,k$ 唯一确定出 $(c,k)$ 中的 $c=m\bmod k$ ，所以我们可以只关心筛选中的模数 $k$ ，而不关心余数 $c$。
考虑一个筛选序列符合要求的充要条件。记筛选序列为 $\{k_1,k_2,k_3,...,k_p\}$ 。
在筛选 $k_{1\sim p-1}$ 生效后（只有最后一个 $k_p$ 未生效），剩余的数至少有两个（否则就停止了）。
记 $s=\prod_{i=1}^{p-1}k_i$ （前 $p-1$ 个筛选叠加），则充要条件为 $0\leq m-s$ （在前面有一个数）或 $m+s \lt n$ （在后面有一个数）。
等价的条件为 $s\leq \max(m,n-m-1)$。
在最后一步，筛选中的数变为单一的 $m$。（并停止）
最后一步的筛选 $k_p$ 要满足 $sk_p>\max(m,n-m+1)$ (将前面的条件取反)
除此之外，还要满足 $k_p$ 不超过 $s$ 生效后的序列长度。
这个长度为 $\lfloor m/s\rfloor + \lfloor (n-1-m)\rfloor/s+1$ （分别计算 $m$ 前后的位置个数）。
总的条件为 $k_p\in \big(\lfloor \max(m,n-m-1)/s\rfloor ,\lfloor m/s\rfloor + \lfloor (n-1-m)/s\rfloor+1\big]$
综上，我们只需要得知 $\prod_{i=1}^{p-1}k_i$ 与 $k_p$ 即可判定一个筛选序列是否符合要求。
定义 $H(n)$ 为各元素 $>1$ 的有序整数序列乘积为 $n$ 的方案数。
$H(n)$ 可由以下简单 DP 求解 ： $$ H(n)=\sum\limits_{d|n,d\neq n}H(d) $$
复杂度为 $O\big(\sum_{i=1}^nd(i)\big)=O(n\log n)$。
考虑枚举 $s$ ，则 $k_p$ 的方案数可以确定。$k_{1\sim p-1}$ 得到 $s$ 的方案数即为 $H(s)$ 。
$$ \begin{aligned} S(n,m)&=\sum\limits_{s=1}^{\max(m,n-m-1)}H(s)*\Big(\lfloor m/s\rfloor + \lfloor (n-m-1)/s\rfloor+1-\lfloor \max(m,n-m-1)/s\rfloor\Big)\\ &=\sum\limits_{s=1}^{\max(m,n-m-1)}H(s)*\Big(\lfloor min(m,n-m-1)/s\rfloor+1\Big) \end{aligned} $$
上式容易整除分块计算。逐个计算 $S$ ，复杂度 $O(n\sqrt{n})$ 。期望得分 $65$。
对每个 $m$ 均进行整除分块是不优的，考虑利用之前的信息来优化复杂度。
首先做一步转化 ：
$$ D(n)=\sum\limits_{s}H(s)*\lfloor n/s\rfloor $$
$$ S(n,m)=D\big(\min(m,n-m-1)\big)+\sum\limits_{s=1}^{\max(m,n-m-1)}H(s) $$
然后考虑如何求 $D(1\sim n)$。
定义 $\Delta D(n)=D(n)-D(n-1)$
$$ \Delta D(n)=\sum\limits_{s}H(s)\Big(\lfloor n/s\rfloor-\lfloor (n-1)/s\rfloor\Big) $$
注意到 $\lfloor n/s\rfloor\neq\lfloor (n-1)/s\rfloor$ 当且仅当 $s|n$ ，且此时 $\lfloor (n-1)/s\rfloor=\lfloor n/s\rfloor-1$。
于是有 ：
$$ \Delta D(n)=\sum\limits_{s|n}H(s) $$
和 $H(s)$ 原本的递推式结合，即可得到 $\Delta D(n)=2H(n)$。
但有一个例外，当 $n=1$ 时是 $\Delta D(1)=H(1)=1$。
于是瓶颈就仅仅在于求出 $H(1\sim n)$ 。复杂度 $O(n\log n)$。期望得分 $100$。
本题 std 代码量不足 500 B ，是一道合格的小清新数论题！（大雾）
这是题目原本的标准做法，由于觉得不太适合 A 题就削弱了。
考虑如何在线性时间内求出 $H(1\sim n)$。
根据递推式观察 $H(n)$ 的组合意义。
根据唯一分解，以各个指数为基，将数 $n=p_1^{c_1}p_2^{c_2}...p_m^{c_m}$ 看做高维空间的一个点 $(c_1,c_2,...c_m)$ （坐标中的大量 $0$ 未写出）
这个点每一步可以走向维度坐标只减不增的区域，求走到原点的方案数。
不难发现，若两个坐标将维度任意排序后相同，则 $H$ 函数的值也是相同的（不同维度的地位没有区别）。为了方便，我们约定坐标按照基底素数从小到大排序，并去掉 $0$。
在这种定义下，在 $2\times 10^7$ 中，仅仅只有 $4223$ 种不同的坐标。对每种坐标进行 DP 求出 $H$ 函数值的复杂度可以忽略。
然后我们将所有坐标（以及对应函数值）插入字典树，便于检索。
接下来的任务就是对每个 $m\in[1,n]$ 求出其质因数分解坐标，并取出对应函数值。
筛出所有质数后，可以利用「树形筛」来得到每个数的坐标。（这个命名是临时的）
该筛法的思想是，从小到大考虑各个质因子，以及其指数（即逐位确定坐标）。配合字典树，可以快速找到对应的函数值。
具体流程可见 评测记录 中 dfs4 部分。
可以发现，该筛法恰会访问 $1\sim n$ 中的每个数各一次，且每个搜索树节点都不会在不合法的分支尝试中浪费超过 $O(1)$ 的时间。因此，该筛法的复杂度即为 $O(n)$。
Idea from rushcheyo, data, std, solution from mayaohua
$n=1$ 的做法样例解释告诉你了。
对于 $n=2$ 的数据，设矩阵 $$A=\begin{pmatrix}a & b\\ c& d\end{pmatrix} $$，那么询问 $B=\mathbf0_{2\times 2}$ 可以得到 $\det(A)=ad-bc$，再询问 $B=e_{1,1}$ 可以得到 $(a+1)d-bc$，做差即可得到 $d$，同理询问其它 $e_{i,j}$ 可以问出所有的 $a,b,c,d$。
这样至多花费 $5$ 次询问，可以通过子任务 $1$，期望得分 $14$ 分。
在算法一的基础上，我们考虑减少一次询问，注意到我们如果知道了 $a,b,c$ 和 $\det(A)=ad-bc$，那么若 $a\neq 0$ 我们可以唯一确定 $d$。
这样在大部分情况下我们可以用 $4$ 次询问通过 $n=2$ 的数据，但是可能会遇到除 $0$ 的情况，一个简单做法是我们初始时随机一个矩阵 $C$，每次询问的时候都把 $B$ 加上 $C$，这样解出来的是 $A+C$，减回去即可。这样既可以大概率避免出现除 $0$ 的窘境了，但是数据造水了，并没有造 $0$ 的数据。
这样至多花费 $4$ 次询问，可以通过子任务 $1 \sim 2$，期望得分 $20$ 分。
对于 $n\leq 20,T=8000$ 的数据，我们希望得到一个询问次数 $n^3$ 的算法。
考虑逐位确定。不妨设我们要确定 $A_{1,1}$，我们考虑取矩阵函数 $B_x=x(I_n-e_{1,1})$，这样 $\det(A+B_x)$ 就是一个关于 $x$ 的不超过 $n-1$ 次多项式，且 $n-1$ 次项系数正好为 $A_{1,1}$，那我们取 $n$ 个 $x$ 插值即可。同理可以取置换，用类似方法来求出所有的 $A_{i,j}$。
这样询问次数为 $n^3$，可以通过子任务 $3$，期望得分 $24$ 分，结合算法二期望得分 $44$ 分。
考虑得到更优秀的算法。
我们同样先问 $B=0_{n\times n}$ 来得到 $\det(A)$，随后问所有的 $B=e_{i,j}$ 来得到 $\det(A+e_{i,j})=\det(A)+M_{i,j}$，其中 $M_{i,j}$ 是 $(i,j)$ 位置代数余子式，即 $(-1)^{i+j}$ 乘上 $A$ 去掉 $i$ 行和 $j$ 列剩余的子矩阵 $A_{i,j}$的行列式，于是我们可以得到所有的 $M_{i,j}$。
线性代数中有一个著名的定理，对于可逆矩阵 $A$，$A^*=\frac{1}{\det(A)}A^{-1}$。这里 $A^*$ 是 $A$ 的伴随矩阵，有 $(A^*)_{i,j}=M_{j,i}$。那么假定 $A$ 可逆，我们知道了 $\det(A)$ 和所有的 $M_{i,j}$，就能推出 $A^{-1}$ 了，再做个矩阵求逆就可以得到 $A$ 了。
但这里 $A$ 不一定可逆，我们可以用类似算法二的策略，预先随机一个矩阵 $C$ 加上去，最后再减回来。这样的效果相当于随机了一个 $\mathbb F_{p}$ 下的 $n$ 阶矩阵，它行列式不为 $0$ 的概率（正确率）是 $$ (1-p^{-(n-1)})(1-p^{-(n-2)}) \ldots (1-p^{-1}) \ge 1-p^{-1}-p^{-2}-\cdots=1-\frac{1}{p-1} $$ 这样询问次数为 $n^2+1$，可以通过子任务 $1,3,4$，期望得分 $65$ 分，结合算法二期望得分 $71$ 分。
对于最后一个子任务，限制询问次数为 $n^2$，还需要进一步优化。
考虑用算法二的思想来优化算法四。我们尝试不问 $e_{1,1}$，假定 $A$ 可逆，这样可以得到所有的 $M_{i,j}$（$(i,j)\neq(1,1)$）与 $\det(A)$。由于 $\det(A^{*})=\det(A)^{n-1}$，若 $A^*$ 的 $M_{1,1}$ 不是 $0$ 我们可以同样解出 $M_{1,1}$（$A$ 的），便能节约一次。
由于 $A^*=\frac{1}{\det(A)}A^{-1}$，上面条件相当于 $A^{-1}$ 的 $M_{1,1}$ 不是 $0$，由 union bound（也就是 $P(A \cup B) \le P(A) + P(B)）$ 知道错误率不超过 $\frac{2}{p-1}$。
这样询问次数为 $n^2$，可以通过子任务 $1\sim 5$，期望得分 $100$ 分。
Idea, data, std, solution from zx2003 and Isonan
给出一个 trie 树以及 $T=S_{a_1}+S_{a_2}+\dots +S_{a_k}$，对于 trie 树上的每个节点，求出该点表示的串 $u_i$ 在 $T$ 中的出现次数。
记 $match(s)$ 表示 $s$ 在 trie 树上能够匹配的最长后缀对应的节点。
记 $exi(s)$ 表示 trie 树上存在一个节点 $x$ 使得 $u_x=s$。
记 $dep_x$ 表示点 $x$ 在 trie 树上的深度。
记 $anc_{a,b}$ 满足 $anc_{a,b}$ 是 a 在 fail 树上的祖先，且 $dep_{anc_{a,b}}=b$。
对原 trie 树建立 AC 自动机，把串T在上面走一遍，最后做一遍 fail 树上前缀和即可。
注意由于字符集过大，而且 trie 树的所有叶子深度和没有保证，故需要使用可持久化数组优化建立 AC 自动机的过程。
复杂度 $O(l\log{w}+mS\log{w})$，可以通过 subtask 1，期望得分 7。
考虑优化串 T 在 AC 自动机上行走的过程。
假设我们已经求出了 $end_{i,j}$ 表示 $match(u_j+S_i[1\dots len_{i,j}])$，其中 $len_{i,j}=\max\{x|exi(u_j+S_i[1\dots x])\}$。
之后我们尝试求出 $dir_{i,j}=match(u_j+S_i)$。
由于 $end_{i,j}$ 已知，所以我们可以知道从点 $j$ 出发沿 $S_i$ 在 AC 自动机上行走时，第一次跳 fail 边后到达的节点 $k=fail(end_{i,j})$。
如果 $dep_k \le dep_{end_{i,j}}-dep_{j}$，则意味着 $u_{dir_{i,j}}$ 完全是 $S_i$ 的后缀，$dir_{i,j}=dir_{1,j}$，注意本题中1号点为根节点。
否则我们可以从 $k'=anc_{k,dep_{k}-(dep_{end_{i,j}}-dep_j)}$ 处继承答案。
注意由 AC 自动机的性质，$k'$ 一定是 $j$ 在 fail 树上的祖先。于是整个算法流程可以在 fail 树上递推计算，DFS 的时候可以开个桶存储在当前 DFS 栈中深度为定值的节点，以便快速查询 $anc_{a,b}$。
注意特判不需要跳 fail 边的情况，此时有 $exi(u_j+S_i)$，故 $dir_{i,j}=end_{i,j}$。
那么对于每个 $i$，我们可以得到 $match(S_{a_1}+\dots +S_{a_i})$。
这样问题进一步被转化为：
对于一个串 $S_i$，已知每次开始加入该串时在哪个节点，求每个节点在所有加入该串的过程中被经过多少次。
那么观察从 $x$ 开始的一次加入，我们首先会走到 $end_{i,x}$，然后跳到 $fail_{end_{i,x}}$。
这里我们仍然沿用求 $dir_{i,j}$ 时的分类讨论模式。
如果 $dep_y \le |S_i|$ ，则 $\exists k$ 使得 $u_y=match(S_i[1\dots k])$，我们只需对所有 $k' \ge k$ ，将 $match(S_i[1\dots k'])$ 加上相应的值即可，这可以通过一个后缀和来解决。
否则，接下来我们会走到 $end_y$，这里 $y=anc_{fail_{end_{i,x}},dep_{fail_{end_{i,x}}}-(dep_{x}-dep_{i,x})}$。
容易发现 $y$ 是 $x$ 的后缀，亦即 $x$ 在 fail 树上的祖先。于是我们可以按长度从大到小枚举 trie 树上的节点，并在 trie 树上差分得到答案。
于是唯一问题变为 $end_{i,j}$ 的求法，如果在 trie 树上暴力匹配，并且计算 $match(S_i[1\dots k])$ 时暴力跳 fail 边且使用哈希表存边来规避可持久化数组，则总复杂度为 $O(l\log{w}+nl^2+S+m)$，可以通过 subtask 1, 3，期望得分 24。
对于 subtask 2，我们可以使用 exKMP 来优化求 $end_{i,j}$ 的过程。
复杂度为 $O(nl+S+m)$，可以通过 subtask 1, 2, 3，期望得分 38。
继续优化求解 $end_{i,*}$ 的过程。
每次计算 $end_{i,*}$ 时，首先通过每条重链上 exKMP 求出每个点在该点所在重链上最多走到哪里。
这样问题形式就转为有若干形如 $(a,b)$ 的询问 ，表示在点 $a$ 的轻子树中查询后缀 $b$ 的匹配情况。
对于所有的 $i$ ，总共有 $n \cdot l$ 个这样的询问。我们将所有询问离线处理，对于每个a，按照后缀 $b$ 从小到大处理询问。然后类似于求虚树的过程，对于当前询问，求出 trie 上的匹配点 $x$；转到下一个询问的时候，$x$ 不断跳父亲直到 $u_x$ 成为后缀 $b$ 的前缀，这里可以使用哈希来进行判定；然后再沿树边往下走。由于每个点上被访问的出边字符是单调递增的，所以可以用一个指针代替可持久化数组。
关于对所有串的所有后缀进行排序的过程，由于字符集的关系，如果使用其它后缀数据结构会极大地降低运行效率，所以 std 使用了 SA-IS。
最后总复杂度 $O(l\log{l}+l\log{w}+nl+S+m)$，可以通过 subtask 1, 2, 3, 4, 5，期望得分 100。
from mayaohua, Itst
仍然考虑优化求解 $end_{i,*}$，但是这次我们转换思路，转为计算 trie 上每个节点对于祖先的 $end_{i,*}$ 的贡献。
具体的，对于每个 $i$，我们在 trie 上 DFS 的同时，对于当前点 $x$ 维护出 $u_x$ 的最长后缀 $p$，满足其也是 $s_i$ 的前缀。
则从 $x$ 往下走的时候，对于 $p$ 的一个长为 $j$ 的 border，如果 $x$ 往下走的对应边没有字符 $S_{i}[j]$ ，则 $x$ 在 trie 上的 $j$ 级祖先 $y$，其 $end_{i,y}$ 就等于 $x$；并且所有的 $end_{i,*}$ 都一定能被这样正确计算。
于是唯一的问题就是找到这些 border。
我们先对 $s_i$ 进行预处理，对于每个前缀 $i$，求出 $lst_i$ 表示 $i$ 的最长 border 使得其后继字符和 $i$ 相等；再对于每个字符 $c$，使用可持久化数组存储后继字符为 $c$ 的最长 border。由于前缀 $i$ 的 border 构成 $O(\log{i})$ 段等差数列，于是数组中非 0 位置的数量也只有 $O(\log{i})$ 个，暴力存储所有非 0 位置，即可以 $O(S\log{S})$ 的复杂度完成预处理。如果你使用可持久化平衡树来存储非 0 位置，则可以做到 $O(S\log{\log{S}})$ 的复杂度。
之后在 trie 上 DFS 的时候，我们将点 $x$ 匹配到的串 $p$ ，遍历一遍存储了其所有 border 后继字符的数组。对于每个字符 $c$，如果有 $x$ 的出边等于 $c$ ，则这部分复杂度不超过 trie 的边数亦即 $O(l)$；否则一定至少有一个点 $y$ 的 $end_{i,y}$ 被算了出来，这部分复杂度仍为 $O(l)$。
最后总复杂度 $O(l\log{w}+nl+S\log \log{S}+m)$，期望得分 100。
如果可持久化数组实现不当，可能无法通过 subtask 5，只能得到 67 分。
Idea, data, std, solution from mayaohua
首先向大家表示抱歉，由于出题人没有出提交答案题的经验，每个测试点没有设计多档部分分，区分度不太足。
原本的想法是出一个对着 AI 攻击的游戏题，但由于出题人能力所限，最后的成品和预期差距比较大，测试点的设计可能不够有趣，但还是希望大家玩得开心。
所有的 AI 都会定向攻击你，且你很难通过给它们加能量来改变它们的目标（即使改变了也不优秀，因为一旦攻击就会吸引仇恨）。因此你的选择只能是逐个击杀并尽量最小化击杀过程中承受的伤害。
注意到所有 AI 都是 $100$ 级，只有体力的区别。显然最优的策略是按体力从小到大击杀，直接排序后模拟一下过程即可。
初始时所有 AI 都不会攻击你，且 $2\sim 99$ 号 AI 都永远不会攻击你，但只要你攻击 $100$ 号 AI，立刻会遭到反击从而失败。于是你的策略只能是一击秒杀掉 $100$ 号 AI。
但你的等级是不够高的，于是你可以依靠 $2\sim 99$ 号 AI 给你反复加能量来提升一次攻击的伤害。但初始时你的威胁度比较高，它们都不会给你加能量，于是你需要通过先给它们加能量来降低威胁度。可以用相邻交换证明最优策略是按 $\frac{a_i}{c_{i,1}}$ 从大到小排序后依次把 $c_{i,1}$ 降到 $0$，模拟完这个过程后只需要挂机直到可以一击击杀 $100$ 号 AI，最后把其它 AI 依次击杀即可（此时你的等级已经足够秒杀所有 AI 了）。
这个测试点把上述的算法卡满了，合法解恰好要 $10000$ 轮。
$2\sim 99$ 号 AI 同样永远不会攻击你，但 $100$ 号 AI 会一直攻击你且不能改变目标。因此你的目标就是在尽量少的轮数内击杀 $100$ 号 AI，然后再依次击杀掉剩下的 AI。
你的最优策略显然是在 $2\sim 99$ 号 AI 中选择若干个，并按某种顺序依次击杀。如果我们已经找到了一个排列，就可以通过 DP 或者直接枚举前缀等方法来找到优秀的解。标程做法是先按 $\frac{a_i}{b_i}$ 从大到小排序得到初始排列，再通过爬山/退火随机交换调整来找到较好的排列。
这是一个精心构造的测试点。
初始时所有 AI 都会攻击你，但对每个 AI 你都可以通过一次给它加能量的操作来转移它的攻击目标。更加仔细的观察会发现所有 AI 的第二目标正好是两两配对的，且对每个 AI 的攻击会拉极大的仇恨，因此对于一对 AI，你只需要给编号小的那个加能量，就可以让它们停止攻击你并互相攻击了。显然你应该按每对 AI 的 $a$ 之和从大到小依次执行这个过程，在 $49$ 轮后就没有 AI 攻击你了。
接下来每对 AI 会反复互相攻击，并在 $1000\sim 9000$ 轮中的某个轮数后其中一个 AI 死亡，模拟这个过程可以发现在一对中的一个 AI 死亡时，另一个 AI 的体力也不会非常大（大概在 $10^6$ 级别），如果你在之前已经对这个存活下来的 AI 进行了适当的攻击（可以通过给另一个 AI 加能量来避免吸引仇恨），使得它剩余的体力在斩杀线内，就可以在下一轮直接击杀掉它使得你不会被它攻击。于是你可以大胆猜测一定有一个解能使你在这个过程中从不会被攻击，这一定是最优解！事实上你只需要按这个死亡轮数排序，然后直接依次执行进行攻击来调整，由于你后面的等级会快速提升，你每次调整所需的轮数会越来越少，实践证明确实是可行的。
所有 AI 会互相攻击直到仅存活下一个，且你的威胁度十分低，以至于不论如何攻击，都仅会在剩余一个 AI 后被攻击。那么要想不受伤害，你必须在剩余一个 AI 的下一轮就把它击杀。
一个想法是类似测试点 4 那样，在限定轮数内对最后存活下来的 AI 进行适当攻击，保证你最后能直接斩杀掉。但是由于你的初始等级太低，直接做是做不到的。于是你可以考虑选择一个中间的 AI，先通过同样的调整击杀掉它来增加自己的等级，再对最后存活下来的 AI 进行攻击。这个测试点设计的十分松，通过简单的枚举即可找到这个中间的 AI。
Idea, data, std, solution from EntropyIncreaser
题意：给定一个 $n-1$ 次多项式在 $1,q,\dots,q^{n-1}$ 处的点值，要求还原出 $m$ 次项系数。点值只有 $k$ 个位置不为 $0$。
使用 $\Theta(n^2)$ 的拉格朗日插值算法。期望得分 $5$。
子任务 $7$ 满足 $q^n=1$。我们熟悉这一情况就是 DFT。此时我们知道
$$ [x^m]f(x) = \frac1{n}\sum_{j=0}^{n-1} q^{-mj} f(q^j) $$
可以在 $\Theta(k\log n)$ 时间内计算。期望得分 $10$。
我们考虑优化拉格朗日插值算法在这一特定问题上的做法，先按照定义写出插得的多项式的表达式：
$$ f(x) = \sum_{i=0}^{n-1} f(q^i) \frac{\prod_{j=0}^{n-1}(x-q^j)}{(x-q^i)\prod_{0\le j\le n-1,j\neq i} (q^i-q^j)} $$
我们先翻转系数，写作
$$ f(x) = \prod_{j=0}^{n-1}(1-q^jx) \cdot \sum_{i=0}^{n-1} \frac{f(q^i)}{\prod_{0\le j\le n-1,j\neq i} (q^i-q^j)} \cdot \frac{1}{(1-q^ix)} $$
其中 $\prod_{0\le j\le n-1,j\neq i} (q^i-q^j)$ 展开后就可以 $\Theta(n)$ 计算所有，我们可以认为核心问题就是计算
$$ \begin{align*} \sum_{i=0}^{n-1} \frac {f_i}{1-q^i x} &= \sum_{i=0}^{n-1} \sum_j f_i q^{ij} x^j\\ &= \sum_{i=0}^{n-1} \sum_j \left(f_i q^{-\binom i 2}\right) \left( x^j q^{-\binom j 2} \right) \cdot q^{\binom{i+j}2} \end{align*} $$
其实也就是 Chirp Z-变换的转置。可以在 $\Theta(n\log n)$ 时间内解决，预计得分 $25$。
为了解决更大的 $n$，我们肯定要考虑只算某一项系数有什么特点了。
对于每个 $0\le i\le n-1$，我们需要求出 $[x^k]\prod_{j\neq i}(1-q^j x)$。设 $P=\prod_{i=0}^{n-1}(1-q^ix), S=\sum_{i=0}^{\infty}\frac {y^i}{1-q^ix}$，我们设 $F(x,y)=P\cdot S$，那么带入 $q$ 可得到方程。
$$ \begin{align*} F(qx,y) &= \left(\prod_{i=1}^{n}(1-q^ix)\right) \cdot \left(\sum_{i=0}^{\infty} \frac {y^i}{1-q^{i+1}x}\right)\\ &= \left(\frac{1-q^nx}{1-x}P\right) \cdot y^{-1}(S-(1-x)^{-1})\\ &= y^{-1}\frac{1-q^nx}{1-x} (F(x,y) - (1-x)^{-1}P) \tag{1}\\ F(x,qy) &= P \cdot \left(\sum_{i=0}^{\infty} \frac{y^iq^i}{1-q^ix}\right)\\ F(x,y)-xF(x,qy) &= P\cdot \frac 1{1-y}\\ xF(x,qy) &= F(x,y) - P \cdot \frac 1{1-y} \\ xF(x,y) &= F(x,q^{-1}y) - P \cdot \frac 1{1-q^{-1}y} \tag{2} \end{align*} $$
我们的目的是对所有 $i$ 提取 $[x^my^i]$，因此我们得到一个仅沿着 $y$ 的递推式。接下来，我们将式 1 带入式 2。
$$ \begin{align*} y(1-x)F(qx,y) &= (1-q^nx)(F(x,y)-(1-x)^{-1}P)\\ yF(qx,y)-q^{-1}y{\color{red} {(qx)F(qx,y)}} &= \left(F(x,y)-\frac{1-q^nx}{1-x}P-q^n{\color{red}{xF(x,y)}}\right)\\ yF(qx,y)-q^{-1}y{\color{red} {\left(F(qx,q^{-1}y)-P(qx)\frac 1{1-q^{-1}y}\right)}} &= F(x,y)-\frac{1-q^nx}{1-x}P\\ &-q^n \color{red}{\left(F(x,q^{-1}y) - P \cdot \frac 1{1-q^{-1}y}\right)} \end{align*} $$
设 $f_i=[x^my^i]F(x,y)$，那么两边提取系数 $[x^my^i]$，设 $i\ge 1$，便有
$$ \begin{align*} q^m f_{i-1} - q^{m-i}(f_{i-1} - [x^m]P) &= f_i - q^{n-i} (f_i - [x^m]P) \\ (1-q^{n-i}) f_i &= (q^m-q^{m-i})f_{i-1}+(q^{m-i}-q^{n-i})[x^m]P \end{align*} $$
便可逐此递推，而且 $1-q^{n-i}\neq0$ 已经蕴含于 $q^i$ 互不相同这一题设中。
我们还需要求出 $[x^m]P$，这可以如法炮制：
$$ \begin{align*} P(qx) &= \frac{1-q^nx}{1-x}P(x)\\ (1-x)P(qx) &= (1-q^nx)P(x)\\ q^i p_i - q^{i-1}p_{i-1} &= p_i - q^np_{i-1}\\ p_i &= \frac{q^{i-1}-q^n}{q^i-1}p_{i-1} \end{align*} $$
时间复杂度 $\Theta(n)$，预计得分 $50$。
为了最后的子任务，我们需要在 $o(n)$ 时间内计算某一项 $i$ 的 $[x^my^i]F(x,y)$，$\prod_{0\le j\le n-1,j\neq i}(q^i-q^j)$ 以及计算 $[x^m]P$。
这种递推式并非常系数，它和我们曾经遇到的整式递推更为相似，递推系数是一个关于 $(q,q^i)$ 的有理分式。
我们首先来看 $\prod_{0\le j\le n-1,j\neq i}(q^i-q^j)$ 的多次询问如何解决。其可以拆解为计算
$$ \begin{align*} & \quad q^{(n-1)i} \prod_{0\le j\le n-1,j\neq i}(1-q^{j-i})\\ &= (-1)^i q^{(n-1)i} \left( \prod_{j=1}^{n-i-1} (1-q^j) \right) \left( \prod_{j=1}^{i} (1-q^{-j}) \right)\\ &= (-1)^i q^{(n-1)i} \left( \prod_{j=1}^{n-i-1} (1-q^j) \right) q^{-\frac{i(i+1)}2} \left( \prod_{j=1}^{i} (1-q^j) \right) \end{align*} $$
因此问题归结于计算 $1-q^j$ 的连乘积。我们设块大小 $b\le \sqrt n$，考虑计算
$$ B(x)=\prod_{j=1}^b (1-q^j x) $$ 在 $1, q^{b}, q^{2b},\dots$ 处的点值。我们可以通过前面所说的递推方法得到 $B(x)$ 的系数，然后通过 Chirp Z-变换计算出这些点值。复杂度为 $O(\frac n b\log n)$。进行一次询问的时候，我们只需要再加上剩下的零散部分，复杂度 $\Theta(b)$。当询问次数 $k$ 较小的时候，只能取 $b=\sqrt n$，复杂度为 $\Theta(\sqrt n\log n + k\sqrt n)$。较大时解得 $b=\sqrt{\frac{n\log n}{k}}$，复杂度 $\Theta(\sqrt{kn\log n})$。
其他几个递推式可以使用类似手段处理，只需将式子通分。不过在数据范围内一个易于实现的方法是令 $b = \min(n, 500)$，这样的话 $\Theta(b^2)$ 算出各部分多项式系数，然后 $\Theta((n/b) \log n + kb)$ 也可以接受。
预计得分 $100$。
当然，这并非最优理论复杂度，我们可以先得到 $\sqrt n$ 个点值之后，每个询问距离最近的点只有 $\sqrt n$ 距离，可以将剩下的跳跃过程二进制分解，每轮进行多点求值。这样就能将复杂度降到 $\tilde O(\sqrt n + k)$，但是由于所含的 $\log$ 因子可能较多，在目前的数据范围下可能不会有很好的表现。
我们算法五的步骤，在 2020 年被学术界捷足先登了：
Idea, data, std, solution from Itst
jiry_2 和 Picks 哥哥不会骂我吧 QAQ
设 $V = 2^{32}$ 表示值域。
我会暴力！模拟题目过程，复杂度 $O(nq)$，可以通过子任务 1 获得 2 分。
我会找子任务！发现子任务 5 没有 + 运算，那么每一个二进制位是独立的。对于每一个二进制位每个操作就只有变成 1、变成 0、取反、不变这四种可能。
可以使用一些数据结构完成，为了给后面的算法进行铺垫，这里给出 $O(n \log V)$ 预处理 $O(1)$ 查询的方法：
维护每个操作前所有异或操作的 $x$ 的异或和，并计算 $pre_{x,y}$ 表示第 $x$ 个操作之前（不包含 $x$）的所有操作中对第 $y$ 位有赋值影响（即变 1 或变 0）的操作中编号最大的一个操作，不存在记为 $0$。这显然可以 $O(n \log V)$ 预处理。
对区间 $[l,r]$ 查询第 $k$ 位取值时，考察 $pre_{r+1,k}$ 与 $l$ 的大小关系。若 $l \leq pre_{r+1,k}$ 则其受到了赋值操作影响，最后一个赋值操作是 $pre_{r+1,k}$，故询问 $pre_{r+1,k}$ 到 $r$ 中所有异或操作的异或和结合 $pre_{r+1,k}$ 个操作的操作类型即可得到当前位答案；否则操作只有异或，直接计算 $l$ 到 $r$ 所有异或操作的异或和即可。
复杂度 $O(n \log V + q)$，可以通过子任务 5，结合算法一可获得 8 分。
我参加了联合省选 2020！（？）
对于子任务二，只有异或操作和加操作且允许离线。考虑将所有询问离线，沿着操作序列扫描线并维护一个 Trie，Trie 中包含了所有会进行这一次操作的询问。也就是说对于一个询问 $(v,l,r,L)$，在操作序列扫到第 $l$ 个元素时将 $v$ 插入，即将扫到第 $r+1$ 个元素时在 Trie 上找到之前插入的 $v$ 现在变成了什么值，取二进制第 $L$ 位即可。找到插入的位置变成了什么值，可以考虑在插入时记录 $v$ 所对应的叶子节点编号，需要查询时从该节点开始不断跳父亲求得答案。
那么这个 Trie 的每个节点不仅需要维护儿子，还需要维护父亲。同时需要支持全局异或和全局 +1。联合省选 2020 中就需要运用这样的 Trie 结构：按照位数从低到高插入每个数，异或操作体现为交换表示某些二进制位的节点的儿子，可以打标记实现；而 +1 操作只需要首先交换根节点的儿子表示最低位的变化，然后递归进入 $0$ 表示的儿子继续做以处理进位即可。这只会递归 $\log V$ 次。
最终时间复杂度 $O((n+q) \log V)$ 空间复杂度 $O(q \log V)$，可以通过子任务 2，结合算法一、二可获得 16 分。
我会树合并！
对于子任务 6、7 考虑沿用算法三的做法。这需要我们支持在 Trie 上进行与和或操作。这个的处理实际上是较为容易的。
仍然在每个节点上打标记，标记为有哪一些二进制位被赋为 0、有哪一些二进制位被赋为 1、有哪一些二进制位被翻转。下传标记时，若当前位被置 0 或者置 1，则其两个儿子会合并到一起。通过 Trie 的树合并即可实现这一点。需要注意的是树合并时需要下传标记，而下传标记也需要合并，故需要一些特殊的实现。
这样的树合并的复杂度分析与树合并一致，每一次合并需要 $O(1)$ 的复杂度减少 Trie 上的一个节点，故树合并复杂度为 $O(q \log V)$。
同时注意到节点可能会合并，故与算法三不同地，在 $r+1$ 位置查询答案时 $l$ 位置插入的节点可能由于合并到其他节点上被删除。此时可以在外部对这 $q$ 个节点维护一个并查集记录每个节点的合并状态以找到真正的节点。
总时间复杂度 $O((n+q) \log V)$ 空间复杂度 $O(q \log V)$，常数较大。可以通过子任务 2、6、7，结合算法一、二可获得 36 分。
from mayaohua
我会线段树！（总算是有一个和线段树有关系的 Sub 了）
考虑对原序列建立线段树，那么在每个节点需要知道一个任意值经过这个区间的操作后变为什么值。考虑沿用算法三提到的 Trie 结构。由于无法提前知道询问，需要对所有值都给出答案，但建立一个满 Trie 是不现实的。考虑进行一些优化。
注意到操作涉及的节点数量非常有限，考虑只把有意义的节点建立出来。这里我们认为无意义的节点指的是在 Trie 上没有做过任何操作（与兄弟交换或者被传标记）的节点。每次异或时在根节点上打上标记。+1 操作与原来一致，但可能在路径中新建额外的节点。但新建节点数量不会超过 $2 \log V$，故总时空复杂度是 $O(n \log n \log V)$ 的。
维护每个节点所表示的初始值域区间，每一次查询找到其所在的初始值域区间对应的节点，则所有 Trie 上的操作没有影响到无效节点对应的若干位。最后跳父亲还原答案，记得把这些节点上剩余的标记进行处理。
时间复杂度 $O((n+q) \log n \log V)$ 空间复杂度 $O(n \log n \log V)$，可通过 Subtask 2、3，结合算法一、二、四可获得 $50$ 分。
from mayaohua
我会分析操作性质！
注意到如果所有询问的 $l$ 都是 $1$，则可以利用算法 5 中的节点内 Trie 树结构，对整个序列建立一个可持久化的这样的结构，即可在 $O(n \log V)$ 的空间内进行前缀询问查询。
对于子任务 4 考虑分析没有与和或操作的性质。一个不难注意到的性质是：给定一个只有 +1 和异或的操作序列，设集合 $S = \{0,1,\cdots,V-1\}$，考虑映射 $f:S \rightarrow S$，其中 $f(x)$ 表示的是 $x$ 经过操作序列后变成的数，则 $f$ 是一个一一映射。
利用这个性质，设 $f_{l,r}(x)$ 表示做序列 $l$ 到 $r$ 的操作对应的映射，则求询问 $v,l,r,L$ 的结果可以通过 $f_{1,r}(f^{-1}_{1,l-1}(v))$ 来得到，也就拆成了两个前缀询问。
$f_{1,r}(x)$ 的询问使用之前的可持久化结构进行计算，而 $f^{-1}_{1,l-1}(x)$ 的询问实际上是更加简单的：在 $f_{1,l-1}(x)$ 对应的数据结构中沿着 $x$ 走，通过其最后到达的有效节点的信息和经过的标记即可得到 $f^{-1}_{1,l-1}(x)$ 的值。
时间复杂度 $O((n+q) \log n)$ 空间复杂度 $O(n \log n)$，可以通过 Subtask 2、3、4，结合算法一、二、四获得 $66$ 分。
考虑将算法四和算法五结合起来，也就是将算法五中每个节点的数据结构更换为算法四中的树合并 Trie。想法是很简单的，但是操作起来可能有不小的困难。
第一点是节点的合并可能会导致两个区间变为同一个区间，不过它们的区间长度会是相同的所以只需要添加一些额外的结构就可以描述这样的关系：对于同一个长度的所有区间维护一个并查集表示区间之间的合并关系，再对每个被分裂区间维护其分裂之后产生的两个区间。这样可以在 $O(\log V \alpha(n))$ 的复杂度内查询每个值对应的区间。并查集的节点可以动态开保证空间使用不超过 $O(n \log n \log V)$。
第二点也是最重要的问题，空间常数过大。线段树内每个节点需要记录至少 8 字节标记（因为每一位有四个状态可以用两个 bit 压掉），还有分裂产生的并查集上的记录，这将导致空间常数的大量增加，很有可能无法在 $\texttt{512MB}$ 的空间限制下通过本题。
当然如果你用这个算法通过了，那你真的很厉害！同时存在其他做法也可以在博客评论区进行交流。可以通过 Subtask 2、3、6、8，结合算法一、二、六获得 80 分。
我不会 Trie！也不会线段树！能不能做这题呢？能！
一个很朴素的想法是把 $+1$ 变成 $\mathrm{bitxor}\ 1$ 去维护，问题出在进位。那么我们可以考虑什么时候某一个 $+1$ 操作会影响到正在询问的第 $L$ 位呢？显然地，这要求底下的所有位全部进位了，也就是当且仅当这个操作过后第 $0 \sim L-1$ 个二进制位全部都是 $0$。
这可以给我们启发。每个位置末尾 $0$ 的个数是一个很重要的状态，这决定了 $+1$ 操作是否会给当前的二进制位进行翻转。因此此时可以考虑找到运行操作的过程中所有末尾有 $L-1$ 个 $0$ 的时刻，把这些位置的 $+1$ 操作换成对当前二进制位的翻转操作，其分割的区间则可以通过算法二的数据结构进行查询。
第一个问题是如何找到这样的状态。考虑不断迭代，把末尾 $0$ 的个数变多。具体设计两个递推数组：
$f_0,g_0$ 都是容易推出的，而 $f_{i,x}$ 可以通过 $f_{i-1,x}$ 推出：若 $f_{i-1,x} \neq \infty$，考察第 $i-1$ 位从第 $x$ 个操作做到第 $f_{i-1,x}-1$ 个操作的结果，特别需要注意的是如果第 $f_{i-1,x}-1$ 个操作是 $+1$ 要把它变成翻转操作（因为低位都是 $0$），此时如果答案是 $0$ 则 $f_{i,x}=f_{i-1,x}$，否则现在末尾就是恰好 $i-1$ 个 $0$，有 $f_{i,x} = g_{i-1,f_{i-1,x}}$。$g_{i,x}$ 则可以从 $f_{i,x}$ 类似推出。
给出询问 $v,l,r,L$，若 $v$ 末尾恰好有 $p$ 个 $0$ 且 $p\lt L$，则尝试将 $l$ 移动到 $g_{p,l}$ 处增加 $0$ 的个数。如果 $g_{p,l} \gt r + 1$ 意味着整个过程中末尾 $0$ 的个数不足以用 $+1$ 操作影响第 $L$ 位，此时只需要用算法二的数据结构查询整段的位运算操作产生的影响。否则移动并用算法二的数据结构判断新的 $p$ 是多少。
如果某个时刻 $p \geq L$ 了，不妨假设此时左端点移动到了 $l'$，则先查询 $v$ 的第 $L$ 位在 $[l,l'-1]$ 区间的结果，再从 $l'$ 开始查询。注意到不断让 $l'$ 变成 $f_{L,,l'}$ 就可以遍历低 $L$ 位为 $0$ 的状态，此时有一个暴力为直接暴跳并计算直到即将跳出 $r+1$，最后再把末尾一段计算进去即可。但这样显然复杂度有问题。
还可以注意到的一点是 $f$ 数组是静态结构，考虑建立 $\log V$ 棵树，第 $i$ 棵树上 $j$ 向 $f_{i,j}$ 连边。此时查询操作就相当与在某棵树上跳祖先并维护信息。对每棵树都树链剖分并维护一些重链上信息就可以做到 $O(\log n)$ 查询了，这部分比较简单不作赘述。
总时间复杂度 $O(q(\log V + \log n) + n \log V)$，空间复杂度 $O(n \log V)$，可以通过所有子任务，获得 100 分！
有一个较为显著的常数优化是把 $f$ 和 $g$ 的状态设计为要求 $f_{i,x}-1$ 和 $g_{i,x}-1$ 位置都是 $+1$ 操作，因为其他情况没有贡献，这样树剖部分常数会好一些。但不加这个常数优化也可以较快通过该题。
from zx2003
我们显然可以将算法八进行拓展得到 $O(n \log V)$ 时空预处理 $O(\log n \log V)$ 单次查询的算法解决计算最终答案值是多少而不只是单个二进制位的问题。但我们还可以做得更优。
还是沿用算法八的 $f,g$ 数组以及不断增加末尾 $0$ 的个数的过程。不妨假设增加到末尾 $p$ 个 $0$ 之后无法增加，则 $> p+1$ 的位使用算法二数据结构，第 $p+1$ 位使用 $f$ 数组的树链剖分，而注意到此时 $\leq p$ 位的答案可以通过 $v=0$ 的一次询问得到。
故只需要额外增加 $v=0$ 的询问的在线查询即可。这只需要对算法四进行简单的修改：不提供删除操作并进行可持久化即可。对于叶子合并的问题，可以对合并过程构建出一棵有根森林，每条边由被合并的点指向合并到的点，边权为合并时间。之后每次查询在该森林上树链剖分或倍增跳即可找到该版本下其合并到的节点，然后在对应版本的 Trie 上跳父亲。
这样的预处理时空复杂度 $O(n \log V)$ 单次查询复杂度 $O(\log V + \log n)$。但是其也有一个致命的问题：可持久化、记父亲、好几个标记的 Trie 的空间占用相当的大，同时其他部分也有一定空间占用，很难以比较优美的空间常数通过。有相关想法或实现的选手可以与出题人或 zx2003 哥哥交流。
UOJ Long Round #2 将于 2021 年 6 月 27 日星期日下午 13:00 举行！比赛将进行 6 个小时，共六道题，总体难度与第一次 ULR 大致持平。
这是 UOJ 第二场 Long Round，这场 Round 非常的长，为了让大家有更好的比赛体验，本次比赛将采取 IOI 赛制。每题最多提交 32 发，可以实时查看成绩，最终取分数最高的提交，若有多发分数最高的提交，则取时间最早的，且可以查看排行榜。欢迎大家来玩，来玩就能上分！
凌晨三点，跳蚤国王习惯性的用手机打开 UOJ。屏幕赫然显示：用户已被禁止。
嗐，原来是超级管理员 skip 蚤背叛了跳蚤国王，把跳蚤国王的账号封禁了。
“这不是什么大问题，打开电脑改一下数据库就——等等，我的电脑怎么也打不开了？！”
跳蚤国王才发现自己对 skip 蚤太信任了，为了让 skip 蚤能加入到 UOJ 开发，他允许 skip 蚤 SSH 到自己电脑。这下好，他釜底抽薪，把自己电脑登录密码都改了。
要用魔法打败魔法，你能不能利用黑客技术，帮跳蚤国王打倒邪恶管理员 skip 蚤呢？
出题人：command_block, rushcheyo, zx2003, Isonan, Itst, EntropyIncreaser, mayaohua
这场成绩将计入 rating。
参加本次比赛将有机会获得 UOJ 抱枕！获奖条件的 SHA256 码是 cb99686324ec17d67ba86e717301d2881183453017156942489cd2628c3482ce。比赛结束后将公布条件。
UPD: 恭喜前五名的选手！
import hashlib
s='比赛中第（总提交次数除以2上取整）发提交对应的选手'
m=hashlib.sha256()
m.update(s.encode('utf-8'))
print(m.hexdigest())
#cb99686324ec17d67ba86e717301d2881183453017156942489cd2628c3482ce恭喜 he_____he 获得 UOJ 抱枕！
from zx2003
构造方法非常多。
一个简单的办法是，对于所有 $n$ 名士兵，将第 $i$ 个士兵的坐标设为 $(i,i)$。然后对于所有 $m=n-1$ 次移动，第 $i$ 次移动将第 $i+1$ 个士兵挪到第 $1$ 行。容易发现这样总的变化次数恰好为 $n$。
构造方法仍然非常多。这里给出一种常数较优的做法。
取一个 $400 \times 500$ 的棋盘，将其黑白染色，并在所有黑格上放上士兵。之后每次操作将相邻列的士兵合并起来，这样所有 $n$ 个士兵所属的分组都会变化恰好一次，并且操作步数只需 $250$。
我们分析下这个问题的性质。
对于一组 $y$ 坐标相同的士兵，设其中有 $a$ 人分组为第二组。则按照分组规则，这些士兵所属的 $x$ 坐标上一定分别有不少于 $a$ 名士兵。故而，$a$ 一定不超过 $\sqrt{n}$。对于 $x$ 坐标进行同样分析，我们就知道了每次操作后分组变化次数一定不超过 $2\sqrt{n}$。
对于总的操作次数，我们可以得到一个更好的上界。注意到每次操作时合并的两行中，较小的那一行贡献的变化次数可以用启发式合并的来分析，这一部分的步数总和是 $n\log n$。所以总的变化次数的界为 $m\sqrt{n}+n\log{n}+O(n+m)$。
下面给出标算的构造。
我们将操作分为若干轮执行。对于第 $T$ 轮，我们需要将点集由 $(T-1) \times (T-1)$ 的正方形增加一行一列变为 $T \times T$ 的正方形，这样在该轮中所有 $(T-1) \times (T-1)$ 个原正方形中的点的分组都会变化一次。我们可以现在平面远处预先放好点，用到时再移过来即可。注意由于两维坐标的不对称性，实现时需要注意增加行和增加列的先后顺序。
这样的操作不一定能恰好契合 $n,m$ 的大小，我们截取按照这种构造方法生成的前 $n$ 个点，再将前 $n-m$ 个点在所有操作开始前就摆在它最后应在的位置上。
最后总的操作步数大约为 $\sum_{i=n-m+1}^{n}\sqrt{i}$，遗憾的是未能贴紧理论上限。
本题是来自于 UOJ #309，那道题需要维护每个点的偏好维度。当时一些提交代码是用 vector 存储每行每列上的关键点。按照前面分析这只有根号个，但是众所周知 vector 的动态操作常数很大，所以我当时就想卡下 vector 动态操作的常数。但最后 vector 莫名其妙跑得飞块，我怀疑是因为构造涉及到的点的坐标本质上只有 $O(\sqrt{n})$ 个，然后缓存非常友好。当时尝试 hack 是失败了，不过也有了现在这道题。
不下发 OJ 上的 $O(m\sqrt{n})$ checker 是因为 checker 的实现可能会对选手做题产生提示作用。
from JohnVictor
我会堆暴力！期望得分 $40$ 分。
首先注意到一个性质，就是优美的图和它的补图不能同时连通。
证明：对 $n$ 归纳，设这张图为 $G$，顶点集为 $V$。
如果 $n-1$ 时成立，注意到优美的图的子图和补图仍然是优美的，我们反证，假设原图和补图都连通。
任意找出一个节点 $v$，如果它和所有的其余节点都连边，那么补图不连通，因此我们不妨假设 $v$ 在原图和补图中都有边。
我们考虑 $V- v$ 的原图 $G_1$ 和补图 $G_2$，由归纳假设它们不同时连通。
不妨假设 $G_1$ 不连通，否则我们考虑 $G$ 的补图也是一样的。假设 $G_1$ 的连通分支为 $X_1,X_2,\cdots,x_t(t \ge 2)$，由于 $v$ 不向所有点连边，所以一定存在一个连通分支，不妨设其为 $X_1$，使得 $v$ 不向 $X_1$ 中的所有点连边。
记 $S$ 为 $X_1$ 中和 $v$ 连边的点构成的集合，$T$ 为与 $v$ 不连边的点构成的集合，$X_1$ 的连通性表明存在 $a \in S,b \in T$ 使得 $a,b$ 连边。再由原图的连通性存在 $w \in X_2$ 使得 $v,w$ 连边，此时 $b-a-t-v$ 构成诱导 $P_4$，矛盾。
那么我们可以考虑递归求解这个问题，考虑答案的生成函数，如果原图不连通那么 GF 就是连通分支的 GF 相加，如果补图不连通那么一个顶点集构成团当且仅当它在补图的每一个连通分支中都构成团，也就代表这个 GF 是连通分支的 GF 相乘。
暴力 BFS 判断连通性，时间复杂度 $O(n^3)$，期望得分 $60$。
使用 std::bitset 优化上述暴力 BFS 即可，因为这个图如果连通那么补图不连通，也就是直径为 $2$，可以扩展出第一层节点之后使用或操作。时间复杂度 $O(n^3/w)$，常数很小，期望得分 $70$。
我们考虑更快的找出连通块。使用启发式分裂的思想，我们希望如果一次 BFS 将图分为大小为 $x,y$ 的两个部分，使用的代价为 $O(xy)$。
仍然应用直径为 $2$ 的性质，首先在原图和补图中各取一个度数最小的节点，然后扩展第一层节点，之后再进行并行 BFS，也就是原图和补图依次扩展一个节点，直到确认其中一个连通为止（显然原图和补图至少有一个连通），可以证明复杂度是 $O(n^2)$，期望得分 $100$。
补充一句，复杂度满足要求是因为设最小度为 $x$，那么较小的一部分大小至少为 $x+1$，而扩展的代价至多为 $x(x+y) \le 2xy$。
from djq_cpp
注意到上述算法的本质是用一棵树来刻画这个图，具体地，一个这样的图能和一棵 $n$ 个叶子的树一一对应，两个节点连边当且仅当 LCA 为奇数。
现在我们考虑建树，只用 $O(n)$ 在前 $n-1$ 个点的树中插入一个节点即可。
可以证明在插入一个节点之后，这棵树只有一条链上的节点会发生变化，因为如果互不包含的两个子树中都有向新节点连边的，容易找到一条 $P_4$，补图也一样。
现在我们只用找出这条链，具体做法是 DFS 并维护出哪些点的子树到这个新节点连边情况完全相同（全连边或者全不连边），找出不同的这一条链之后，再专门去改变这条链的节点即可，具体可以见这份代码。
时间复杂度 $O(n^2)$，常数略大于算法四，期望得分 $100$。
from deadecho
经 EntropyIncreaser 氏加强！！！
为了叙述方便，接下来叙述的 $k$ 是原题面中输入的 $k$ 减去 $1$。
考虑按照题意自底向上进行 DP。设 $f_{k,n}$ 是 $k$ 层，$n$ 个节点对应的答案。那么有 $f_{0,n}=[n=1]$ 和递推式 $$ f_{k,n} = \sum_{m=0}^{n-1} \binom{n-1}{m}f_{k-1,m} [n-1-m \equiv 0 \pmod 2] $$ 时间复杂度 $\Theta(kn^2)$，期望得分 $15\sim 25$。
算法一中的递推式可以写作卷积，因此可以用 FFT 优化，时间复杂度 $\Theta(kn\log n)$，期望得分 $25$。
考虑将问题写作生成函数，设 $F_k(x) = \sum_{n} f_{k,n}\frac{x^n}{n!}$，发现有关系 $$ \newcommand{\me}{\mathrm{e}} \newcommand{\d}{\,\mathrm{d}} \begin{aligned} F_0(x) &= x\\ F_k(x) &= \int_0^x F_{k-1}(u) \frac{\me^u + \me^{-u}}2 \d u \end{aligned} $$ 我们发现直接积分是没有显式表达式的，但考虑建立辅助生成函数 $F_k(x) = G_k(\frac{\me^u -\me ^{-u}}2)$。
接下来我们记 $\cosh x=\frac{\me^x+ \me^{-x}}2,\sinh x = \frac{\me^x -\me^{-x}}{2}$。但我们接下来不会用到任何双曲三角函数结论。 $$ \begin{aligned} F_k(x) &= \int_0^x G_{k-1}(\sinh u) \cosh u \d u\\ &= \int_0^x G_{k-1}(\sinh u) \d (\sinh u)\\ &= \int_0^{\sinh x}G_{k-1}(t) \d t\\ G_k(x) &= \int_0^x G_{k-1}(t)\d t \end{aligned} $$ 而我们的目的就是算出 $[x^n] F_k(x)$，因此我们可以分为计算 $G_k(x)$ 的前 $n$ 项系数和所有的 $[x^n] (\sinh x)^m, m\le n$。
由 $G_0(\frac{\me^x -\me^{-x}}2)=x$，根据复合逆关系，设 $u=G_0$，那么 $\frac{\me^u-\me^{-u}}2=x$，设 $t=\me^u$，也就有 $\frac {t-1/t}2=x$，解得 $t=x+\sqrt{1+x^2}$，也就有 $G_0(x) = \sinh^{-1}x = \ln(x+\sqrt{1+x^2})$。
$G_k(x)$ 是将 $G_0(x)$ 连续积分 $k$ 次，也就有 $[x^n]G_k(x) = \frac 1{n^{\underline k}}[x^{n-k}]G_0(x)$，预处理阶乘就可以做到 $\Theta(n)$ 计算 $G_k(x)$ 的系数。
而根据 Lagrange 反演公式，有 $[x^n](\sinh x)^m = \frac m n [x^{n-m}]\left( \frac{x}{\sinh^{-1}x} \right)^n$。
综上，我们可以通过计算生成函数的幂在 $\Theta(n\log n) \sim \Theta(n\log^2 n)$ 内完成。预计得分 $40$。
在 $n$ 很大的时候，我们不得不考虑 $F_k$ 的具体形式。
我们考虑二元 GF $\mathcal F(x,t) = \sum_k F_k(x)t^k$，可依 $F_k$ 的递推关系列出方程 $$ \begin{aligned} \mathcal F(x,t) &= x + t\int_0^x \mathcal F(u,t) \cosh u \d u\\ \frac{\partial}{\partial x}\mathcal F &= 1 + t\mathcal F \cdot \cosh x \end{aligned} $$ 根据一阶 ODE 的通解形式，确定常数项之后我们得到了 $$ \mathcal F(x,t) = \me^{t\sinh x} \int_0^x \me^{-t\sinh u} \d u $$ 提取 $[t^k]$，可知 $$ F_k(x) =\sum_{j=0}^k \frac{(\sinh x)^{k-j}}{(k-j)!} \cdot \int_0^x \frac{(-\sinh u)^j}{j!} \d u \tag{1} $$ 注意到有积分 $$ \int_0^x \me^{ju} \d u = \begin{cases} \frac{\me^{jx} - 1}{j} & j\neq 0\\ x & j=0 \end{cases} $$ 可知 $F_k$ 的形式为 $x^a \me ^{cx}$ 的线性组合，其中 $0\le a\le 1, -k\le c\le k$。
可以使用上述和式，通过 FFT 在 $\Theta(k^2\log k)$ 时间内计算出 $x^a\me ^{cx}$ 基下的系数，如果暴力按照积分式递推系数则可做到 $\Theta(k^2)$。预计得分 $60$，和算法三拼起来可以获得 $75$。
我们希望加速 $x^a \me^{cx}$ 基的系数的计算，考虑 $F_k(\ln x) = G_k(\frac{x-1/x}2)$ 是一组 $x^c(\ln x)^a$ 基，为了借助微分方程的力量，我们首先考虑 $G_k(x)$ 的微分性质。
设 $A(x) = \left(\sinh^{-1} x\right)' = (1+x^2)^{-1/2}$，记其系数为 $a_n$。那么有递推式 $$ na_n = (1-n)a_{n-2} $$ 设 $b_n = \frac{a_{n-k-1}}{n^{\underline {k+1}}}$，即对应的 $B(x)=G_k(x)$ 为 $A(x)$ 做 $k+1$ 次积分，可得递推式 $$ \begin{aligned} (n-k-1) a_{n-k-1} &= (2-n+k) a_{n-k-3}\\ (n-k-1) b_n \cdot n^\underline{k+1} &= (2-n+k) b_{n-2} \cdot (n-2)^{\underline {k+1}}\\ n(n-1)(n-k-1)b_n &= -(n-k-1)(n-k-2)^2b_{n-2}\\ (n-k-1)(n(n-1)b_n + (n-k-2)^2b_{n-2}) &= 0\\ n(n-1)b_n + (n-k-2)^2b_{n-2} &= \frac 1{(k-1)!} \cdot [n=k+1]\\ k^2 x^2B(x) + (1-2k)x^3B'(x) + x^2(1+x^2)B''(x) &= \frac {x^{k+1}}{(k-1)!}\\ k^2 B(x) + (1-2k)xB'(x) + (1+x^2)B''(x) &= \frac {x^{k-1}}{(k-1)!} \end{aligned} $$ 我们考虑设 $X=\frac {x-1/x}2$，令 $P(x)=B\left( \frac{x-1/x}2 \right)$，考虑列出 $P,B$ 之间的导数关系。 $$ \begin{aligned} P'(x) &= \left( \frac{1+x^{-2}}2 \right) B'(X)\\ P''(x) &= \left(\frac {1+x^{-2}}2\right)^2 B''(X) - x^{-3} B'(X)\\ \Rightarrow B'(X) &= \left( \frac{2}{1+x^{-2}} \right) P'(x)\\ B''(X) &= \left( \frac{2}{1+x^{-2}} \right)^2 P''(x) + x^{-3} \left( \frac{2}{1+x^{-2}} \right)^3 P'(x) \end{aligned} $$ 这就导出了 $P(x)$ 满足的方程 $$ \begin{aligned} k^2B(X) + (1-2k)X B'(X) + (1+X^2)B''(X) &= \frac{X^{k-1}}{(k-1)!}\\ k^2 P(x) + (1-2k)X \cdot \left( \frac{2}{1+x^{-2}} \right) P'(x) + (1+X^2) \cdot \left[\left( \frac{2}{1+x^{-2}} \right)^2 P''(x) + x^{-3} \left( \frac{2}{1+x^{-2}} \right)^3 P'(x)\right] &= \frac{X^{k-1}}{(k-1)!}\\ k^2 \left( \frac{1+x^{-2}}2 \right)^3 P(x) + (1-2k)X \cdot \left( \frac{1+x^{-2}}2 \right)^2 P'(x) + (1+X^2) \cdot \left[\left( \frac{1+x^{-2}}2 \right) P''(x) + x^{-3} P'(x)\right] &= \frac{X^{k-1}}{(k-1)!} \cdot \left(\frac{1+x^{-2}}2\right)^3\\ k^2 (1+x^2) P(x) + ((1+2k)x + (1-2k)x^3) P'(x) + ( x^2+x^4) P''(x) &= \frac{X^{k-1}}{(k-1)!} \cdot (1+x^2) \end{aligned} $$ 由此我们已经得到了 $P(x)$ 满足的一个微分方程，将其提取 $[x^n \ln x]$ 设为 $g_n$，提取等式两边的 $[x^n\ln x]$ 可得递推式 $$ (n+k)^2g_n + (n-2-k)^2g_{n-2} = 0 $$ 再提取 $[x^n]$ 设为 $f_n$，提取等式两边的 $[x^n]$ 可得递推式 $$ (n+k)^2 f_n + (n-2-k)^2 f_{n-2} + 2(n+k)g_n + 2(n-k-2)g_{n-2} = [x^n] \frac{X^{k-1}}{(k-1)!} (1+x^2) $$
还需解决边界值问题，根据 $(1)$ 式可知： $$ \begin{aligned} f_k &= \frac 1{2^k}\sum_{j=1}^k \frac{(-1)^j}{(k-j)!j!\cdot j} = \frac {-1}{2^k k!} H_k\\ g_k & = \frac 1{2^kk!} \end{aligned} $$ 由此即可从大到小递推，在 $\Theta(k)$ 时间内计算出系数，然后通过线性筛，只需计算 $\pi(k) \sim \frac k{\ln k}$ 次快速幂，时间复杂度 $\Theta(k\log_k \min(n, p))$。预计得分 $100$。
在操作过程中，我们考虑了复合 $B\left( \frac{x-1/x}2 \right)$，但 $B$ 是形式幂级数，复合的 $\frac{x-1/x}2$ 既有正次项又有负次项，其即使拓展到 Laurent 级数也无法定义复合，但我们对微分方程的推导得到的，对于 $x^c(\ln x)^a$ 组成的「生成函数」给出的系数递推式也确实给出了正确的答案。如何更加严格刻画这种推导，或许是个有趣的问题。
UOJ Round #21 将于 5 月 29 日星期六晚上 19：00 举行！比赛将进行 3 个小时，共三道题。
这是 UOJ 第二十一场 UOJ Round，还是一如既往的省选及以上难度，欢迎大家来玩！UR 终于不是年更了
公元 1453 年 5 月 29 日，君士坦丁堡在奥斯曼帝国苏丹穆罕默德二世领导之下被攻陷，末代皇帝君士坦丁十一世殉国，东罗马帝国自此灭亡。
一天，跳蚤国王醒来，只见大臣伏特告诉他：跳晚国大军兵临城下，危机之时跳蚤国王冲入敌阵，在战场中昏迷后被自己救出。
面对如今已是断壁残垣的跳蚤国，你能不能帮跳蚤国王卷土重来呢？
出题人： zx2003, JohnVictor, deadecho
这场比赛成绩将计入 rating。
参加本次比赛将有机会获得 UOJ 抱枕！获奖条件的 SHA256 码是 6f8d7b1c5f55d1f5a428842fbfb98a719a41151312fec619d39422dee4c1163d。比赛结束后将公布条件。
再次提醒大家比赛中途只测样例，最后会进行最终测试，把所有提交记录重测。
UPD: 恭喜前五名的选手！
import hashlib
s='分数平方乘罚时秒数平方模14530529最大的，如有多个取排名最高的'
m=hashlib.sha256()
m.update(s.encode('utf-8'))
print(m.hexdigest())
#6f8d7b1c5f55d1f5a428842fbfb98a719a41151312fec619d39422dee4c1163d恭喜 Rainybunny 获得 UOJ 抱枕！
网上资料比较少，所以我来补充一下。
本文主要证明：对无向连通图 $G(V,E)$ 的任意生成树 $T$，给每条非树边分配一位，每条树边用长为 $m-n+1$ 的二进制数表示（覆盖这条边的非树边为 $1$，其余为 $0$），那么删掉一组边集后图不连通当且仅当这些二进制数在异或运算下线性相关。
一句话解释：图的回路空间和割空间互为正交补。而以下是面向不懂线性代数的读者的叙述。
定义 $E' \subseteq E$ 是回路，当且仅当每个点都与偶数条 $E'$ 中的边相邻。回路显然对边集异或 $\oplus$ 封闭，因此回路集合可看成 $F_2$ 上的线性空间，称为回路空间 $\mathcal C$。
定义 $E' \subseteq E$ 是割，当且仅当 $\exists S(E') \subseteq V$ 使 $E' = \{(u,v) | u \in S(E'),v \in V-S(E')\}$。容易验证，可以取 $S(E_1 \oplus E_2)=S(E_1) \oplus S(E_2)$，因此割集也可看成 $F_2$ 上的线性空间，称为割空间 $\mathcal D$。
$E$ 自然也可看成 $F_2$ 上的线性空间。
显然，删掉一组边集 $E_1$ 后图不连通，当且仅当 $\exists E_2 \subseteq E_1$ 使得 $E_2 \in \mathcal D$。因此只需证，像命题中一样分配二进制数后，$E_2 \in \mathcal D$ 当且仅当 $E_2$ 中的边异或和为 $0$。
一条非树边 $(u,v)$ 与 $T$ 上 $u \leadsto v$ 的路径的并称为 $\langle G,T \rangle$ 的一只基环，所有 $m-n+1$ 只基环构成 $\mathcal C$ 的一组基。
证明：
由于一条非树边仅在一只基环中出现，因此所有基环线性无关。
我们对回路所含非树边数量 $c$ 归纳证明所有回路均可被基环线性表出。$c=0$ 时，唯一的回路是 $\varnothing$；$c>0$ 时，随便异或一只基环后 $c \gets c-1$ 递归即可。
任取根将 $T$ 看成有根树，$T$ 的一棵子树 $T_1$ 与 $V-T_1$ 之间的边称为一只基础割，所有 $n-1$ 只基础割构成 $\mathcal D$ 的一组基。
证明：
由于一条树边仅在一只基础割中出现，因此所有基础割线性无关。
我们对割所含树边数量 $d$ 归纳证明所有割均可被基础割线性表出。$d=0$ 时，唯一的割是 $\varnothing$；$d>0$ 时，随便异或一只基础割后 $d \gets d-1$ 递归即可。
对于边集 $E_1,E_2$，定义点积 $\langle E_1,E_2 \rangle=\lvert E_1 \cap E_2 \rvert \bmod 2$，那么 $\forall c \in \mathcal C,d \in \mathcal D$，有 $\langle c,d \rangle=0$。
证明：
定义一个点的度数是其属于 $c$ 的邻边数，这是一个偶数。
考虑 $S(d)$ 中点度数和 $s$：两端同属 $S(d)$ 或 $V-S(d)$ 的边，若不属于 $c$ 则被计算 $0$ 次，否则被计算 $2$ 次；其余边被计算恰 $1$ 次。因此 $\langle c,d \rangle \equiv s \equiv 0 \pmod 2$。
$x \in \mathcal D$ 当且仅当 $x$ 与所有基环点积为 0。
证明：
原命题中所赋二进制数就是一条边与所有基环的点积，这就不难看出其正确性了。
练习：
如何判断删掉 $k$ 个点后图的连通性？
和欧式空间不同，这里的空间不能写成一个子空间与其正交补的直和。例如，$C_4$ 的整个边集既是回路也是割。试证明：一个连通图的边空间是回路空间与割空间的直和，当且仅当其生成树数量为奇数。
参考文献：
UOJ Easy Round #9 将于 2 月 27 日星期六晚上 19:00 举行！比赛将进行 3 个小时，共三道题。
这是 UOJ 第九场 Easy Round。自从发完征题公告后，有许多热心的同学给我们投来了不少道有趣的题目，于是我们也有余裕办更多的比赛啦！
寒假转眼间就过完了，大家也都要开学啦！2021 年高考日期确定在 6 月 7 日，这场比赛的开始也意味着高考最后一百天的倒计时敲响。抱憾退役的 OIer 们加油，做好最后的百米冲刺吧！
本场 UER 将以文化课大师 skip 蚤准备高考为主题。
PS：是时候结束 UOJ Extremely hard Round 的时代了！本场 UER 的难度约为 NOI 难度或更低，NOIP 选手也可以来玩。
出题人：skip2004, he_____he, Itst
这场成绩将计入 rating。
参加本次比赛将有机会获得 UOJ 抱枕！获奖条件的 SHA256 码是 80cbc6220dbe91c898555e5078b8ff8fdae45359c12ea90d0c3b2ac35c1d6d83，比赛结束后将公布条件。
注意本场比赛是 OI 赛制，比赛中途只测样例，最后会进行最终测试，把所有提交记录重测。
UPD: 恭喜前五名的选手！
import hashlib
s='有分且罚时（以秒为单位）模分数最大的选手，如果有多个，取排名最高的'
m=hashlib.sha256()
m.update(s.encode('utf-8'))
print(m.hexdigest())
#80cbc6220dbe91c898555e5078b8ff8fdae45359c12ea90d0c3b2ac35c1d6d83恭喜 nqiiii 获得 uoj 抱枕！
由于撞上冬令营以及一些管理员们的个人原因，这次的准备时间非常仓促，即使管理员考前熬了几次夜也难以称得上进行了充分的准备，C 题和 E 题还发生了暴力通过的事故，先在此表示道歉！
Idea, data, std from MatKave, solution from rushcheyo
良心送温暖大水题~
题目要最小化最大值，不妨二分答案，下面判断答案 $x$ 是否可行。
显然第 $i$ 个米其林精品要在 $[a_i,b_i+x]$ 中选一天吃。这是一个经典问题，按左端点排序贪心即可。
具体的，我们考虑左端点最小的区间 $y$，假如只有一个，那么它一定在第 $a_y$ 天被吃，否则移到第 $a_y$ 天不会产生冲突；同理地，若有多个左端点最小的区间，我们显然会在第 $a_y$ 天吃右端点前 $m$ 小的。我们扫过天数，用堆维护现在可以吃且没被吃的区间即可。
复杂度 $O\left(n \log^2 n\right)$，期望得分 $65$ 分，实际得分 $100$ 分。
咦上面的算法中二分答案好像没啥用？直接去掉就好了！复杂度 $O(n \log n)$，期望得分 $100$ 分。
具体地，上面每次二分的过程中，左端点排序的结果并没有变，左端点相同时由于右端点都加了 $x$，相对顺序也没有变，所以直接拿堆扫过去并更新答案就好了。
Idea, solution from rushcheyo, data, std from skip2004
首先要做一步 easy 的转化：
充分性是显然的，必要性考虑反证：任意两条路径都是连通的。这也是显然的，我们在两条路径上各取一个点，把这两个点树上路径每条边都随便取一条链，就整出了一条路径。
那么给定 $m$ 条链时，我们只需要枚举一条边，使得边两边都存在链，然后用经过这条边的链数更新答案即可。这样我们得到 $O(nq)$ 的做法，期望得分 $48$ 分。
下面就要用数据结构维护了。
先考虑链的情况，我们可以直接对每条边维护：子树内的链数 $X$、子树外的链数 $Y$ 和经过这条边的链权和 $Z$。然后线段树上维护 $X$ 的最小值、$Y$ 的最小值、$Z$ 的最小值、$X$ 不取到最小值时 $Z$ 的最小值，$Y$ 不取到最小值时 $Z$ 的最小值、$X$ 和 $Y$ 均不取到最小值时 $Z$ 的最小值，之后判一下前两项是不是 $0$ 就能轻松算答案。这样结合算法一能拿到 $71$ 分。
上树的话，我们发现每次是对 $X$ 到根加，对 $Y$ 全局加再减掉两条链的并，对 $Z$ 链加。拿树剖等维护可以做到 $O\left(n \log^2 n\right)$ 或 $O(n \log n)$。期望得分 $100$。
上面这个做法好难写啊！注意为了选手和出题人身体健康本题只有加入操作，每条边的状态（子树内有链，子树外有链）只会变化 $O(1)$ 次，可以用并查集 / 链表等找到每次边状态的变化而不是暴力维护 $X/Y$。期望得分 $100$。
上面这个做法还是好难写啊！注意问题是离线的，考虑倒着做，每次删掉一条链。我们称一条边的贡献是覆盖它的链的权值和。考虑这条链经过的贡献最小的边，如果这条边合法而且等于之前的答案，那么本次选这条边就是答案；如果这条边不合法，以后更不可能合法，将其贡献改为 $+\infty$ 即可；如果合法但无法更新答案，那我们一条条检查现在贡献最小的边，合法就停止并输出答案，不合法就将其贡献改为 $+\infty$。于是我们把并查集 / 链表都去掉了。期望得分 $100$。
本题大家纷纷通过了，但是有几位选手可以证明甚至是相信自己算法的时间复杂度呢？
Idea, data, std from skip2004, solution from mayaohua
mayaohua 和 skip2004 讨论后想出了标算。
题意其实就是给一个 $ n $ 个点的无向图，每次可以询问一个点集是否是独立集，要求还原出整张图。
一个暴力的想法是依次枚举所有点对 $ (u,v)(u \lt v) $ ，分别询问这些点对是否是独立集（即它们间是否有边）。
询问次数和点集大小和都是 $ O\left(n^2\right) $ 级别的，期望得分 $ 25 $ 分。
考虑一个剥独立集的做法：每次从图中删去一个极大的独立集（剩余点均和这个独立集中点有边），然后递归还原剩下的子图，再还原独立集中的点和不在独立集中的点间所有边。寻找独立集的时候只需要依次加入每个点，询问现在的极大独立集加上这个点后是否仍为独立集。还原边时，可以枚举不在独立集中的每个点，尝试二分出它和该独立集间的所有边。
不算还原边的部分询问次数为 $ O(m) $ ，而每次寻找一条边需要 $ O(\log n) $ 轮，于是总询问次数是 $ O(m\log n) $ 级别。
不算还原边的部分点集大小和为 $ O\left(n^2\right) $ ，而寻找一条边时直接二分的话，容易证明点集大小和是 $ O(nm) $ 的，如果做一个小优化，每次寻找某个点和一个独立集间的所有边时进行整体分治，可以证明点集大小和是 $ O\left(n^2\log \left(\frac{m}{n}\right)\right) $ 的。
期望得分 $ 60 $ 分，精细实现的话实际得分 $ 100 $ 分。
初始时随机打乱所有点。
考虑一个分治算法，每次尝试还原出点集 $ S $ 内的所有边。首先将 $ S $ 均匀划分为 $ L $ 和 $ R $ ，递归找出点集 $ L $ 和点集 $ R $ 内的所有边，然后尝试找出 $ L $ 和 $ R $ 间的边。
首先将 $ L $ 和 $ R $ 划分为尽量少的独立集。这可以应用一个贪心策略，每次寻找一个度数最小的点删去，得到一个点序列，接着从后往前给每个点选择任意划分到一个标号最小的独立集，使得不产生冲突。容易证明若 $ L $ 内部边数与 $ R $ 内部边数总和为 $ ms $ ，可以划分出 $ O\left(\sqrt {ms}\right) $ 个独立集。接着将大小 $ >2\sqrt{ms} $ 的独立集拆分，可以分别将 $ L $ 和 $ R $ 划分为 $ O\left(\sqrt {ms}\right) $ 个大小为 $ O\left(\frac{\lvert S \rvert}{\sqrt {ms}}\right) $ 的独立集。
随后我们枚举 $ L $ 和 $ R $ 间的每个独立集对，询问它们的并集是否是独立集。若它们的并集不是独立集，我们尝试找出它们间的所有边，这可以采取一个分治策略：每次同时将两侧均匀分成两半，分别询问 $ 4 $ 组独立集对间是否有边，若某个独立集对间有边则递归下去寻找。
考虑分析这个算法。
首先分析询问次数。
第一部分枚举每个独立集对间寻找它们的并集是否是独立集，这至多询问 $ O\left(\sqrt {ms}^2\right)=O(ms) $ 次，而由于是均匀分治，分治树深度 $ O(\log n) $ ，容易看出这部分总询问次数是 $ O(m\log n) $ 的。
第二部分分治寻找边，容易看出若找到了 $ k $ 条边，询问次数是 $ O(k\log n) $ 的，因此这部分总询问次数也是 $ O(m\log n) $ 的。
那么整个算法的询问次数就是 $ O(m\log n) $ 的。
接着分析点集大小和。
第一部分枚举每个独立集对间寻找它们的并集是否是独立集。由于两侧都只有 $ O(\sqrt {ms}) $ 个独立集，因此点集大小和是 $ O\left(\lvert S \rvert\sqrt {ms}\right) $ 的。
引理 1： $ n $ 个点 $ m $ 条边的无向图中，随机 $ k $ 个点导出子图边数的根号期望是 $ O\left(\frac{\sqrt {m}k}{n}\right) $ 的。
证明：考虑所有 $ k $ 个点的导出子图集合 $ G_k $ ，其中 $ |G_k|=\binom{n}{k} $ 。那么边数的根号期望为 $ \frac{\sum_{G\in G_k}\sqrt {|E|_{G}}}{|G_k|}\leq \sqrt {\frac{\sum_{G\in G_k}|E|_{G}}{|G_k|}}=\sqrt {\frac{m\cdot \binom{n-2}{k-2}}{\binom{n}{k}}}=O\left(\frac{\sqrt {m}k}{n} \right) $ ，其中不等号应用了琴生不等式。
那么由于初始时我们打乱了点集，容易分析出第一部分期望点集大小和为 $ O\left(\sum_{i=1}^{\lceil \log n\rceil}2^{i-1}\cdot \frac{n}{2^{i-1}}\cdot \frac{\sqrt {m}\frac{n}{2^{i-1}}}{n}\right)=O\left(n\sqrt {m}\right) $ 的。
如果不采用随机化，视实现不同分别可以卡到 $ O\left(n\sqrt m\log n\right) $ 或 $ O\left(n\sqrt {m\log n}\right) $ 的上界。
第二部分分治寻找边。
引理 2：对于 $ n_1,n_2,\ldots,n_k,m_1,\ldots,m_k>0 $ ，且 $ m_1+\ldots+m_k=m $ ，则 $ \sum_{i=1}^{n}n_i\sqrt {m_i}\leq \sqrt {(\sum_{i=1}^{n}n_i^2)m} $ 。
证明：由拉格朗日乘数法，容易得到当 $ m_i=\sqrt {\frac{n_i^2\cdot m}{\sum_{i=1}^{n}n_i^2}} $ 时取极大值 $ \sqrt {\left(\sum_{i=1}^{n}n_i^2\right)m} $ 。
引理 3：在一对大小为 $ O(\lvert S \rvert) $ 的独立集间分治寻找边，若找出了 $ k $ 条，则点集大小和是 $ O(\lvert S \rvert\sqrt {k}) $ 的。
证明：分治寻找边的树形结构可以认为是一棵四叉树，其中第 $ i $ 层至多有 $ 4^{i-1} $ 个点，且每个点对应点集大小为 $ O\left(\frac{\lvert S \rvert}{2^{i-1}}\right) $ 。考虑前 $ \lceil log_4 k\rceil $ 层，这部分点集大小和至多是 $ \sum_{i=1}^{\lceil log_4 k\rceil}4^{i-1}\cdot \frac{\lvert S \rvert}{2^{i-1}}=O\left(\lvert S \rvert\sqrt {k}\right) $ 的。而对于后面的层，每条边对应路径的点集大小和至多是 $ \sum_{i>\lceil \log_4 k\rceil}\frac{\lvert S \rvert}{2^{i-1}}=O\left(\frac{\lvert S \rvert}{\sqrt {k}}\right) $ 的。因此总点集大小和也是 $ \mathcal O\left(\lvert S \rvert\sqrt {k}\right) $ 的。
那么考虑某一层，由于我们将 $ L $ 和 $ R $ 分别分成了 $ O(\sqrt {ms}) $ 个大小为 $ O\left(\frac{\lvert S \rvert}{\sqrt {ms}}\right) $ 的独立集，对于每一对有边的独立集，若其中有 $ k $ 条边，对其分治点集大小和为 $ O\left(\frac{\lvert S \rvert\sqrt {k}}{\sqrt {ms}}\right) $ ，而仅有 $ O(ms) $ 对，因此总点集大小和为 $ O\left(\lvert S \rvert\sqrt {m'}\right) $ 。而所有点的 $ \sum m'=m $ ，那么所有点加起来的点集大小和为 $ O\left(\sum_{i=1}^{\lceil \log n\rceil}2^{i-1}\cdot \sqrt {\left(\frac{n}{2^{i-1}}\right)^2m}\right)=O(n\sqrt m) $ 。
那么第二部分点集大小和就是 $ O(n\sqrt m) $ 的。
那么整个算法的期望点集大小和就是 $ O(n\sqrt m) $ 的。
期望得分 $ 100 $ 分。
我们也可以给出一个渐进意义下相同的确定性算法。
考虑将分治的过程改为合并，令一个点集 $ \lvert S \rvert $ 的权值为 $ \lvert S \rvert+ms $ ，即点集大小加上点集内部边数。求一个哈夫曼树，每次选择两个权值和最小的点集合并，合并过程同算法三。
由于每个点被连续合并两次后，所在点集权值至少加倍，而点集总权值是 $ n+m $ ，因此哈夫曼树深度是 $ O(\log n) $ 的。那么类似算法三的分析，询问次数显然还是 $ O(m\log n) $ ，且第二部分点集大小和显然还是 $ O(n\sqrt m) $ 。考虑对第一部分点集大小和换一个方式分析，每个点到根路径的 $ \sqrt {ms} $ 之和放大为 $ \sqrt {\lvert S \rvert+ms} $ 之和，这不超过 $ 2\sum_{i\geq 0}\sqrt {\frac{n+m}{2^i}}=O(\sqrt {n+m})=O(\sqrt m) $ ，因此总点集大小和之和仍是 $ O(n\sqrt m) $ 的。
期望得分 $ 100 $ 分，由于算法常数问题未必可以通过。
由于数据范围问题，各种复杂度不一的算法均可能可以通过。
Idea, data, std, solution from EntropyIncreaser
对于全体满足 $p_i>p_{i+1}$ 的位置恰有 $m$ 个的 $n$ 阶排列，计算 $p_k$ 的分布。
使用著名的 next_permutation 枚举所有排列。
期望得分 $5$。
我们考虑 DP，设 $f(n,m,l)$ 表示对于 $(n,m)$ 来说，$p_n$ 的分布。那么每次考虑在结尾插入一个元素，可以通过前缀和优化转移，每个状态可以 $\Theta(1)$ 得到答案。接下来对于 $p_k$ 的分布的计算，只需要拆成前面一个 $k$ 长度的排列和后面一个 $n-k+1$ 长度的排列，枚举 $p_k$ 分布在其中的位置，以及两边大于号的数量即可。
时间复杂度 $\Theta(n^3)$，期望得分 $20$。
为了方便刻画排列的性质，我们首先需要将问题进行适当的变换。考虑将问题进行下述改写：
对于全体满足 $\alpha_i>\alpha_{i+1}$ 的位置恰有 $m$ 个的实数数列 $\alpha_1,\dots,\alpha_n$，计算 $\alpha_k$ 的分布。其中每个 $\alpha_i$ 在 $[0,1]$ 上均匀分布。
由对称性可知，按照 $\alpha$ 的排名分配的排列，每个排列都是等概率出现的。
那么我们在考察其中一个特定实数的分布的时候，用类似概率密度函数的工具来刻画是较为恰当的。如果一个 $n$ 阶排列中 $\alpha_k$ 的排名是 $j$，那么其贡献的概率密度无非就是 $$ \frac{x^{j-1} (1-x)^{n-j}}{(j-1)!(n-j)!} $$ 这是因为当 $\alpha_k =x$ 时，有 $j-1$ 个数小于其的概率各是 $x$，然后他们有 $(j-1)!$ 种排列方法，大于其的数情况类似。
转化为概率密度的好处在于，我们可以轻松地刻画问题中出现的约束关系，设原先的概率密度函数为 $f(x)$，那么有：
注意到概率密度函数也是个多项式，设原排列中 $p$ 特定位置为 $k$ 的方案数为 $a_k$，那么我们就给出了转化关系： $$ f(x) = \sum_{k=0}^{n-1} f_kx^k = \sum_{k=0}^{n-1} a_k \frac{x^k(1-x)^{n-1-k}}{k!(n-1-k)!} $$ 因此，不难得到其反演： $$ \sum_{k=0}^{n-1} \frac{a_k}{k!(n-1-k)!} x^k = \sum_{k=0}^{n-1} f_k x^k (1+x)^{n-1-k} $$ 接下来，我们可以开始讨论怎么解决这个问题了。
设 $F(u,v,t)$ 表示一个排列，用 $u$ 计量 $"<"$ 的数量，用 $v$ 计量 $">"$ 的数量，用 $t$ 计量概率密度，此时排列末尾的分布。立即列出方程 $$ F(t) = 1 + u\int_0^t F(\tau)\d \tau + v\int_t^1 F(\tau) \d \tau $$ 进行微分，可得 $$ F' = (u-v)F $$ 众所周知，这个微分方程的解是 $$ \newcommand{\me}{\mathrm{e}} F(t) = C\me^{(u-v)t} $$ 但 $C$ 是包含 $u,v$ 项的，我们需要定出其形式。将原式带入 $t=0,1$ 的情况，设 $I=\int_0^1 F(t)\d t$，可得 $$ \begin{aligned} 1+vI &= C\\ 1+uI &= C\me^{u-v}\\ C &= \frac{u-v}{u-v\me^{u-v}}\\ F &= \frac{(u-v)\me^{(u-v)t}}{u-v\me^{u-v}} \end{aligned} $$ 由于接下来要把两边粘起来，大小号是反过来的。
我们接下来让 $x$ 计量边数，$y$ 计量 $">"$ 的数量。对于左侧，我们需要令 $u=x,v=xy$，对于右侧，我们需要令 $u=xy,v=x$。则有 $$ \begin{aligned} L &= \frac{(1-y)\me^{x(1-y)t}}{(1-y\me^{x(1-y)})}\\ R &= \frac{(y-1)\me^{x(y-1)t}}{(y-\me^{x(y-1)})}\\ &= \frac{(1-y)\me^{x(y-1)(t-1)}}{(1-y\me^{x(1-y)})} \end{aligned} $$ 设 $n_1 = k-1, n_2 = n-k$，我们需要提取 $[x^{n_1}]L$ 和 $[x^{n_2}]R$，也就有 $$ \begin{aligned}{} [x^n]L&= (1-y)^{n+1}[x^n] \frac{\me^{xt}}{1-y\me^x}\\ %&= (1-y)^{n+1} \sum_{j\ge 0} y^j [x^n]\me^{x(t+j)}\\ &= (1-y)^{n+1} \sum_{j\ge 0} y^j \frac{(t+j)^n}{n!}\\ [x^n]R&= (1-y)^{n+1}[x^n]\frac{\me^{x(1-t)}}{1-y\me^x}\\ %&= (1-y)^{n+1} \sum_{j\ge 0} y^j [x^n]\me^{x(j+1-t)}\\ &= (1-y)^{n+1} \sum_{j\ge 0} y^j \frac{(j+1-t)^n}{n!} \end{aligned} $$ 计算乘积。 $$ \begin{aligned}{} &\quad ([x^{n_1}] L) \cdot ([x^{n_2}] R) \\ &= \frac{1}{n_1!n_2!}(1-y)^{n_1+n_2+2} \left(\sum_{j\ge 0} y^j(t+j)^{n_1} \right) \left(\sum_{j\ge 0} y^j((j+1)-t)^{n_2} \right) \end{aligned} $$ 我们考虑将结果这个 $f(t)$ 多项式插出 $0,\dots,n$ 的点值。
我们发现对于 $u^{n_1}\cdot v^{n_2}$，它会以 $[y^m](1-y)^{n+2}y^{u+v-1}$ 的贡献给满足 $t \in [1-v,u]$ 的所有 $f(t)$。我们不妨做一个差分，就将所有 $u^{n_1}\cdot v^{n_2}$ 以 $[y^m](1-y)^{n+2}y^{u+v-1}$ 的 $-1$ 贡献给 $t=u+1$，$+1$ 贡献给 $t=1-v$。这是两个分别都是卷积。因此通过两次卷积就可以算出 $f(t)$ 的连续点值了。
复杂度 $\Theta\left(n\log^ 2n\right)$，期望得分 $70\sim 100$，取决于实现的常数差异。
插出点值这个过程其实并不是那么必要，我们考虑怎么直接计算系数。首先观察我们所求的和式 $$ \newcommand{\Di}{\mathrm{D}} \begin{aligned} &\quad\frac {(-1)^{n_2}}{n_1!n_2!}[y^m](1-y)^{n+1} \sum_{i\ge 0} \sum_{j\ge 0} y^{i+j} (t+i)^{n_1}(t-(j+1))^{n_2}\\ &=\frac {(-1)^{n_2}}{n_1!n_2!} \sum_{s=0}^m \left([y^m](1-y)^{n+1}y^{s}\right) \sum_{i=0}^s (t+i)^{n_1}(t+i-(s+1))^{n_2} \end{aligned} $$ 里层的和是一个区间求和的形式（这和插值的前面步骤是一致的），我们考虑拆成正方向的无穷和 $\sum_{i+1}$ 加上一个差分 $\Delta_{s+1} f(t) = f(t) - f(t+s+1)$。设 $f_s = \left([y^m] (1-y)^{n+1}y^{s}\right)$，就有 $$ \begin{aligned} &=\frac {(-1)^{n_2}}{n_1!n_2!} \sum_{s=0}^m f_s \Delta_{s+1}\left(\sum_{i+} (t+i)^{n_1}(t+i-(s+1))^{n_2}\right)\\ &=\frac {(-1)^{n_2}}{n_1!n_2!} \sum_{s=0}^m f_s \left(\sum_{i+} \Delta_{s+1}(t+i)^{n_1}(t+i-(s+1))^{n_2}\right) +C \end{aligned} $$ 我们这里将 $\Delta$ 换到里面之后，无穷和的常数项其实就没法确定了。
一个常数小的计算 $C$ 的方法是注意到常数项在变换后对数列的影响恰好是给所有数加上一个量，而我们知道所有数的和必然是欧拉数 $\left\langle {n \atop m} \right\rangle$，所以就很容易修正了。 $$ \begin{aligned} &=\frac {(-1)^{n_2}}{n_1!n_2!} \sum_{i+} \left(\sum_{s=0}^m f_s\Delta_{s+1}(t+i)^{n_1}(t+i-(s+1))^{n_2}\right) +C\\ &=\frac {(-1)^{n_2}}{n_1!n_2!} \sum_{i+} \left(\sum_{s=0}^m f_s\left[(t+i)^{n_1}(t+i-(s+1))^{n_2} - (t+i+(s+1))^{n_1}(t+i)^{n_2}\right]\right) +C\\ \end{aligned} $$ 根据 Taylor 公式，我们知道 $f(t+c) = \me^{c\Di} f(t)$，其中 $\Di$ 是对 $t$ 的求导算子。因而不妨设 $F(x)=\sum_s f_s x^{s+1}$，就有 $$ \begin{aligned} &=\frac {(-1)^{n_2}}{n_1!n_2!} \sum_{i+} \left((t+i)^{n_1}F(\me^{-\Di})(t+i)^{n_2} - (t+i)^{n_2}F(\me^{\Di})(t+i)^{n_1}\right) +C\\ &=\frac {(-1)^{n_2}}{n_1!n_2!} \Sigma \left[ \left(t^{n_1}F(\me^{-\Di})t^{n_2} - t^{n_2}F(\me^{\Di})t^{n_1}\right)\right] +C\\ &=\frac {(-1)^{n_2}}{n_1!n_2!} \int B(\Di) \left[t^{n_1}F(\me^{-\Di})t^{n_2} - t^{n_2}F(\me^{\Di})t^{n_1}\right] +C,\quad B(t) = \frac{t}{1-\me^t} \end{aligned} $$ Bernoulli 数的使用是众所周知的，我们考虑如何快速计算 $F(\me^x)$，这需要考虑 $F(x)$ 满足的微分方程。 $$ \begin{aligned} F(x) &= \sum_{i=0}^m \binom{n+1}{m-i}(-1)^{m-i} x^{i+1}\\ &= xf(x)\\ (n-m+1+i)f_i &= -(m-i+1)f_{i-1} + [i=0]C\\ (n-m+1)f(x) + xf'(x)&= -mxf(x) + x^2 f'(x) + C \end{aligned} $$ 令 $G(x)=F(\me^x)=\me^x g(x)$，可得 $$ \begin{aligned} (n+1-m+m\me^x)g(x)+(1-\me^x)g'(x) &=C\\ ((n-m)\me^{-x} +m+1)G + (\me^{-x}-1)G' &= C \end{aligned} $$ 我们可以通过半在线卷积的方法进行计算，时间复杂度 $O \left(\frac{n\log^2 n}{\log \log n}\right)$。预计得分 $100$。
虽然数据范围是 $5\times 10^5$，但是半在线卷积还是很快的，胡写的标程只跑了 $1.2\,\mathrm{s}$。
这是一种与算法四殊途同归的推导。我们先不急着提取系数，考虑将两边的总变数写成 $p,q$，那么乘起来就是要提取 $$ (1-y)^2 \frac{\me^{pt(1-y)+q(1-t)(1-y)}}{(1-y\me^{p(1-y)})(1-y\me^{q(1-y)})} $$ 的 $[y^mp^{n_1}q^{n_2}]$。首先可以对 $p,q$ 做换元，提出来 $(1-y)$ 的幂，就变成了 $$ (1-y)^{n+1} \frac{\me^{pt+q(1-t)}}{(1-y\me^{p})(1-y\me^{q})} $$ 我们对其施**分式分解**，即得 $$ (1-y)^{n+1} \me^{pt+q(1-t)} \frac 1{\me^p -\me^q} \left(\frac{\me^p}{1-y\me^p} - \frac{\me^q}{1-y\me ^q}\right) $$ 但是 $\me^p-\me^q$ 的倒数在计算上的意义是令人困惑的，但是我们若给上式对 $t$ 求导，可得 $$ \begin{aligned} &\quad (1-y)^{n+1} \me^{pt+q(1-t)} \frac {p-q}{\me^p -\me^q} \left(\frac{\me^p}{1-y\me^p} - \frac{\me^q}{1-y\me ^q}\right)\\ &= (1-y)^{n+1} \me^{pt+q(1-t)} \frac {(p-q)\me^{-q}}{\me^{p-q} - 1} \left(\frac{\me^p}{1-y\me^p} - \frac{\me^q}{1-y\me ^q}\right)\\ &= (1-y)^{n+1} \me^{(p-q)t} B(p-q) \left(\frac{\me^{p}}{1-y\me^p} - \frac{\me^q}{1-y\me ^q}\right),\quad B(x) = \frac{t}{\me^t-1} \end{aligned} $$ 因此我们对 $y$ 提取系数，就出现了算法四中的 $G(x)=F(\me^x)$： $$ \me^{(p-q)t}B(p-q)(G(p)-G(q)) $$ 以 $\me^{(p-q)t}B(p-q)G(p)$ 为例，换元为 $\me^{p(1-r)t}B(p(1-r))G(p)$，提取 $[p^{n-1}r^{n_2}]$，展开可得 $$ \begin{aligned} &\quad \sum_j \left([p^{n-1-j}]G(p)\right) \left([r^{n_2}](1-r)^j\right) [p^j]B(p)\me^{pt}\\ &= \sum_j Q_{n-1-j} [p^j] B(p)\me ^{pt}, \quad Q(p) = \sum_j \left([p^{n-1-j}]G(p)\right) \left([r^{n_2}](1-r)^j\right)p^j\\ &= [p^{n-1}]Q(p)B(p)\me^{pt}\\ &= \sum_j \frac{t^j}{j!} [p^{n-1-j}] Q(p)B(p) \end{aligned} $$ 这种做法的实际实现几乎是和算法四一致的。
Idea from rushcheyo
Checker 有两版，分别由 rushcheyo 和 vfleaking 完成
Task 1, 3: std, solution from rushcheyo
Task 2: std, solution from skip2004
本题准备时间实在太短，主要的精力都花在搭建嘿嘿计算机上了，题目本身内容不是很有趣，再道歉一次。
由于时间仓促，我没实现任意一种暴力。从比赛现场来看，堆排序和归并排序都可以拿到一定的分数。在此基础上和其他任务一样把分治叉数增大到 $\Theta(w)$ 就可以优化一个 $\log w$ 因子达到接近满分。
std 的做法是，首先将数组随机 shuffle，然后一个一个把元素插进最 naive 的 BST，最后先序遍历 BST 即可。每次插入的时候要找到插入位置，需要 $O(\log n)$ 次读，然后插结点仅需 $O(1)$ 次写，于是期望时间复杂度为 $O(nw + n \log n)$。
首先如果我们不知道下标是多少，我们只能在内部实现数据结构，这是很低效的，需要大量的判断语句，因此我们考虑把下标转移到外部。
我们可以用好多好多 CMP 下标和 JMP 来把程序分成 $n$ 个部分，每个部分都是下标确定时候要做的操作。
然后使用树状数组来进行维护，我们求出已知下标时需要访问的位置，直接实现即可。
但是由于修改复杂度较高，所以我们可以把树状数组的叉数提高至 $\Theta(w)$，这样复杂度为 $O(n w\log_w n)$。
事实上，这里层数不大，类似于分块，而分块有这样一种常数优化的技巧：询问一个块内区间信息，用大块信息减去其余信息来求解它。
我们记 $s_i$ 为 $\sum_{x=0}^i a_{x}$。容易发现一个区间 $[l, r]$ 可以用一条指令的代价由 $s_{l-1}$ 算出 $s_{r}$ 或者由 $s_{r}$ 算出 $s_{l - 1}$，同时这个区间内元素发生修改时它需要被更新。因此如果我们知道所有这些区间，只需要连边跑最短路就可以知道怎么最快求解一个 $s_i$。
这里 std 选用了 $[i, i], [32i, 32i+31], [928i, 928i + 927]$ 这些区间，得到了一个还不错的解。
这不是裸的 FFT 吗？容我抄个 FFT 板子，改成 hei++ 语言，一发 AC！出题人可真 sb。
本题的指令集中间进行了一次大更换，在迁移老版 std 时我忘记了寄存器数量达到了 $32$ 之多，导致 task 3 的 std 浪费了一些拷贝的时间，致使直接的 FFT 代码通过了，非常非常抱歉！选手赛后做题时可认为本任务 $u=2363007$。
与任务二中的思想类似，我们将 FFT 的叉数增大到 $\Theta(w)$，本题不妨设叉数 $k=16$。
$k$ 叉 FFT 的做法是，先将多项式 $f$ 按 $\bmod k$ 分类：$f(x)=\sum_{i=0}^{k-1} x^if_i(x^k)$，于是有：
$$ f\left(\omega_n^{i+\frac{n}{k}p} \right)=\sum_{j=0}^{k-1} \omega_n^{\left(i+\frac{n}{k}p\right)j}f_j\left(\omega_n^{ik}\right)=\sum_{j=0}^{k-1} \omega_n^{\left(i+\frac{n}{k}p\right)j}f_j\left(\omega_{n/k}^{i}\right) $$
这样的做法时间复杂度是 $O\left(nk \log_k n \right)$ 的，但只需要 $O(n \log_k n)$ 次写操作，毕竟最内层只有算术运算，于是总复杂度为 $O\left(nw\frac{\log n}{\log w}\right)$，比起裸暴力优化了 $O(\log w)$。
然后和经典的 FFT 类似，我们可以在 $k$ 进制下 reverse bits，就能把程序转成非递归了。当然这不是必要的。
希望大家能够爱护 UOJ 环境，不要发无意义的博客。
封禁名单：
鄂公网安备 42010202000505 号Server time: 2024-11-21 14:21:08