题解：AT_abc379_e [ABC379E] Sum of All Substrings

· · 题解

思路：拆分，算贡献。

让我们先玩玩样例。

比如对于这个数 379， 它的所有拆分的和是 3+37+379+7+79+9。

继续拆：3+37+379+7+79+9=3+30+7+300+70+9+7+70+9+9

合并：\text{上式}=333+77\times 2+9\times3。

对于这个式子进行推广，设数字从左往右第 i 位的数是 a_i，不难发现答案就是下面这个式子：

我们发现直接用高精度计算似乎不太现实，于是考虑优化。 对于答案，可以先不考虑进位，设答案数组是 $c$，上式的每一项都可以变为如下操作： - 把 $c$ 的 $1$ 到 $n$ 位全部加上 $a_1\times 1$， - 把 $c$ 的 $2$ 到 $n$ 位全部加上 $a_2\times 2

我们就可以使用差分完成以上操作。

最后一遍前缀和统计答案，然后处理进位即可。

代码

时间复杂度：O(n)