题解：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

。

文章操作