[题解] ABC390G Permutation Concatenation

· · 题解

记 m = \lfloor \lg n \rfloor，a_i = 10^{i+1}，b_i = \lvert [10^i, 10^{i + 1}) \cap[1, n] \cap \mathbb Z \rvert。

不难发现，对于 [10^i, 10^{i + 1}) 中的数，它们的贡献系数是相同的，为：

\sum_{0\le j < n} j!(n-j-1)! [x^j] \frac{\prod_{0 \le k \le m} (1+a_kx)^{b_k}}{(1+a_ix)}

那么现在的问题就是要计算出：

F(x) = \prod_{0 \le k \le m} (1+a_k x)^{b_k}

的各项系数。

求导可得：

F' = \sum_{0 \le k \le m} a_kb_k(1+a_kx)^{b_k-1} \prod_{\substack{0 \le j \le m \\ j \neq k}} (1+a_jx)^{b_j}

记：

G(x) = \prod_{0 \le k \le m} (1+a_kx)

那么有：

\begin{aligned} F' G &= \sum_{0 \le k \le m} a_k b_k \prod_{\substack{0 \le j \le m \\ j \neq k}} (1+a_jx)\prod_{1 \le j \le m} (1+a_jx)^{b_j} \\ &= \left(\sum_{0 \le k \le m} a_k b_k \prod_{\substack{0 \le j \le m \\ j \neq k}} (1+a_jx) \right) F \end{aligned}

记前面那一坨是 H，那么就得到了：

F'G = FH

两边同时提取 x^n 系数可得：

\begin{aligned} \sum_{0 \le i \le n} (i + 1) f_{i +1} g_{n - i} &= \sum_{0 \le i \le n} f_i h_{n - i} \\ (n+1)f_{n+1}g_0 &= \sum_{0 \le i \le n} f_i h_{n - i} - \sum_{0 \le i < n}(i+1)f_{i+1}g_{n-i} \\ f_{n + 1} &= \frac{1}{(n+1)g_0} \left( \sum_{0 \le i \le n} f_i h_{n - i} - \sum_{0 \le i < n}(i+1)f_{i+1}g_{n-i} \right) \end{aligned}

由于 H 和 G 都只有 O(m) 项，右边其实只有 O(m) 项，这样就能 O(n \log n) 递推出 F 的各项系数。

然后要算的就是：

\begin{aligned} P &= \frac{F}{(1+a_ix)} \\ \end{aligned}

的各项系数，这个也可以用类似的方法得到递推式：

\begin{aligned} (1+a_ix)P &= F \\ p_n+ a_i p_{n-1} &= f_n \\ p_n &= f_n - a_ip_{n-1} \end{aligned}

可以 O(n) 递推。

时间复杂度 O(n \log n)。

代码。