P9930 [NFLSPC #6] 1064 病毒

Iniaugoty · 2023-12-16 22:20:27 · 题解

感觉挺诈骗的一道题。

你发现答案可能极大，但是南夫拉斯又不大可能出高精度。

于是你猜想这个 10 ^ {10 ^ 5} 可能是假的，或者所有 f _ k (i) 都相同或类似，使得答案是一个可以处理的数后面跟上一串 0。

于是你手模了一下 0 \sim 20 和几个大数。

于是你发现迭代数次之后他们都得到了 213。

于是你猜想所有 f _ k (i) 都是 213。

于是你写了一份代码，输出了 213 和 n 个 0。

于是你获得了 0 分。

于是你继续观察，发现当 k = 1 时（n 只能为 0）答案是 11，似乎只有这个不符合你的猜想。

于是你加了一个特判。

于是你通过了。

上面是我乱搞过题的过程，接下来我将给出解释。

当 0 \le n < 10 ^ 9，显然 \vert g(n') \vert = 3。

当 10 ^ 9 \le n < 10 ^ {16}，显然 \vert g(n') \vert \le 6，那么 \vert g(g(n')) \vert = 3。

当 10 ^ {16} \le n < 10 ^ {10 ^ 5}，显然 \vert g(n') \vert \le 16，那么 \vert g(g(n')) \vert \le 6，进而 \vert g(g(g(n'))) \vert = 3。

如果 \vert g(x) \vert = 3，g(x) 一定可以通过迭代得到 213。对 g 每一位的奇偶性分类讨论（因为前两位之和是第三位，所以只有两种情况）：

• 奇偶奇/偶奇奇/奇奇偶：显然迭代 1 次就是 213 了。

• 偶偶偶：迭代 1 次是 033，再 1 次就是 213。

对于 n = 0，需要迭代 2 次达到 213，所以 k = 1 时答案为 11，否则 213。

对于 0 < n < 10，由于迭代 1 次之后最后一位必为奇数，符合第一种情况，只需再迭代 1 次。而由题意这一部分一定有 k \ge 2，所以一定是 213。

对于 10 \le n < 10 ^ 9，需迭代至多 3 次，而这里有 k \ge 3，必为 213。

对于 10 ^ 9 \le n < 10 ^ {16}，需迭代至多 4 次，而这里有 k \ge 10，必为 213。

对于 10 ^ {16} \le n \le 10 ^ {10 ^ 5}，需迭代至多 5 次，而这里有 k \ge 17，必为 213。

综上，k = 1 时答案为 11，否则为 213 \times 10 ^ n。

代码很简单，不贴了。