CF1637G Birthday 题解

zrl123456 · 2025-10-08 11:20:00 · 题解

:::::info[题目基本信息] 考察：构造（3000）。
题目简述：

- 选定 $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)。