自动搬运

查看原文

来自洛谷，原作者为

	WorldMachine 请引领我至夜晚熠熠闪烁的群星之下

搬运于2025-08-24 23:17:29，当前版本为作者最后更新于2025-06-04 21:51:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

几个人一起做的，贡献了一个多项式板子和部分分数。

做题顺序：1 2 3 4 5 6 7 9 11 16 19 20 10 15 14 13 12 8 17 18。

$1\sim5$ Binary

这几个点的输出都是 $n$ 个整数。

随便输入几个数据，发现答案的第 $i$ 位只和 $a_i,b_i$ 有关。猜几个常见的二元运算，很容易发现这五个点对应的二元运算分别为 $+,-,\text{xor},\text{or},\text{and}$。

$6$ Multiply

本来想着会不会有多项式操作，结果还真有啊。

输出 $2n-1$ 个数，发现答案就是序列 $a$ 和 $b$ 的卷积。将 $a$ 和 $b$ 当成两个多项式乘起来输出就行了，注意下标从 $0$ 开始，要写 NTT。

还有一个问题是模数取多少，猜测是 $998244353$，然后就对了。

$7$ Inverse

输出 $2n$ 个数，看起来毫无头绪啊。但由于 prog.exe 要求了 $b_0=1$，猜测大概是 $\text{inv}$ 或者 $\ln$ 这类东西。

固定 $b_0=1$，其它都为 $0$，发现得到的多项式就是 $a$ 本身；固定 $a_0=1$，其它都为 $0$，发现得到的多项式就是 $b$ 的乘法逆。再多试几个，猜测答案为 $a\cdot b^{-1}$，就过了。

注意次数要补到 $2n-1$。

$8$ Cbrt

输出 $2n$ 个数。

随便试几组数据，发现答案和 $b$ 无关。

尝试 $1-x$，得到了一列以 A004117 为分子，以 A067623 为分母的数（当然是在模 $998244353$ 意义下给出的，原数得自己猜），也就是 $\sqrt[3]{1-x}$。猜测需要多项式开立方根。

做法就是把 $a$ 做多项式 $\ln$ 之后每一项乘上 $\dfrac13$ 再 $\exp$ 回去，虽然 $\exp$ 常数不轻但还是能过的。

还是要注意次数要补到 $2n-1$。

$9$ Compound

输出 $n$ 个数。

发现 $a$ 和 $b$ 都是排列。尝试 $b_i=i$，发现答案就是 $a$ 本身；尝试 $b_i=n-i+1$，发现答案是 $a$ 翻转后的结果。那么答案就是输出 $a_{b_i}$。

$10\sim11$ Sort

输出 $n$ 个数。

首先发现答案和 $b$ 无关，并且 $a$ 现在不一定是排列了。

先说第 $10$ 个点。尝试 $a$ 为排列的情况，发现第 $i$ 位就是数 $i$ 在 $a$ 中出现的位置。

猜测按 $a_i$ 为第一关键字、$i$ 为第二关键字排序，答案的第 $i$ 位就是排序后第 $i$ 小的数在原序列中的下标。

对于第 $11$ 个点，发现其答案就是第 $10$ 个点的答案的排列的逆。

$12$ Order

输出 $1$ 个数。

答案还是和 $b$ 无关，先尝试 $a$ 为排列的情况。

对 $n=5$ 的所有排列打一个表，答案为 $1\sim 6$ 的排列个数分别为 $1,25,20,30,24,20$，即 A057731 的第五行。

因此所求即为输入置换的阶，即每个轮换大小的 $\text{lcm}$。

首先，当输入数据不是一个排列的时候，需要将其按 $a_i$ 为第一关键字、$i$ 为第二关键字离散化成排列再做。

其次，答案可能很大，是 $\mathcal O\left(e^{\sqrt{n\ln n}}\right)$ 级别的（见此），所以要么取模，要么需要高精度。试了几个模数都不对，那就是不取模了。

不想写高精度怎么办？注意到这是一道提交答案题，那就把每个轮换大小输出出来，再丢到 python 里求 $\text{lcm}$ 即可。随机置换的轮换个数期望是调和级数的，可以接受。

$13$ Distance

输出一个两位小数。

首先尝试 $n=2$ 的情况，发现就是以 $a$ 为横坐标、以 $b$ 为纵坐标的两个点的距离。

尝试 $n$ 更大的情况，可以发现答案就是编号相邻的每对点的距离之和。

$14$ Variance

输出一个两位小数。

首先观察到答案只和 $a_i-b_i$ 有关，并且所有数乘以 $k$ 后，答案乘以 $k^2$；所有 $a_i$ 加上 $k$ 后，答案不变。

具有如上性质的东西在统计学中比比皆是，猜测是总体方差，然后就过了。

$15$ Linear

输出格式很神奇，给出了 $k$ 和 $b$ 两个两位小数，那应该是一个一次函数。

那么猜测输入给出的应该是平面直角坐标系上的 $n$ 个点，自然想到线性回归，使用最小二乘法求解即可。

$16$ Matrix

输出一个 $01$ 矩阵。

令 $b$ 全为 $0$，发现只输出一列，从 $a$ 中最小值到最大值，如果一个值在 $a$ 中出现过则为 $1$，否则为 $0$。

考虑一般情况，会输出一个矩阵，每一行从 $b$ 中最小值到最大值，对于 $(i,j)$，如果存在一个 $k$ 使得 $a_k=i,b_k=j$，那么该位置就为 $1$，否则为 $0$。

$17$ Area

输出一个两位小数。

根据前面的经验，给出的应该还是平面上的 $n$ 个点。

对于 $n=2$，不管怎样输出都为 $0$。对于 $n=3$，发现答案刚好为这三个点围成的三角形面积。

猜想和面积有关，但这 $n$ 个点按照给出顺序甚至不一定能围成一个简单多边形，猜测答案为这 $n$ 个点的凸包的面积，用 Andrew 算法求解即可。

$18$ Sqrt

输出 $2n$ 个数。

还是多项式题，答案和 $b$ 无关。

观察前几项可以发现答案的平方恰好为 $a$，多项式开根即可。

还是要注意次数要补到 $2n-1$。

$19$ Nim

输出 Win! 或者 Lose!。

猜想和博弈论有关，比如 Nim 博弈。因为答案和 $a,b$ 都有关，猜测是把 $a,b$ 中的每个数异或起来，如果不为 $0$ 则输出 Win!，否则输出 Lose!。

还有一种做法，因为输出要么是 Win! 要么是 Lose!，尝试最多两次即可。

$20$ Easy

输出 $2n$ 个数。

发现把两个序列拼接起来就是答案。

完整代码见此。

123asdf123 Enoch006 流水行船CCD Orz Orz Orz