题解：P12695 序列游戏

· · 题解

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

做题顺序：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