P9897题解
ydzr00000
·
·
题解
题面
令 f(x) 表示 x 中各个数位上的数字的封闭部分的数量，再令 g^0(x)=x，对于 k\ge 1 满足 g^k(x)=f(g^{k-1}(x))，给定 T 组 x,k，试求 g^k(x)。
### 题解
首先让我们考虑 $g^1(x)$ 的值，因为 $8$ 的封闭部分最多（有 $2$ 个），所以 $g^1(x)$ 在 $x=888,888,888$ 时取到最大值，为 $18$。
再考虑 $g^2(x)$ 的值，因为 $0\leq g^1(x)\leq 18$，计算所有可能的 $g^2(x)$，可以发现 $0\leq g^2(x)\leq 2$。
再类推一次，可以得到 $0\leq g^3(x)\leq 1$。
在 $k\ge 3$ 的时候，$g^k(x)$ 不等于 $0$ 就会等于 $1$，事实上，可以发现之后的部分为 $0,1$ 交替的循环，因为 $f(0)=1,f(1)=0$。
于是最多循环 $3$ 次，若 $k\ge 3$ 的时候判断最后的值是 $0$ 还是 $1$ 即可。
我们可以认为暴力计算 $f(x)$ 的时间复杂度是 $\log_{10}x$，于是最终时间复杂度为 $\mathcal{O}(T\log_{10}x)$。
**注意一下 $f(0)=1$，一些写法可能使得 $f(0)=0$。**