这篇文档是验题人提供的一些解题思路及同一文件夹下其它文件的说明。出题人 E.Space 的题解请参考 solution 文件夹下的文档。（顺便一说，我看完他的题解之后觉得我写的太详细了，就把比较明显的事实给略去了，如果有看不懂的地方可以自己尝试着理解或证明）

这道题的一个关键是没有给出序列的长度 $n$。我们很难在不预先求出 $n$ 的情况下得到一个满足要求的序列，所以我们需要先求出一个可能的 $n$。

根据题目要求，不难发现每个下标 $i$ 都需要至少被选择一次（$a_n \ne 0$）。那么输入中给的 $k$ 相当于”除此之外，这个序列还需要操作多少次“。直观上，越长的序列能提供越多的额外操作机会。记对于给定的 $n$，所有长度为 $n$ 的能变成全 $0$ 序列的 $\left\{a_n\right\}$ 中，最少的操作次数为 $K_1\left(n\right)$，最多为 $K_2\left(n\right)$。我们希望 $K_1$ 和 $K_2$ 有单调性，这样我们可以通过二分找到一个满足要求的 $n$。

这个单调性是不难证明的。一个长度为 $\left(n+1\right)$ 且所需操作次数最少的序列一定只有 $i = n+1$ 时满足 $a_i = i$，否则它便不是操作次数最少的；而对 $a_{n+1}$ 进行操作之后，我们会得到一个长度为 $n$ 的序列（忽略 $a_{n+1}$ 这一项），这个序列可以变成全 $0$ 序列且至少需要进行 $K_1\left(n\right)$ 次操作。所以一定有 $K_1\left(n\right) < K_1\left(n+1\right)$。

同样，给一个长度为 $n$，需要 $K_2\left(n\right)$ 次操作的序列，这个序列一定没有 $0$；否则，我们可以找到一个满足 $a_i = 0$ 的最小的 $i$，将其改成 $a_i = i$，并将所有在它之前的 $a_j$ 减一（为方便起见，下文将这样的操作称为对 $a_i$ 进行逆操作），这会给我们一个操作次数更多的序列。我们将这个需要 $K_2\left(n\right)$ 次操作的序列补上 $a_{n+1} = n + 1$ 这一项，并将它前面所有 $a_i$ 减一，这样我们就得到了一个长度为 $\left(n+1\right)$，操作次数为 $K_2\left(n\right)+1$ 的序列。因此必有 $K_2\left(n\right) < K_2\left(n+1\right)$。

这一单调性告诉我们，我们可以二分 $n$，通过当前 $n$ 对应的 $K_1\left(n\right)$ 或 $K_2\left(n\right)$ 来判断当前的 $n$ 是大了还是小了。注意这里我们并没有用到 $K_2\left(n\right)$ 与 $K_1\left(n+1\right)$ 的关系，这不影响我们二分的正确性。但实际上可以证明 $K_2\left(n\right) + 1 = K_1\left(n+1\right)$，所以 E.Space 大概不是在做白日梦：每个 $k$ 都必定有解(实际上还要证明从 $K_1\left(n\right)$ 到 $K_2\left(n\right)$ 的每一个 $K$ 都对应一个长度为 $n$ 的序列，参考下文“暴力进位”的部分）。同时，子任务 3 里给出的特殊条件说明，存在某个 $n$ 使得 $k = K_1\left(n+1\right)-\left(n+1\right) = K_2\left(n\right)-n$（可以自己试着证明一下）。

现在的问题是：如何高效地计算 $K_1\left(n\right)$ 或 $K_2\left(n\right)$？以 $K_1\left(n\right)$ 为例，我们知道它对应的序列一定只有 $a_n$ 满足 $a_i = i$。不妨从 $a_n$ 倒着推算，因为后面的 $a_i$ 不会受到前面的操作的影响。如果对 $n\ge 3$ 有 $a_n = n$，那么为了使 $a_{n-1}$ 能归零，$a_{n-1}$ 在操作之后必须为 $\left(n-1\right)$，也即操作之前必须为 $\left(n-2\right)$。类似地，如果已经知道 $a_{i+1}, \cdots, a_n$ 需要 $x$ 次操作，那这 $x$ 次操作会使 $a_i$ 加上 $x$，故必有 $a_i + x\equiv 0\pmod i$。如果 $i\nmid x$，那么 $a_i = i - x \bmod i$，且对 $a_i$ 进行操作的次数为 $\frac{a_i + x}{i} = \left\lceil \frac{x}{i} \right\rceil$；否则 $a_i = 0$ 或 $i$（我们将这样的 $a_i$ 称为可分支的 $a_i$），令其等于 $0$ 会使我们得到操作次数最小的序列。

这样计算是每次 $O\left(n\right)$ 的，所以总共需要 $O\left(n\log k\right)$ 的复杂度来得到我们需要的那个 $n$。得到 $n$ 之后，你可以利用上一段中提到的方法（可分支的 $a_i$）搜索所有的能消成全 $0$ 的序列，但经过出题人 E.Space 的加强之后这个做法大概会被卡掉（考虑一下几百万层的递归搜索，你甚至不知道它会分叉多少次，虽然实测是挺快的）。至于说“大概”，是因为我在写这篇文档的时候我们还没有在正式评测环境上进行最终的测试，所以只能根据本机运行情况来预估。

E.Space 提供了一种暴力的做法，他称其为“暴力进位”：每次选一个下标最小的 $a_i = 0$，并对其进行逆操作。这一思想在上文中也有提到。可以证明这一做法能从操作次数为 $K_1\left(n\right)$ 的序列开始，遍历每一种操作次数，直到得到操作次数为 $K_2\left(n\right)$ 的序列。同一目录下的 force.cpp 就采用了这个做法。

这个做法的复杂度是多少呢？让我们记 $d_i$ 表示在从 $K_1\left(n\right)$ 到 $K_2\left(n\right)$ 的“暴力进位”中 $a_i$ 被选中了 $d_i$ 次。所有的 $d_i$ 之和应该为 $\Delta K\left(n\right) = K_2\left(n\right) - K_1\left(n\right)$，而这大约为 $O\left(k \over n\right)$ 级别（稍后我们将会看到，这个估计是足够准确的）。对于 $a_1$ 来说，每操作一次 $a_i \left(i \ge 2\right)$ 就会使 $a_1 = 1$，而我们不得不释放 $a_1$ 上的 $1$，否则它将会变得不可操作。所以 $d_1 \approx \frac{\Delta K\left(n\right)}{2}$，同时 $d_2 + \cdots + d_n \approx \frac{\Delta K\left(n\right)}{2}$。接着我们考虑 $d_2$：对 $a_3, \cdots , a_n$ 总共操作 $2$ 次就要操作 $a_2$ 一次，所以应该有 $d_2 \approx \frac{\Delta K\left(n\right)}{2} \cdot \frac{1}{3} = \frac{\Delta K\left(n\right)}{6}$，而 $d_3 + \cdots + d_n \approx \frac{\Delta K\left(n\right)}{2} \cdot \frac{2}{3} = \frac{\Delta K\left(n\right)}{3}$。你可能已经看出规律了：对于 $a_i$，它应该被操作 $d_i \approx \frac{\Delta K\left(n\right)}{i\left(i+1\right)}$ 次，而每次操作 $a_i$ 的复杂度为 $O\left(i\right)$，所以对 $a_i$ 进行的模拟操作复杂度为 $O\left(\frac{\Delta K\left(n\right)}{i}\right)$。对所有 $i$ 求和得到总复杂度为 $O\left(\Delta K\left(n\right) \ln n\right) = O\left(\frac{k}{n} \ln n\right)$。

上式中用到了 $n$ 来计算复杂度，但这并不是题目中的已知量，所以我们需要估计一下 $n$ 的大小。如果我们把上一段中的 $\Delta K\left(n\right)$ 换成 $\left(n+k\right)$，我们就得到了对于某个操作次数为 $\left(n+k\right)$ 的序列而言，每个 $a_i$ 需要被操作多少次（你可能需要仔细想一想这是为什么，或者参考下面关于 forward.cpp 的部分）。所以我们有 $1 \approx \frac{n+k}{n\left(n+1\right)}$，即 $n = O\left(\sqrt{k}\right)$。也就是说，我们看上去很暴力的做法实际上是 $O\left(\sqrt{k} \ln k\right)$ 的。我在一台比较慢的 Ubuntu 上测试了一下，基本上能在 0.9s 左右出解。只要评测机足够快，这个做法应该能通过本题，除非出题人精心卡了时限（目前还是 1s 题）。

另外，有的人可能会想用线段树来维护区间修改，但它的常数比较大，无法通过本题（最大的 $\Delta K\left(n\right)$ 似乎有近七百万，除非你的常数真的特别优秀，否则这样的程序大概无法通过本题）。

当然你可能想要一个更快的做法，或者出题人真的卡了时限导致“暴力进位”的做法过不去。

提醒一下，输出优化可以减少约 0.1s 的用时。（我自己提供的程序中，包含后缀 fastout 的程序都使用了输出优化）

确实也有一个快一点的暴力。它是由之前的搜索优化而来。之前我们在求 $K_1\left(n\right)$ 时，我们将所有可分支的 $a_i$ 都赋值为 $0$，它只有 $O\left(\sqrt{k}\right)$ 的时间开销，但无法枚举到足够多的情况。而搜索的时候，我们分别递归地搜索了 $a_i = 0$ 及 $a_i = i$ 的情况，它能枚举到每一种情况，但时间开销过大。取一个折中的方法，我们在从后往前枚举 $i$ 时，每次碰到一个可分支的 $a_i$，先假设 $\left(n+k\right)$ 次操作对应的序列中 $a_i = 0$，然后从 $\left(i-1\right)$ 开始往前枚举 $j$，构造 $a_i=0$ 的所有序列中操作次数最大的那个（它是唯一满足所有 $a_j \ne 0$ 的那一个），并判断它的操作次数是否不超过 $\left(n+k\right)$。如果是，则可以令 $a_i=0$，否则 $a_i = i$；之后再往前找下一个可分支的 $a_i$。这一做法的复杂度与枚举时碰到的可分支的 $a_i$ 的下标之和有关，我并不会估计这个值，但它并不会特别大。我的 bin.cpp 采用了这个做法，它比之前的 force.cpp 快了 0.1s。

但是这个做法还是不够快。另外还有一个从前往后推的做法，它利用了我们之前分析 force.cpp 的复杂度时用到的思想。我们知道，对于 $a_i$ 而言，如果 $a_{i+1}, \cdots, a_n$ 一共操作了 $\kappa_i$ 次，那么 $a_i$ 的操作次数 $\delta_i \approx \frac{\kappa_i}{i}$。对于 $a_1$ 而言，它操作的次数 $\delta_1 = a_1 + \kappa_1$，而 $n+k=\delta_1 + \kappa _1 = a_1 + 2\kappa_1$，其中 $a_1 \in \left\{0, 1\right\}$。那么 $a_1 = \left(n+k\right) \bmod 2, \kappa_1 = \left\lfloor\frac{n+k}{2}\right\rfloor$。我们可以继续往下推：对于 $a_i$ 而言，它之后的所有 $a_j$ 会给它加上 $\kappa_i$，而每操作一次 $a_i$ 需要消耗 $i$，故 $i\delta_i = a_i + \kappa_i$，$\kappa_{i-1} = \delta_i + \kappa_i = \frac{a_i + \kappa_i}{i} + \kappa_i$，整理得 $a_i + \left(i+1\right) \kappa_i = i\kappa_{i-1}$，从而 $a_i = i\kappa_{i-1} \bmod \left(i+1\right), \kappa_i = \frac{i\kappa_{i-1}}{i+1}$。这样我们就可以从 $a_1$ 推到 $a_n$，它的复杂度是 $O\left(n\right) = O\left(\sqrt{k}\right)$ 的。

这个做法我写在了 forward.cpp 里，但它仅比 bin.cpp 快一点点（大约是 0.04s 左右）。这暗示我们，算法的瓶颈还是在之前的二分中。

改进二分的方法有很多。例如，如果你发现了 $n = O\left(\sqrt{k}\right)$（或者你猜它可能有这种关系），你可能会想用一个二次函数去拟合 $n$ 与 $k$ 的关系。这个做法会让你很快地接近你需要的 $n$，因为它确实存在一个平方的关系。或者你比较擅长找规律，并且试着计算了一些 $\frac{k}{n^2}$ 的值，你会发现它约等于 $0.3183$。如果你对各种常见的数字比较敏感（实话说我没有这么敏感），你会发现它基本上就是 $\frac{1}{\pi}$；或者你直接计算了 $\frac{n^2}{k}$，那就可以明显看出它比较接近 $\pi$。而事实上，这个规律确实成立（参见 E.Space 题解中的那篇论文）。如果你对这个结论不放心，你可以在 $\left[\sqrt{\pi k} - 100, \sqrt{\pi k} + 100\right]$ 或者更小一点的范围内二分，这会大大减小二分的用时（大约只有原来的一半，以 pi 开头的代码都是如此）。在本机测试的结果显示，即使只是在 $\pm 100$ 的范围内二分也能比较轻松地通过本题（甚至即使出题人卡了时限），这一改进对我们程序用时的提升是显著的。

所以 A 掉这道题需要什么呢？我想是一些冷静分析的技能，大胆猜测的勇气，以及足够好的运气（特别是当你没有前两者的时候）。