题解：AT_abc390_g [ABC390G] Permutation Concatenation

· · 题解

观前提示：3 \times 10^5 是 6 个数，而不是 5 个（不要问为什么要提示）。

考虑先求出 len_i 表示长度为 i 的数有多少个，以及 s_i 表示长度为 i 的数之和。

我们对数 x 统计其造成的所有贡献，可以写出（注意 x 对应的 len 要减 1）：

\sum_{\{v_i\}}(x\prod_{i=1}^{6}(10^{i})^{v_i})(\prod_{i=1}^{6}\binom{len_i}{v_i})(\sum v_i)!(n-1-\sum v_i)!

稍微解释下，枚举每种数有多少个在 x 之前，然后贡献就是 (x\prod_{i=1}^{6}(10^{i})^{v_i})，方案数就是 (\sum v_i)!(n-1-\sum v_i)!。

整理一下：

\sum_{\{v_i\}}x(\prod_{i=1}^{6}(10^{i})^{v_i}\binom{len_i}{v_i})(\sum v_i)!(n-1-\sum v_i)!

设哑元 L(u^i)=i!(n-1-i)!，根据线性性，原式：

x\sum_{\{v_i\}}(\prod_{i=1}^{6}\binom{len_i}{v_i}(10^iu)^{v_i})\\=x\prod_{i=1}^{6}(1+10^iu)^{len_i}

直接对同一类数求和，答案就是：

\sum_{i=1}^{6}s_i\prod_{j=1}^{6}(1+10^ju)^{len_j-[j=i]}\\ans=\sum_{i=1}^{6}\sum_{k=0}^{n-1}s_ik!(n-1-k)![u^k]\prod_{j=1}^{6}(1+10^ju)^{len_j-[j=i]}

具体求解可以先快速幂 O(n\log^{2}{n}) 求出，再除掉一个 (1+10^{i}u)，容易做到 O(n)。

时间复杂度就是 O(n\log^2{n}+V(n+k)),V=6。