求 $\log$ 部分。下面 $n\gets \log_{10} n\le 10^5$

先说正解，就是用 $\lfloor\log _{10}\rfloor\times C$ 估计 $\log_{10}$，其中 $C\sim \log _2 10$。

然后累加做快速幂判断。此时 $\ln-\exp$ 做法不行，于是预处理 $2^{2^l}$ 的数，注意一定要记位数保证复杂度，然后直接按二进制顺序乘起来。这样复杂度看似两 $\log$，实际仍是 $O(n\log n)$ 的。

预处理部分：$(1\times 2+2\times 2+4\times 2+\dots+2^{\log(n)}\times 2)\times \log n=O(n\log n)$，其中左边最后的 $\log$ 是 NTT。

快速幂部分：由于顺序，于是最坏的复杂度为 $(1+(1+2)+(1+2+4)+\dots(1+2+\dots +2^{\log(n)}))\log n=O(n\log n)$，其中左边最后的 $\log$ 是 NTT。

这里把估计的与实际的 $\log_{10}$ 的差距认为是 $O(1)$。

错解部分。

我当时第一想法是倍增，同样预处理 $2^{2^l}$，同样记位数，预处理复杂度不变。

计算部分我想倍增，就是相当于把上面快速幂的顺序变成倒序，这样复杂度变成了：

$(2^{\log(n)}+(2^{\log(n)}+2^{\log(n)-1})+(2^{\log(n)}+2^{\log(n)-1}+2^{\log(n)-2})+\dots(1+2+\dots +2^{\log(n)}))\log n=O(n\log^2 n)$

在本题条件下无法通过。于是不能倍增。