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 抱枕！
鄂公网安备 42010202000505 号Server time: 2024-11-21 13:11:43