P12417 解题报告

· · 题解

前言

好玩构造题。

摘自交互、构造、博弈。

后记：根本没想到这么能优化，目前流程是 392960\rightarrow295554\rightarrow14855\rightarrow3577\rightarrow2050\rightarrow2047，应该是全流程了。

思路分析

没有很多思路，那就先随便手玩看看性质。

看一眼样例发现 2,4 的情况的构造很规整，好像比较容易推出 2^n 如何构造。

对于 2^n 的情况，我们考虑先构造出两块 2^{n-1} 个相等的数，然后再将这两块对应位置的数用操作合并即可。

这样不断递归的做就可以做出序列长度为 2^n 的情况。

那对于非 2 的幂次的情况呢？难道都是无解吗？

考虑到我们每次操作是合并两个数让两个数变为相同的值，所以奇数看起来貌似很不行的样子？

那么就来尝试证明下奇数是不可行的（下列思路启发来自于出题人，猫猫想了半天差一步）。

其实我们只需要令 a_i 为第 i 个质数，那么如果给出的方案可以使这样的 a 序列满足条件，就一定是都满足条件的。

这点不难理解，因为在这个限制条件下对于一项 a_i，并不能用其他的项凑出来，也就是其是唯一的。

为了证明 n 为奇数不可行，我们考虑找到一个当 n 为奇数时并不满足的必要不充分的条件。

考虑到最后的数是都相同的，也就是说最大值出现了 n 次，接着就是尝试证明最大值的出现次数不可能为奇数。

在未操作前最大值出现次数为 1 次恰为奇数，这是一个极端的边界，我们先给这部分搞掉。

因为 n\ge3，以及 a_n 不可能用其他数凑出来和他相等，所以总有一步你是要操作到 a_n 或是通过操作别的数得到比 a_n 更大的值。

或者说在可能的操作过程中，最大值总会在某一时刻被一个操作更新，而不可能一直是 a_n。

所以在这一步操作完之后，操作的两个数都变成了最大值，此时的最大值出现次数是偶数次。

接下来影响最大值的操作大概有如下三种：

  1. 我们操作产生了更大的值，此时出现次数回到 2。
  2. 我们操作产生了当前最大值，此时出现次数增加 2 次，仍然为偶数。
  3. 我们操作了当前最大值和另一个数，此时操作出来的值一定比当前最大值更大，出现次数回到 2。

所以综合上述情况，我们知道最大值的出现次数肯定是偶数次。

也就是说 n 为奇数的情况一定是不可行的。

接下来我们尝试来构造 n 为偶数的情况。

构造是怎么样的一个过程？

肯定是将 n 划分为两个数 x,y，然后构造出 x 个相同的数，构造出 y 个相同的数，再将这两个情况合并在一起。

这是一个分割子问题的思想。

根据前面的证明我们知道 x,y 肯定是偶数。

构造而言不妨来考虑一些极端的情况，我们直接令 y=2，相当于是尝试往 x 个相同的数后面拼上 2 个数。

设这相同的数分别为 a,b，当前序列即为：

\underbrace{a,a,\dots,a}_{x},b,b

考虑到最后合并完后是一定有 b 存在的，而 b 只有两个，必然是要围绕着 b 去一直操作先让 b 在前面 x 个数中都出现的。

这样想还是太困难了，让我们先来试试 x=2 的情况。

此时序列为：

a,a,b,b

我们的构造方式为 1,3 操作 2,4 操作，即可变为：

ab,ab,ab,ab

然后推广一下来考虑 x=4 的情况。

此时序列为：

a,a,a,a,b,b

第一步操作肯定是操作一个 a 一个 b（不然都是和原序列本质相同的无意义的）。

那么我们得到：

ab,a,a,a,ab,b

这时 3,4 位置上的 a 可以考虑用 x=2 时的方法搞掉，还需要变动的是 2 号位置。

因为最后的操作是 3,5 和 4,6，会使最后 4 个数都相同，所以我们想要让 1,2 操作后的 1,2 也能和后面的数相同。

那就需要让 1 的 a 的次数加上 2 的 a 的次数等于 3 的 a 的次数加上 5 的 a 的次数。

对于 b 也同理要满足这点。

注意到什么？

注意到当前情况下 1,3 的 a 的次数是相同的，所以进行一次 2,5 操作，就可以让 5 上 a 的次数和 2 相同。

当前序列即为：

ab,a^2b,a,a,a^2b,b

接下来我们让 5,6 相等，再套用 x=2 的操作，变化步骤即为：

ab,a^2b,a,a,a^2b^2,a^2b^2 ab,a^2b,a^3b^2,a,a^3b^2,a^2b^2 ab,a^2b,a^3b^2,a^3b^2,a^3b^2,a^3b^2

不难发现，在我们的精心构造下此时刚好满足了 1,2 操作后和剩下四个数都相同，a,b 的次数都恰好满足。

这下构造方案就呼之欲出了，我们考虑对于一般的情况。

构造一个 a 的次数等差的一个序列，这样我们可以通过首尾操作的方法让 a 的次数都变得相同。

具体的，考虑对于序列：

\underbrace{a,a,\dots,a}_{x},b,b

我们先进行操作 i,x+i(i\le x-2)，那么序列就变成了：

\underbrace{ab,a^2b,\dots,a^{x-2}b,a,a}_{x},a^{x-2}b,b

然后我们套用 x=2 的构造：

\underbrace{ab,a^2b,\dots,a^{x-2}b,a,a}_{x},a^{x-2}b^2,a^{x-2}b^2 \underbrace{ab,a^2b,\dots,a^{x-2}b,a^{x-1}b^2,a}_{x},a^{x-1}b^2,a^{x-2}b^2 \underbrace{ab,a^2b,\dots,a^{x-2}b,a^{x-1}b^2,a^{x-1}b^2}_{x},a^{x-1}b^2,a^{x-1}b^2

最后我们进行操作 i,x-1-i(i\le\frac{x-2}{2})。

也就是将 a 的次数为 i 次的和为 x-i-1 次的拼在一次，恰好得到 a^{x-1}b^2。

这样我们最后就得到了 \underbrace{a^{x-1}b^2,\dots,a^{x-1}b^2}_{x+2}，完成了 x 个和 2 个的合并。

于是我们就完成了这题。

猫猫的代码（392960 次）。

update（小优化）

由于题目修改了计分方式，把次数限制从 5\times10^5 改为了 3\times10^5，所以更新一下构造方案。

先算一下上面那种情况我们的构造方案。

我们是枚举了左端长度 x，然后每次合并一个 2 进来花费的步数是 1+x-2+3+\frac{x-2}{2}=\frac{3x}{2}+1。

总的步数也就是 \sum\limits_{i=1}^{\frac{n}{2}} 3i-2（请注意这里加上了最开始的第一步整体平移了一下重写了式子，所以是 3i-2 不是 3i+1）。

这是一个简单的等差数列求和，拆开可以得到为 \frac{3n^2-2n}{8}。

代入极限数据 n=1024 可以得到操作次数为 392960，直接被卡爆了。

所以我们来考虑优化。

不难发现其实这个次数相差也不是特别多，所以随便加点小优化就能过了（笔者也不知道还能不能再优化了，目前是就想了 5 分钟搓出来的）。

我们考虑到前面最大的浪费是在什么地方？

就是说比如我们想要让 256 个数字都变相等，选择了 2 个 2 个的加，这也太浪费了。

考虑到最初我们写过一个 2^n 的处理方法，这个次数显然少的多了。

直接把这个 2^n 的做法套上来先把这部分搞掉就可以做到优化很多步数了。

算一下大概是多少步。

在卡满的极限数据下，我们把最初的 512 个数合并的这一步跳过了，也就是节约了 98176 步，并用 2304 步完成了这个部分。

再加上卡满的极限次数实际上是 n=1022，所以最后的次数来到 391426-98176+2304=295554 步，极限压过去。

猫猫的代码（295554 次）。

update（O(n\log n) 做法）

目前我们有哪些操作手段，只有末尾增加 2 个数这种操作吗？

考虑溯源。

在这题的最开始，我们想到的 2^n 做法中，可以用 m 次实现两段长为 m 的相同的数的合并。

这个操作是非常优秀的，设 f_n 表示长为 2^n 的序列需要的合并次数，可以得到 f_{i}=2f_{i-1}+2^{i-1}。

最后求一个通项可以得到 f_n=2^{n-1}n，也就是 O(n\log n) 级别。

如何推广这个合并操作呢？

我们尝试尽可能的将原本的序列均分，把分割出的两部分都搞成相同后再用上述的合并操作，最后再修改末尾可能需要加上的 2 个数，就可以得到一个更为优秀的做法。

这时我们需要考虑怎样分割序列最为优秀了。

具体的，对于一个长度为 i 的序列，我们可以取掉最后的 j 个数先不管，把前面的 i-j 个数均分为两半，操作完合并后再把最后的 j 个数合并进来。

设长为 n 的序列答案为 f_i，转移式即为：

f_i=\min\limits_{j=0}^i 2f_{\frac{i-j}{2}}+h(i)-h(i-j)+\frac{i-j}{2}

其中 h(n)=\frac{3n^2-2n}{8}，即为上面做法中只使用合并末尾两个数做法的代价。

感性理解/直接跑 dp 打表/拆开 h(i) 配方取最小值等方法，都可以得到当 i\equiv0\pmod4 时，取 j=0 最优，否则取 j=2 最优。

此时的操作次数可以跑一遍 dp 算一下，在 n=1022 时取最大值为 14855 次，已经做到了 O(n\log n)，是一个比较重大的飞跃了。

猫猫的代码（14855 次）。

update（\frac{7}{2}n-7 做法）

我们考虑到前面的合并操作递归调用的话，$\log$ 在这是跑不了的。 而末尾加 $2$ 的操作就更劣了，每次都是 $O(n)$ 的。 所以我们考虑能否先线性构造出 $n-2$，最后再用一次加 $2$ 操作，这样就可以把复杂度控制在 $O(n)$。 那么如何快速构造 $n-2$ 个相同的数？ 我们设最开始的序列为 $a_1,a_2,\dots,a_n$ 这样。 那么最后的序列得到的唯一的数肯定可以写做 $\prod\limits_{i=1}^n a_i^{b_i}$ 的形式，其中 $\forall i\in[1,n],b_i\ge1$。 我们有一个想法是，先把 $1$ 和其他的所有数都操作一遍，这样就可以得到 $\prod\limits_{i=1}^n a_i,\prod\limits_{i=1}^2 a_i,\prod\limits_{i=1}^3 a_i,\dots,\prod\limits_{i=1}^n a_i$ 的一个序列。 但这样接下来就没法做了。 所以我们考虑类似于前面末尾加 $2$ 的想法灵感，尝试构建一个次数等差的序列。 也就是说，我们尝试让由 $i$ 个数乘起来得到的数和由 $n-i$ 个数乘起来得到的数配对，这样给他们两两乘一下就可以都变成 $\prod\limits_{i=1}^n a_i$。 现在的问题就是如何让他们刚好不重不漏。 不难发现我们前面的那个想法大概是一个前缀的状物，为了与他互补，我们尝试构建一个后缀状物。 或者说，我们先以 $\frac{n}{2}$ 为断点，将序列划分为长度相同的两段。 对于前面一段我们前缀相邻操作，对于后面一段我们后缀相邻操作，就可以得到： $$\prod\limits_{i=1}^2 a_i,\prod\limits_{i=1}^3 a_i,\dots,\prod\limits_{i=1}^{\frac{n}{2}} a_i,\prod\limits_{i=\frac{n}{2}+1}^n a_i,\dots,\prod\limits_{i=n-2}^n a_i,\prod\limits_{i=n-1}^n a_i$$ 这样的一个序列。 但这样前后还是不互补的，该怎么办呢？ 可以发现的是，对于前面一半的一个位置 $i$，和后面的一个倒着对应的位置乘起来后缺少的因子，刚好就是在后一半对应的前 $i+1$ 个数。 所以我们先把 $i,i+\frac{n}{2}(1\le i\le\frac{n}{2})$ 先操作了，就能保证互补。 这样之后再进行上面的前后缀操作，最后再操作一下 $i,i+\frac{n}{2}+3(1\le i\le\frac{n}{2}-3)$ 就可以使其互补了。 这样刚好可以构造出 $n-2$ 个 $\prod\limits_{i=1}^n a_i$。 还没构造出来的两个不同的位置就是 $\frac{n}{2}-2$ 和 $\frac{n}{2}+3$。 我们套用上面的末尾加两个数的做法即可。 这样的总代价是 $h(n)-h(n-2)+\frac{n}{2}+2(\frac{n}{2}-1)+\frac{n}{2}-3=\frac{7}{2}n-7$，已经来到线性。 [猫猫的代码（3577 次）](https://www.luogu.com.cn/paste/5ey6b192)。 ### update（$2n+2\sim 2n-1$ 做法） 其实 $2n+2$ 做法还是比较好想的。 考虑 $3577$ 次操作的时候，最浪费操作步数的还是末尾的加 $2$ 操作。 那为什么最后面的两个数不能用类似的构造只能用加 $2$ 操作呢？ 因为他们的次数都是 $n-2$ 次，已然没有次数为 $2$ 次的数来和他们调平了。 所以思路就有了，我们考虑先保留 $n-1,n$ 这两个数用来补足最后出现的 $n-2$ 次的数。 但这里就有一个问题，由于最后两个 $n-2$ 次的数他所需要的两个因子分别是 $a_1a_{\frac{n}{2}}$ 与 $a_{\frac{n}{2}-1}a_{n-2}$，所以我们需要保证 $a_{n-1},a_n$ 可补足这两个因子，即需要保证他们都相等。 使用一次 $n=6$ 的 $11$ 次操作先钦定这些数都相等，就可以做到 $11+\frac{n}{2}-3+2(\frac{n}{2}-2)+\frac{n}{2}-4+2=2n+2$。 注意这里的第二部分中的 $-3$，是因为在 $3577$ 次的做法中，我们的操作是 $\forall i\in[1,\frac{n}{2}],(i,i+\frac{n}{2})$，而在这里我们保证了相等后，就不需要操作左右两个边界了，省下来两次。 [猫猫的代码（2050 次）](https://www.luogu.com.cn/paste/zextcbnf)。 接下来就是最后的一步优化了，这个优化就比较显然了。 我们发现还是有浪费啊，到底是在哪里浪费了呢？ 注意到我们需要的是让 $a_{n-1},a_{1},a_{\frac{n}{2}}$ 相等，以及 $a_{n},a_{\frac{n}{2}-1},a_{n-2}$ 相等，并不需要让这六个数都相等。 这意味着什么，我们可以把一次 $n=6$ 的操作拆开，拆成两个 $n=3$ 的操作。 但是 $n=3$ 的时候是不可构造的，所以我们要令 $n=4$ 去构造，不妨把 $a_3,a_4$ 也拿过来，这样就刚好 $4$ 个一组可以调用 $n=4$ 时的操作了。 通过这样的方法我们可以把原来的 $11$ 次操作换成 $4+4=8$ 次操作，也就是抠出来了 $3$ 次操作，最后刚好 $2n-1$ 次操作，可以通过本题。 写代码的时候注意一下如果 $a_{n-1}$ 是和 $a_{\frac{n}{2}-3}$ 调平的话，他需要的因子是 $a_{\frac{n}{2}-1}a_{n-2}$，恰好是反过来的。 [猫猫的代码（2047 次）](https://www.luogu.com.cn/paste/9z29mq02)。 至此，我们完成了这题。 回顾一下整题的流程，我们刻画了 $2^n$ 时的合并操作，构造了末尾加 $2$ 的一般性操作，围绕着次数等差数列展开思考，通过调平配出了线性做法，尝试了一切可能的切入点最后完成这题，是非常好的构造练习题了。