本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-10-08 11:20:00

:::::info[题目基本信息] 考察：构造（$3000$）。
题目简述：
$T$ 组数据，每组数据给定 $n$，有一序列 $\{a_n\}$，初始时 $\forall i\in[1,n],a_i=i$，你可以进行下面操作若干次：

• 选定 $x,y$ 满足 $x,y\in[1,n]$ 且 $x\ne y$，同时进行操作 $a_x\leftarrow a_x+a_y$ 和 $a_y\leftarrow|a_x-a_y|$。

你想让 $\{a_n\}$ 中的元素都为一个数，在此基础上你想让这个数最小，在此基础上你想让操作数不超过 $20n$，问是否有解，若有解构造方案。
数据范围：

• $1\le T\le 25000$
• $2\le n\le 5\times 10^4$
• $\sum n\le 5\times 10^4$ ::::: :::::info[闲话] 神秘构造题。
  本题中所有结论均可使用打表发现。
  ::::: 结论 1：若有解，则最后序列中含有的唯一一个数为 $2^{\lceil\log_2 n\rceil}$。 :::::success[证明] 先把这个结论拆成答案上界和下界均为 $2^{\lceil\log_2 n\rceil}$ 证明。
  对于答案上界，可以直接构造证明，如何构造就留在后面，所以我们先证明答案下界。
  结论 1.1：最终的数一定不是奇素数的倍数。
  ::::success[证明] 考虑反证法。
  设一奇素数为 $P$。
  若对 $a_x,a_y$ 进行操作，设 $p=a_x\bmod P,q=a_y\bmod P$，则 $(a_x+a_y)\bmod P=(p+q)\bmod P,|a_x-a_y|\bmod P=|p-q|\bmod P$，如果我们想让最后的数是奇素数的倍数，那么我们需要在 $p\ne 0\lor q\ne 0$ 的条件下凭空制造出 $(p+q)\bmod P=|p-q|\bmod P=0$，同时由于 $p,q\in[0,P)\cap\mathbb N$，那么我们得到：
  $$(p+q)\bmod P=0\Rightarrow p=q=0\lor p+q=P\Rightarrow p+q=P$$ $$|p-q|\bmod P=0\Rightarrow p=q$$ 解得 $p=q=\dfrac{P}{2}\notin \mathbb N$，产生矛盾。
  证毕。
  :::: 最后的数不是奇素数的倍数，那么它一定能被表示为 $2^k$（$k\in \mathbb N$）。
  由于操作 $a_x,a_y$ 会产生一个更大的数 $a_x+a_y$，所以答案下界就是 $2^{\lceil\log_2 n\rceil}$。
  答案下界证毕。
  ::::: 现在我们要构造方案，注意到操作两个数 $0,x$ 能变成 $x,x$，再操作一次 $0,2x$，所以我们在序列有 $0$ 时能够将任意一个数乘 $2$，所以我们考虑将这些数全部操作成 $2$ 的非负整数次幂，比较容易想到具体过程：
  以序列 $\{a_{10}\}=\{1,2,3,4,5,6,7,8,9,10\}$ 为例：
• 若 $n$ 自身就是 $2$ 的非负整数次幂那么我们就递归大小为 $n-1$ 的子问题，但是这里 $10$ 不是 $2$ 的非负整数次幂，要继续往下走。
• 先取 $pos=2^{\lfloor\log_2 n\rfloor}=8$，在 $pos$ 左右对称取数操作，变成 $\{1,2,3,4,5,\color{red}4\color{black},\color{blue}2\color{black},8,\color{blue}16\color{black},\color{red}16\color{black}\}$。
• 观察发现子序列 $\{1,2,3,4,5\}$ 是一个更小的子问题，子序列 $\{4,2\}$ 整体除以 $2$ 后也是一个子问题，递归处理，当序列长度不超过 $2$ 时停止递归，因为已经合法。
• 最终，序列变为 $\{1,2,2,4,8,4,2,8,16,16\}$，操作次数为 $3$ 次。

然后我们考虑选择两个相同的数操作 $1$ 次得到 $0$，但是注意，这两个数不能等于 $2^{\lceil\log_2 n\rceil}$。
结论 2：当 $n\ne 2$ 时，一定能得到一个 $0$（下文简称序列合法）。
:::::success[证明] 首先当 $n$ 是 $2$ 的非负整数次幂时，长度为 $n$ 的序列合法当且仅当长度为 $n-1$ 的序列合法。
然后一个长度为 $n$（$n$ 不是 $2$ 的非负整数次幂，下同）的序列，操作一次后会产生 $n-pos$ 个 $2^{\lceil\log_2 n\rceil}$，且由于向下的两个递归长度一定小于 $pos$，所以不会再产生 $2^{\lceil\log_2 n\rceil}$，所以最后一共会有 $n-pos$ 个 $2^{\lceil\log_2 n\rceil}$，所以有 $pos$ 个不是 $2^{\lceil\log_2 n\rceil}$，在 $\lfloor\log_2 n\rfloor+1<pos$ 时序列一定合法，令 $t=\lfloor\log_2 n\rfloor\in\mathbb Z$，解不等式：
$$\lfloor\log_2 n\rfloor+1<pos\\Leftrightarrow\lfloor\log_2n\rfloor+1<2^{\lfloor\log_2n\rfloor}\\Leftrightarrow t+1<2^t\\Leftrightarrow t\ge 2\\Leftrightarrow n\ge 4$$ 接下来对 $n=2,3$ 时进行检验（CF 还怪良心，样例就是这两个），发现 $n=2$ 不合法，$n=3$ 合法。
证毕。
::::: 所以我们直接 $\Theta(n)$（可能由于实现方式导致 $\Theta(n\log n)$，但是肯定远远跑不满）找到相同的数构造出一个 $0$，然后让其它数暴力乘 $2$，最后还原 $0$ 即可。
此时，构造数无论是递归部分还是暴力乘 $2$ 部分显然都是 $\Theta(n\log n)$ 级别，但是两者都远远跑不满，实测在 $n=5\times 10^4$ 时操作数约为 $2.1\times 10^5$，虽然此时的操作数比序列长度不是最大的，但是可以看出即使最大时也并不大，通过暴力计算发现该比值最大为 $6.76$。
然后做完了。
时间复杂度为 $\Theta(n\log n)$（如果实现较劣可能变成 $\Theta(n\log^2 n)$），空间复杂度为 $\Theta(n)$。