Foreigner
Contest: Codeforces Round 549 (Div. 1)
Difficulty rating: 2800
Tags: dp

Traveling around the world you noticed that many shop owners raise prices to inadequate values if the see you are a foreigner.

You define inadequate numbers as follows:

- all integers from $$$1$$$ to $$$9$$$ are inadequate;
- for an integer $$$x \ge 10$$$ to be inadequate, it is required that the integer $$$\lfloor x / 10 \rfloor$$$ is inadequate, but that's not the only condition. Let's sort all the inadequate integers. Let $$$\lfloor x / 10 \rfloor$$$ have number $$$k$$$ in this order. Then, the integer $$$x$$$ is inadequate only if the last digit of $$$x$$$ is strictly less than the reminder of division of $$$k$$$ by $$$11$$$.

Here $$$\lfloor x / 10 \rfloor$$$ denotes $$$x/10$$$ rounded down.

Thus, if $$$x$$$ is the $$$m$$$-th in increasing order inadequate number, and $$$m$$$ gives the remainder $$$c$$$ when divided by $$$11$$$, then integers $$$10 \cdot x + 0, 10 \cdot x + 1 \ldots, 10 \cdot x + (c - 1)$$$ are inadequate, while integers $$$10 \cdot x + c, 10 \cdot x + (c + 1), \ldots, 10 \cdot x + 9$$$ are not inadequate.

The first several inadequate integers are $$$1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, 21, 30, 31, 32 \ldots$$$. After that, since $$$4$$$ is the fourth inadequate integer, $$$40, 41, 42, 43$$$ are inadequate, while $$$44, 45, 46, \ldots, 49$$$ are not inadequate; since $$$10$$$ is the $$$10$$$-th inadequate number, integers $$$100, 101, 102, \ldots, 109$$$ are all inadequate. And since $$$20$$$ is the $$$11$$$-th inadequate number, none of $$$200, 201, 202, \ldots, 209$$$ is inadequate.

You wrote down all the prices you have seen in a trip. Unfortunately, all integers got concatenated in one large digit string $$$s$$$ and you lost the bounds between the neighboring integers. You are now interested in the number of substrings of the resulting string that form an inadequate number. If a substring appears more than once at different positions, all its appearances are counted separately.

Input format:
The only line contains the string $$$s$$$ ($$$1 \le |s| \le 10^5$$$), consisting only of digits. It is guaranteed that the first digit of $$$s$$$ is not zero.

Output format:
In the only line print the number of substrings of $$$s$$$ that form an inadequate number.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first example the inadequate numbers in the string are $$$1, 2, 4, 21, 40, 402$$$.

In the second example the inadequate numbers in the string are $$$1$$$ and $$$10$$$, and $$$1$$$ appears twice (on the first and on the second positions).

Example input:
4021

Example output:
6

Example input:
110

Example output:
3

Editorial:
Let's take any inadequate number $$$x$$$ of length $$$n$$$. Let's keep 3 parameters for it: $$$a_x$$$ which is the number of all inadequate numbers less of equal then $$$x$$$, $$$b_x$$$ which is the number of inadequate numbers less then $$$x$$$ which have length $$$n$$$ and $$$c_x$$$ which is the number of inadequate numbers grater then $$$x$$$ which have length $$$n$$$. We know that there are exactly $$$a_x$$$ modulo 11 inadequate numbers that come from $$$x$$$ by adding a new digit to the end. Also, because we know $$$b_x$$$ and $$$c_x$$$, we can find $$$a$$$, $$$b$$$ and $$$c$$$ parameters for each of those numbers. Let's now notice, that if instead of keeping $$$a$$$, $$$b$$$ and $$$c$$$ parameters we can keep all of them modulo 11. The parameters of all numbers that come from $$$x$$$ will still be defined because if we increase $$$a$$$ by 11, these parameters will be the same modulo 11, if we increase $$$b$$$ by 11, $$$a$$$ and $$$b$$$ parameters of all numbers that come from $$$x$$$ are increase by $$$0 + 1 + 2 + \ldots + 10 = (11 \cdot 10) / 2 = 55$$$ which is 0 modulo 11. The same is with $$$c$$$ parameter. So these 3 parameters modulo 11 exactly define what new numbers will come from $$$x$$$ and the values of these 3 parameters for them. Now we can create some kind of automaton of size $$$11^3$$$, where we will have 9 starting nodes and all paths from these nodes will be the inadequate numbers and for any inadequate number there will be path which will define it. Now let's create dynamic $$$dp[i][j]$$$, which is how long we can go into the automaton by the characters of suffix of length $$$i$$$ of our given string $$$s$$$ starting from node $$$j$$$ in automaton. We can calculate this $$$dp$$$ in $$$n \cdot 11^3$$$ time and using it we can check for each suffix of $$$s$$$ what is its longest prefix that is an inadequate number and so we can solve the problem.
Actually, during the contest it turned out that this problem has shorter solution, but this is more general one which doesn't depend on the starting numbers (in our case they were $$$1, 2, 3, \ldots 9$$$).