题解：AT_abc390_g [ABC390G] Permutation Concatenation
TLE_Automat
·
·
题解
令 sum_i 为位数为 i 的所有数之和，tot_i 为位数为 i 的数的个数，m 表示 n 的位数。
令
\begin{aligned}
F(x) = \prod_{i = 0}^{m} (1 + 10^{i}x)^{tot_i}
\end{aligned}
考虑每一项的含义，(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)）
\begin{aligned}
\sum_{i = 0}^{m} sum_i \sum_{j = 1}^{n} j!(n - j - 1)![x^{j}]\frac{F(x)}{1 + 10^{i}x}
\end{aligned}
注意到 m = log_n，所以 i,j 可以暴力枚举，难点在于算出后面的多项式。
对后面的多项式取 \ln 可得
\begin{aligned}
\ln\frac{F(x)}{1 + 10^{i}x} = \left[\sum_{j = 0}^{m}tot_{j}\ln(1 + 10^{j}x)\right] - \ln(1 + 10^{i}x)
\end{aligned}
由泰勒展开
\ln(1 + x) = \sum_n(-1)^{n - 1}\frac{x^{n}}{n}
故原式等于
\begin{aligned}
\left[\sum_{j = 0}^{m}tot_{j}\sum_{k = 0}^{\infty}(-1)^{k}\frac{(10^{j}x)^{k}}{k}\right] - \sum_{k = 0}^{\infty}(-1)^{k}\frac{(10^{i}x)^{k}}{k}
\end{aligned}
因为取 [x^j] 时 j 不会超过 n，所以 k 枚举到 n 即可，这个式子可以 O(nm) 计算，算完了再 \exp 回去即可。
这样总时间复杂度是 O(nm^{2} + n\log n) = O(n\log^{2}n)。