Foreigner

题意翻译

## 题目描述 定义 “不充分” 的数字 $x$ 必须满足以下条件之一 - $x$ 是 $[1, 9]$ 范围内的数字 - $\lfloor x/10\rfloor$ 是一个 “不充分” 的数字；并且若给每个 “不充分” 的数字排名（序号从 $1$ 开始），而 $\lfloor x/10\rfloor$ 得到的排名为 $k$，那么 $x$ 的最后一位数必须严格小于 $k\mod 11$ 这里 $\lfloor x/10\rfloor$ 指 $x/10$ 向下取整 因此，如果有一个 “不充分” 的数字，且其排名为 $m$，而 $m$ 模 $11$ 的余数为 $c$，那么 $10\cdot x+0, 10\cdot x+1, \cdots, 10\cdot x+(c-1)$ 都是 “不充分” 的，同时 $10\cdot x+c, 10\cdot x+(c+1), \cdots, 10\cdot x+9$ 都不是 “不充分” 的 前几个 “不充分” 的数字为 $1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, 21, 30, 31, 32, \cdots$ 在这之后，$40, 41, 42, 43$ 是 “不充分” 的，而 $44, 45, 46, \cdots, 49$ 不是 “不充分” 的；由于 $10$ 是第 $10$ 个 “不充分” 的数字，因此 $100, 101, 102, \cdots, 109$ 都是 “不充分” 的。由于 $20$ 是第 $11$ 个 “不充分” 的数字，因此 $200, 201, 202, \cdots, 209$ 中，没有一个数是 “不充分” 的 现在给出一个仅由数字组成的字符串，你需要求出该字符串中所有为 “不充分” 的数字的子串数量。如果一个一个子串在不同的位置出现多次，则对它的所有出现分别计数 ## 输入格式 仅一行，一个字符串 $s$（$1\leq |s|\leq 10^5$），仅由数字组成。保证 $s$ 的第一个字符不是零 ## 输出格式 仅一行，即构成 “不充分” 数字的 $s$ 的子串的数量 ## 样例解释 在第一个样例中，字符串中 “不充分” 的数字是 $1, 2, 4, 21, 40, 402$ 在第二个样例中，字符串中 “不充分” 的数字是 $1, 10$，并且 $1$ 出现了两次（分别为 $s$ 的第一位和第二位）

题目描述

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.

输入输出格式

输入格式

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.

输出格式

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

输入输出样例

输入样例 #1

4021

输出样例 #1

6

输入样例 #2

110

输出样例 #2

3

说明

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).