
ZOJ Problem Set  4095
If a string $s$ is composed of digits from 0 to 9, we call this string a "digit string". It's obvious that each substring of $s$, except those who start with 0, can be considered as a positive integer. Let $\mathbb{S}$ be the set containing all these positive integers, define a function $$f(s) = \min\{x  x \in \mathbb{Z}^+, x \not\in \mathbb{S}\}$$ That is to say, $f(s)$ is the smallest positive integer which is not in $\mathbb{S}$. For example, $f(\text{"1241"}) = 3$, $f(\text{"542"}) = 1$, $f(\text{"11023456879"}) = 12$, and $f(\text{"00000"}) = 1$ (note that in this case, $\mathbb{S}$ is an empty set). Given a digit string $s$, let $\text{substr}(i, j)$ be the substring of $s$ which starts from the $i$th digit and ends at the $j$th digit, your task is to calculate $$\sum_{i=1}^{s}\sum_{j=i}^{s} f(\text{substr}(i, j))$$. InputThere are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case: The first and only line contains a digit string $s$ ($1 \le s \le 5 \times 10^5$). It's guaranteed that the sum of $s$ of all test cases will not exceed $5 \times 10^6$. OutputFor each test case output one line containing one integer, indicating the answer. Sample Input4 1241 542 11023456789 00000 Sample Output21 6 162 15 HintWe explain the first sample test case below.
So the answer is 2 + 1 + 1 + 2 + 3 + 1 + 2 + 3 + 3 + 3 = 21. For the second sample test case, it's obvious that the values of all the substrings are 1. So the answer is 6. Author: WENG, Caizhi Source: The 19th Zhejiang University Programming Contest Sponsored by TuSimple 