后门

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 _{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_1{c}_2,k_1{k}_2)$。

$S(n,m)$ 相当于计数有多少种筛选序列叠加后最终得到单一的 $\{A_m\}$。

注意到我们总是可以根据 $m,k$ 唯一确定出 $(c,k)$ 中的 $c=mmodk$ ，所以我们可以只关心筛选中的模数 $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\le m-s$ （在前面有一个数）或 $m+s<n$ （在后面有一个数）。

  等价的条件为 $s\le max(m,n-m-1)$。

• 在最后一步，筛选中的数变为单一的 $m$。（并停止）

  最后一步的筛选 $k_p$ 要满足 $s{k}_p>max(m,n-m+1)$ (将前面的条件取反)

  除此之外，还要满足 $k_p$ 不超过 $s$ 生效后的序列长度。

  这个长度为 $\lfloor m/s\rfloor +\lfloor (n-1-m)\rfloor /s+1$ （分别计算 $m$ 前后的位置个数）。

  总的条件为 $k_p\in (\lfloor max(m,n-m-1)/s\rfloor ,\lfloor m/s\rfloor +\lfloor (n-1-m)/s\rfloor +1]$

综上，我们只需要得知 $\prod _{i=1}^{p-1}{k}_i$ 与 $k_p$ 即可判定一个筛选序列是否符合要求。

定义 $H(n)$ 为各元素 $>1$ 的有序整数序列乘积为 $n$ 的方案数。

$H(n)$ 可由以下简单 DP 求解 ： $$H(n)=\sum _{d|n,d\ne n}H(d)$$

复杂度为 $O(\sum _{i=1}^{n}d(i))=O(n\log n)$。

考虑枚举 $s$ ，则 $k_p$ 的方案数可以确定。$k_{1\sim p-1}$ 得到 $s$ 的方案数即为 $H(s)$ 。

$$\begin{array}{rl}S(n,m)& =\sum _{s=1}^{max(m,n-m-1)}H(s)\ast (\lfloor m/s\rfloor +\lfloor (n-m-1)/s\rfloor +1-\lfloor max(m,n-m-1)/s\rfloor )\\ & =\sum _{s=1}^{max(m,n-m-1)}H(s)\ast (\lfloor min(m,n-m-1)/s\rfloor +1)\end{array}$$

上式容易整除分块计算。逐个计算 $S$ ，复杂度 $O(n\sqrt{n})$ 。期望得分 $65$。

算法三

对每个 $m$ 均进行整除分块是不优的，考虑利用之前的信息来优化复杂度。

首先做一步转化 ：

$$D(n)=\sum _{s}H(s)\ast \lfloor n/s\rfloor$$

$$S(n,m)=D(min(m,n-m-1))+\sum _{s=1}^{max(m,n-m-1)}H(s)$$

然后考虑如何求 $D(1\sim n)$。

定义 $\mathrm{\Delta }D(n)=D(n)-D(n-1)$

$$\mathrm{\Delta }D(n)=\sum _{s}H(s)(\lfloor n/s\rfloor -\lfloor (n-1)/s\rfloor )$$

注意到 $\lfloor n/s\rfloor \ne \lfloor (n-1)/s\rfloor$ 当且仅当 $s|n$ ，且此时 $\lfloor (n-1)/s\rfloor =\lfloor n/s\rfloor -1$。

于是有 ：

$$\mathrm{\Delta }D(n)=\sum _{s|n}H(s)$$

和 $H(s)$ 原本的递推式结合，即可得到 $\mathrm{\Delta }D(n)=2H(n)$。

但有一个例外，当 $n=1$ 时是 $\mathrm{\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=\left(\begin{array}{cc}a& b\\ c& d\end{array}\right)$$，那么询问 $B={\mathbf{0}}_{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\ne 0$ 我们可以唯一确定 $d$。

这样在大部分情况下我们可以用 $4$ 次询问通过 $n=2$ 的数据，但是可能会遇到除 $0$ 的情况，一个简单做法是我们初始时随机一个矩阵 $C$，每次询问的时候都把 $B$ 加上 $C$，这样解出来的是 $A+C$，减回去即可。这样既可以大概率避免出现除 $0$ 的窘境了，但是数据造水了，并没有造 $0$ 的数据。

这样至多花费 $4$ 次询问，可以通过子任务 $1\sim 2$，期望得分 $20$ 分。

算法三

对于 $n\le 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^{\ast }=\frac{1}{det(A)}{A}^{-1}$。这里 $A^{\ast }$ 是 $A$ 的伴随矩阵，有 $(A^{\ast }{)}_{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)})\dots (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)\ne (1,1)$）与 $det(A)$。由于 $det(A^{\ast })=det(A{)}^{n-1}$，若 $A^{\ast }$ 的 $M_{1,1}$ 不是 $0$ 我们可以同样解出 $M_{1,1}$（$A$ 的），便能节约一次。

由于 $A^{\ast }=\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}+\cdots +S_{a_k}$，对于 trie 树上的每个节点，求出该点表示的串 $u_i$ 在 $T$ 中的出现次数。

记号约定

记 $match(s)$ 表示 $s$ 在 trie 树上能够匹配的最长后缀对应的节点。

记 $exi(s)$ 表示 trie 树上存在一个节点 $x$ 使得 $u_x=s$。

记 $de{p}_x$ 表示点 $x$ 在 trie 树上的深度。

记 $an{c}_{a,b}$ 满足 $an{c}_{a,b}$ 是 a 在 fail 树上的祖先，且 $de{p}_{an{c}_{a,b}}=b$。

算法一

对原 trie 树建立 AC 自动机，把串T在上面走一遍，最后做一遍 fail 树上前缀和即可。

注意由于字符集过大，而且 trie 树的所有叶子深度和没有保证，故需要使用可持久化数组优化建立 AC 自动机的过程。

复杂度 $O(l\log w+mS\log w)$，可以通过 subtask 1，期望得分 7。

算法二

考虑优化串 T 在 AC 自动机上行走的过程。

假设我们已经求出了 $en{d}_{i,j}$ 表示 $match(u_j+S_i[1\dots le{n}_{i,j}])$，其中 $le{n}_{i,j}=max\{x|exi(u_j+S_i[1\dots x])\}$。

之后我们尝试求出 $di{r}_{i,j}=match(u_j+S_i)$。

由于 $en{d}_{i,j}$ 已知，所以我们可以知道从点 $j$ 出发沿 $S_i$ 在 AC 自动机上行走时，第一次跳 fail 边后到达的节点 $k=fail(en{d}_{i,j})$。

如果 $de{p}_k\le de{p}_{en{d}_{i,j}}-de{p}_j$，则意味着 $u_{di{r}_{i,j}}$ 完全是 $S_i$ 的后缀，$di{r}_{i,j}=di{r}_{1,j}$，注意本题中1号点为根节点。

否则我们可以从 $k^{\prime }=an{c}_{k,de{p}_k-(de{p}_{en{d}_{i,j}}-de{p}_j)}$ 处继承答案。

注意由 AC 自动机的性质，$k^{\prime }$ 一定是 $j$ 在 fail 树上的祖先。于是整个算法流程可以在 fail 树上递推计算，DFS 的时候可以开个桶存储在当前 DFS 栈中深度为定值的节点，以便快速查询 $an{c}_{a,b}$。

注意特判不需要跳 fail 边的情况，此时有 $exi(u_j+S_i)$，故 $di{r}_{i,j}=en{d}_{i,j}$。

那么对于每个 $i$，我们可以得到 $match(S_{a_1}+\cdots +S_{a_i})$。

这样问题进一步被转化为：

对于一个串 $S_i$，已知每次开始加入该串时在哪个节点，求每个节点在所有加入该串的过程中被经过多少次。

那么观察从 $x$ 开始的一次加入，我们首先会走到 $en{d}_{i,x}$，然后跳到 $fai{l}_{en{d}_{i,x}}$。

这里我们仍然沿用求 $di{r}_{i,j}$ 时的分类讨论模式。

如果 $de{p}_y\le |S_i|$ ，则 $\mathrm{\exists }k$ 使得 $u_y=match(S_i[1\dots k])$，我们只需对所有 $k^{\prime }\ge k$ ，将 $match(S_i[1\dots k^{\prime }])$ 加上相应的值即可，这可以通过一个后缀和来解决。

否则，接下来我们会走到 $en{d}_y$，这里 $y=an{c}_{fai{l}_{en{d}_{i,x}},de{p}_{fai{l}_{en{d}_{i,x}}}-(de{p}_x-de{p}_{i,x})}$。

容易发现 $y$ 是 $x$ 的后缀，亦即 $x$ 在 fail 树上的祖先。于是我们可以按长度从大到小枚举 trie​ 树上的节点，并在 trie 树上差分得到答案。

于是唯一问题变为 $en{d}_{i,j}$ 的求法，如果在 trie 树上暴力匹配，并且计算 $match(S_i[1\dots k])$ 时暴力跳 fail 边且使用哈希表存边来规避可持久化数组，则总复杂度为 $O(l\log w+n{l}^2+S+m)$，可以通过 subtask 1, 3，期望得分 24。

算法三

对于 subtask 2，我们可以使用 exKMP​ 来优化求 $en{d}_{i,j}$ 的过程。

复杂度为 $O(nl+S+m)$，可以通过 subtask 1, 2, 3，期望得分 38。

算法四

继续优化求解 $en{d}_{i,\ast }$ 的过程。

每次计算 $en{d}_{i,\ast }$ 时，首先通过每条重链上 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

仍然考虑优化求解 $en{d}_{i,\ast }$，但是这次我们转换思路，转为计算 trie 上每个节点对于祖先的 $en{d}_{i,\ast }$ 的贡献。

具体的，对于每个 $i$，我们在 trie 上 DFS 的同时，对于当前点 $x$ 维护出 $u_x$ 的最长后缀 $p$，满足其也是 $s_i$ 的前缀。

则从 $x$ 往下走的时候，对于 $p$ 的一个长为 $j$ 的 border，如果 $x$ 往下走的对应边没有字符 $S_i[j]$ ，则 $x$ 在 trie 上的 $j$ 级祖先 $y$，其 $en{d}_{i,y}$ 就等于 $x$；并且所有的 $en{d}_{i,\ast }$ 都一定能被这样正确计算。

于是唯一的问题就是找到这些 border。

我们先对 $s_i$ 进行预处理，对于每个前缀 $i$，求出 $ls{t}_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$ 的 $en{d}_{i,y}$ 被算了出来，这部分复杂度仍为 $O(l)$。

最后总复杂度 $O(l\log w+nl+S\log \log S+m)$，期望得分 100。

如果可持久化数组实现不当，可能无法通过 subtask 5，只能得到 67 分。

全是 AI 的比赛

Idea, data, std, solution from mayaohua

首先向大家表示抱歉，由于出题人没有出提交答案题的经验，每个测试点没有设计多档部分分，区分度不太足。

原本的想法是出一个对着 AI 攻击的游戏题，但由于出题人能力所限，最后的成品和预期差距比较大，测试点的设计可能不够有趣，但还是希望大家玩得开心。

测试点 1

所有的 AI 都会定向攻击你，且你很难通过给它们加能量来改变它们的目标（即使改变了也不优秀，因为一旦攻击就会吸引仇恨）。因此你的选择只能是逐个击杀并尽量最小化击杀过程中承受的伤害。

注意到所有 AI 都是 $100$ 级，只有体力的区别。显然最优的策略是按体力从小到大击杀，直接排序后模拟一下过程即可。

测试点 2

初始时所有 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$ 轮。

测试点 3

$2\sim 99$ 号 AI 同样永远不会攻击你，但 $100$ 号 AI 会一直攻击你且不能改变目标。因此你的目标就是在尽量少的轮数内击杀 $100$ 号 AI，然后再依次击杀掉剩下的 AI。

你的最优策略显然是在 $2\sim 99$ 号 AI 中选择若干个，并按某种顺序依次击杀。如果我们已经找到了一个排列，就可以通过 DP 或者直接枚举前缀等方法来找到优秀的解。标程做法是先按 $\frac{a_i}{b_i}$ 从大到小排序得到初始排列，再通过爬山/退火随机交换调整来找到较好的排列。

测试点 4

这是一个精心构造的测试点。

初始时所有 AI 都会攻击你，但对每个 AI 你都可以通过一次给它加能量的操作来转移它的攻击目标。更加仔细的观察会发现所有 AI 的第二目标正好是两两配对的，且对每个 AI 的攻击会拉极大的仇恨，因此对于一对 AI，你只需要给编号小的那个加能量，就可以让它们停止攻击你并互相攻击了。显然你应该按每对 AI 的 $a$ 之和从大到小依次执行这个过程，在 $49$ 轮后就没有 AI 攻击你了。

接下来每对 AI 会反复互相攻击，并在 $1000\sim 9000$ 轮中的某个轮数后其中一个 AI 死亡，模拟这个过程可以发现在一对中的一个 AI 死亡时，另一个 AI 的体力也不会非常大（大概在 ${10}^6$ 级别），如果你在之前已经对这个存活下来的 AI 进行了适当的攻击（可以通过给另一个 AI 加能量来避免吸引仇恨），使得它剩余的体力在斩杀线内，就可以在下一轮直接击杀掉它使得你不会被它攻击。于是你可以大胆猜测一定有一个解能使你在这个过程中从不会被攻击，这一定是最优解！事实上你只需要按这个死亡轮数排序，然后直接依次执行进行攻击来调整，由于你后面的等级会快速提升，你每次调整所需的轮数会越来越少，实践证明确实是可行的。

测试点 5

所有 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$。

算法一

使用 $\mathrm{\Theta }(n^2)$ 的拉格朗日插值算法。期望得分 $5$。

算法二

子任务 $7$ 满足 $q^n=1$。我们熟悉这一情况就是 DFT。此时我们知道

$$[x^m]f(x)=\frac{1}{n}\sum _{j=0}^{n-1}{q}^{-mj}f(q^j)$$

可以在 $\mathrm{\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\ne i}(q^i-q^j)}$$

我们先翻转系数，写作

$$f(x)=\prod _{j=0}^{n-1}(1-q^{j}x)\cdot \sum _{i=0}^{n-1}\frac{f(q^i)}{\prod _{0\le j\le n-1,j\ne i}(q^i-q^j)}\cdot \frac{1}{(1-q^{i}x)}$$

其中 $\prod _{0\le j\le n-1,j\ne i}(q^i-q^j)$ 展开后就可以 $\mathrm{\Theta }(n)$ 计算所有，我们可以认为核心问题就是计算

$$\begin{array}{rl}\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}^{-(\genfrac{}{}{0ex}{}{i}{2})}\right)\left(x^j{q}^{-(\genfrac{}{}{0ex}{}{j}{2})}\right)\cdot q^{(\genfrac{}{}{0ex}{}{i+j}{2})}\end{array}$$

其实也就是 Chirp Z-变换的转置。可以在 $\mathrm{\Theta }(n\log n)$ 时间内解决，预计得分 $25$。

算法四

为了解决更大的 $n$，我们肯定要考虑只算某一项系数有什么特点了。

对于每个 $0\le i\le n-1$，我们需要求出 $[x^k]\prod _{j\ne i}(1-q^{j}x)$。设 $P=\prod _{i=0}^{n-1}(1-q^{i}x),S=\sum _{i=0}^{\mathrm{\infty }}\frac{y^i}{1-q^{i}x}$，我们设 $F(x,y)=P\cdot S$，那么带入 $q$ 可得到方程。

$$\begin{array}{rl}F(qx,y)& =(\prod _{i=1}^n(1-q^{i}x))\cdot \left(\sum _{i=0}^{\mathrm{\infty }}\frac{y^i}{1-q^{i+1}x}\right)\\ & =\left(\frac{1-q^{n}x}{1-x}P\right)\cdot y^{-1}(S-(1-x{)}^{-1})\\ \text{(1)}& & =y^{-1}\frac{1-q^{n}x}{1-x}(F(x,y)-(1-x{)}^{-1}P)F(x,qy)& =P\cdot \left(\sum _{i=0}^{\mathrm{\infty }}\frac{y^i{q}^i}{1-q^{i}x}\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}\\ \text{(2)}& xF(x,y)& =F(x,q^{-1}y)-P\cdot \frac{1}{1-q^{-1}y}\end{array}$$

我们的目的是对所有 $i$ 提取 $[x^m{y}^i]$，因此我们得到一个仅沿着 $y$ 的递推式。接下来，我们将式 1 带入式 2。

$$\begin{array}{rl}y(1-x)F(qx,y)& =(1-q^{n}x)(F(x,y)-(1-x{)}^{-1}P)\\ yF(qx,y)-q^{-1}y(qx)F(qx,y)& =(F(x,y)-\frac{1-q^{n}x}{1-x}P-q^{n}xF(x,y))\\ yF(qx,y)-q^{-1}y(F(qx,q^{-1}y)-P(qx)\frac{1}{1-q^{-1}y})& =F(x,y)-\frac{1-q^{n}x}{1-x}P\\ & -q^n(F(x,q^{-1}y)-P\cdot \frac{1}{1-q^{-1}y})\end{array}$$

设 $f_i=[x^m{y}^i]F(x,y)$，那么两边提取系数 $[x^m{y}^i]$，设 $i\ge 1$，便有

$$\begin{array}{rl}{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{array}$$

便可逐此递推，而且 $1-q^{n-i}\ne 0$ 已经蕴含于 $q^i$ 互不相同这一题设中。

我们还需要求出 $[x^m]P$，这可以如法炮制：

$$\begin{array}{rl}P(qx)& =\frac{1-q^{n}x}{1-x}P(x)\\ (1-x)P(qx)& =(1-q^{n}x)P(x)\\ q^i{p}_i-q^{i-1}{p}_{i-1}& =p_i-q^n{p}_{i-1}\\ p_i& =\frac{q^{i-1}-q^n}{q^i-1}{p}_{i-1}\end{array}$$

时间复杂度 $\mathrm{\Theta }(n)$，预计得分 $50$。

算法五

为了最后的子任务，我们需要在 $o(n)$ 时间内计算某一项 $i$ 的 $[x^m{y}^i]F(x,y)$，$\prod _{0\le j\le n-1,j\ne i}(q^i-q^j)$ 以及计算 $[x^m]P$。

这种递推式并非常系数，它和我们曾经遇到的整式递推更为相似，递推系数是一个关于 $(q,q^i)$ 的有理分式。

我们首先来看 $\prod _{0\le j\le n-1,j\ne i}(q^i-q^j)$ 的多次询问如何解决。其可以拆解为计算

$$\begin{array}{rl}& q^{(n-1)i}\prod _{0\le j\le n-1,j\ne i}(1-q^{j-i})\\ & =(-1{)}^i{q}^{(n-1)i}(\prod _{j=1}^{n-i-1}(1-q^j))(\prod _{j=1}^i(1-q^{-j}))\\ & =(-1{)}^i{q}^{(n-1)i}(\prod _{j=1}^{n-i-1}(1-q^j))q^{-\frac{i(i+1)}{2}}(\prod _{j=1}^i(1-q^j))\end{array}$$

因此问题归结于计算 $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)$。进行一次询问的时候，我们只需要再加上剩下的零散部分，复杂度 $\mathrm{\Theta }(b)$。当询问次数 $k$ 较小的时候，只能取 $b=\sqrt{n}$，复杂度为 $\mathrm{\Theta }(\sqrt{n}\log n+k\sqrt{n})$。较大时解得 $b=\sqrt{\frac{n\log n}{k}}$，复杂度 $\mathrm{\Theta }(\sqrt{kn\log n})$。

其他几个递推式可以使用类似手段处理，只需将式子通分。不过在数据范围内一个易于实现的方法是令 $b=min(n,500)$，这样的话 $\mathrm{\Theta }(b^2)$ 算出各部分多项式系数，然后 $\mathrm{\Theta }((n/b)\log n+kb)$ 也可以接受。

预计得分 $100$。

当然，这并非最优理论复杂度，我们可以先得到 $\sqrt{n}$ 个点值之后，每个询问距离最近的点只有 $\sqrt{n}$ 距离，可以将剩下的跳跃过程二进制分解，每轮进行多点求值。这样就能将复杂度降到 $\tilde{O}(\sqrt{n}+k)$，但是由于所含的 $\log$ 因子可能较多，在目前的数据范围下可能不会有很好的表现。

晚了一步……

我们算法五的步骤，在 2020 年被学术界捷足先登了：

• Fast Computation of the $N$-th Term of a $q$-Holonomic Sequence and Applications, Alin Bostan, Sergey Yuekevich. (arxiv)

Picks loves segment tree IX

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$ 的异或和，并计算 $pr{e}_{x,y}$ 表示第 $x$ 个操作之前（不包含 $x$）的所有操作中对第 $y$ 位有赋值影响（即变 1 或变 0）的操作中编号最大的一个操作，不存在记为 $0$。这显然可以 $O(n\log V)$ 预处理。

对区间 $[l,r]$ 查询第 $k$ 位取值时，考察 $pr{e}_{r+1,k}$ 与 $l$ 的大小关系。若 $l\le pr{e}_{r+1,k}$ 则其受到了赋值操作影响，最后一个赋值操作是 $pr{e}_{r+1,k}$，故询问 $pr{e}_{r+1,k}$ 到 $r$ 中所有异或操作的异或和结合 $pr{e}_{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\to S$，其中 $f(x)$ 表示的是 $x$ 经过操作序列后变成的数，则 $f$ 是一个一一映射。

利用这个性质，设 $f_{l,r}(x)$ 表示做序列 $l$ 到 $r$ 的操作对应的映射，则求询问 $v,l,r,L$ 的结果可以通过 $f_{1,r}(f_{1,l-1}^{-1}(v))$ 来得到，也就拆成了两个前缀询问。

$f_{1,r}(x)$ 的询问使用之前的可持久化结构进行计算，而 $f_{1,l-1}^{-1}(x)$ 的询问实际上是更加简单的：在 $f_{1,l-1}(x)$ 对应的数据结构中沿着 $x$ 走，通过其最后到达的有效节点的信息和经过的标记即可得到 $f_{1,l-1}^{-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 压掉），还有分裂产生的并查集上的记录，这将导致空间常数的大量增加，很有可能无法在 $\mathtt{\text{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_{i,x}$：给出一个末尾至少有 $i$ 个 $0$ 的数（显然高位不会产生影响），从第 $x$ 个操作开始进行操作，则做完第 $f_{i,x}-1$ 个操作后其末尾第一次又有至少 $i$ 个 $0$。若不存在取 $f_{i,x}=\mathrm{\infty }$。
• $g_{i,x}$：给出一个末尾恰有 $i$ 个 $0$（也就是第 $i$ 位为 $1$）的数，从第 $x$ 个操作开始进行操作，则做完第 $g_{i,x}-1$ 个操作后其末尾第一次又有至少 $i+1$ 个 $0$。若不存在取 $g_{i,x}=\mathrm{\infty }$。

$f_0,g_0$ 都是容易推出的，而 $f_{i,x}$ 可以通过 $f_{i-1,x}$ 推出：若 $f_{i-1,x}\ne \mathrm{\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<L$，则尝试将 $l$ 移动到 $g_{p,l}$ 处增加 $0$ 的个数。如果 $g_{p,l}>r+1$ 意味着整个过程中末尾 $0$ 的个数不足以用 $+1$ 操作影响第 $L$ 位，此时只需要用算法二的数据结构查询整段的位运算操作产生的影响。否则移动并用算法二的数据结构判断新的 $p$ 是多少。

如果某个时刻 $p\ge L$ 了，不妨假设此时左端点移动到了 $l^{\prime }$，则先查询 $v$ 的第 $L$ 位在 $[l,l^{\prime }-1]$ 区间的结果，再从 $l^{\prime }$ 开始查询。注意到不断让 $l^{\prime }$ 变成 $f_{L,,l^{\prime }}$ 就可以遍历低 $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$ 数组的树链剖分，而注意到此时 $\le p$ 位的答案可以通过 $v=0$ 的一次询问得到。

故只需要额外增加 $v=0$ 的询问的在线查询即可。这只需要对算法四进行简单的修改：不提供删除操作并进行可持久化即可。对于叶子合并的问题，可以对合并过程构建出一棵有根森林，每条边由被合并的点指向合并到的点，边权为合并时间。之后每次查询在该森林上树链剖分或倍增跳即可找到该版本下其合并到的节点，然后在对应版本的 Trie 上跳父亲。

这样的预处理时空复杂度 $O(n\log V)$ 单次查询复杂度 $O(\log V+\log n)$。但是其也有一个致命的问题：可持久化、记父亲、好几个标记的 Trie 的空间占用相当的大，同时其他部分也有一定空间占用，很难以比较优美的空间常数通过。有相关想法或实现的选手可以与出题人或 zx2003 哥哥交流。