题解 P5246 【[集训队互测 2016] 消失的源代码】

· · 题解

大概自己做出了一半左右，写篇题解来记录下。

subtask1

发现整个过程跟字符串加密差不多，一个个打表可以发现是这样一种对应关系：

string str = "yfrbkgimujvphatdsnelozcxwq";

把输入的一位位替换就行了。

subtask2

打出前 10 位的表，找不到规律，那就差分。还是找不到规律，再差分，发现得到的结果都是 4032。

猜想答案是关于 n 的多项式，有 2016n(n-1) 这一项，进而解得 f(n) =2016n(n-1) + 2020n+10。

当然你也可以拉格朗日插值硬搞。

然后发现第 11 项比 f(11) 要小 233333，于是猜测模数就是 233333 验证一下发现是对的。

subtask3

比较神秘。

打表打出前 30 项，扔进 oeis 里，他会告诉你输出 \sqrt{\dfrac{n}{\pi}} 的整数部分。

subtask4

接下来这 3 个比较简单。

通过小数据测试发现答案是图上连通块大小的平方和。

subtask5

观察输入发现大概是这样的。

通过 $m=1$ 的尝试发现节点距离为路径上的边权和。扩大 $m$ 发现要把 $m$ 次的结果异或起来输出。 ## subtask6 跟上面一个差不多，节点距离为路径上的边权最小值。 然后有一个很恶心的地方就是自己跟自己的距离是 $1987654321$。 ## subtask7 打出 $10 \times 10$ 的表，每行 oeis 无果，发现输入大多是 $n=m$ 就把对角线上的数扔进 oeis，发现是在求 $\sum\limits_{i=1}^n\sum\limits_{j=1}^m gcd(i,j)$。 代码参考 [P1390](https://www.luogu.com.cn/problem/P1390)。 ## subtask8 不会做，是让你求不同子串个数。 代码参考 [P2408](https://www.luogu.com.cn/problem/P2408)。 ## subtask9 输入了一堆二元组，经过小样例的不断尝试发现是求平面最近点对。 代码参考 [P1429](https://www.luogu.com.cn/problem/P1429)。 ## subtask10 因为我在写的时候没做出来的点都用 `invalid input!` 占位，然后发现过了。 那么就是输出 $10$ 个 `invalid input!`。