题解：AT_abc390_g [ABC390G] Permutation Concatenation

令 $sum_i$ 为位数为 $i$ 的所有数之和，$tot_i$ 为位数为 $i$ 的数的个数，$m$ 表示 $n$ 的位数。

令

考虑每一项的含义，$(1 + 10^{i}x)$ 中的 $1$ 表示下方不选这个数的贡献，$10^{i}x$ 表示下方选了这个数的贡献，$tot_i$ 作为指数代表有 $tot_i$ 个位数为 $i$ 的数可供选择。

于是可以自然地得到 $[x^j]F(x)$ 的含义为下方选了 $j$ 个数所产生的贡献之和。

考虑枚举位数为 $i$ 的数卡在中间产生的贡献：（注意我们钦定一个位数为 $i$ 的数卡在中间，所以有一个位数为 $i$ 的数不能自由选择，所以 $F(x)$ 中要少乘一项 $(1 + 10^{i}x)$）

注意到 $m = log_n$，所以 $i,j$ 可以暴力枚举，难点在于算出后面的多项式。

对后面的多项式取 $\ln$ 可得

由泰勒展开

故原式等于

因为取 $[x^j]$ 时 $j$ 不会超过 $n$，所以 $k$ 枚举到 $n$ 即可，这个式子可以 $O(nm)$ 计算，算完了再 $\exp$ 回去即可。

这样总时间复杂度是 $O(nm^{2} + n\log n) = O(n\log^{2}n)$。