CF908G New Year and Original Order

Sol

设 $c_i(0\le i\le 9)$ 表示 $i$ 这个数字在 $k$ 中出现了几次，则

$$\begin{aligned} Ans &= \sum_{k=1}^X \sum_{i=1}^9 i \cdot \frac{10^{\sum_{j=i}^9 c_j}-10^{\sum_{j=i+1}^9 c_j}}{9}\\ &= \sum_{k=1}^X \sum_{i=1}^9 \sum_{y=1}^i \frac{10^{\sum_{j=i}^9 c_j}-10^{\sum_{j=i+1}^9 c_j}}{9}\\ &= \sum_{k=1}^X \sum_{y=1}^9 \sum_{i=y}^9 \frac{10^{\sum_{j=i}^9 c_j}-10^{\sum_{j=i+1}^9 c_j}}{9}\\ &= \sum_{k=1}^X \sum_{y=1}^9 \frac{10^{\sum_{j=y}^9 c_j}-1}{9}\\ \end{aligned}$$

在最外层枚举 $y$ 之后，可以用数位 dp 在 $O(\lg^2 X)$ 的时间内算出答案。

Code

link