AT_dwango2015_prelims_2 ニコニコ文字列

给定一个由 $0$ 到 $9$ 组成的字符串 $S$。 对于某个字符串 $X$，如果 $X = "25"$，或者 $X = "2525"$，或者 $X = "252525"$，…… 也就是说，$X$ 是由若干次重复 "25" 拼接而成的字符串，那么称 $X$ 为“ニコニコ字符串”。例如，"25" 和 "25252525" 是ニコニコ字符串，而 "123" 和 "225" 不是ニコニコ字符串。 你的任务是，计算字符串 $S$ 中有多少种取出连续子串的方法，使得该子串是ニコニコ字符串。即使子串内容相同，只要取出的位置不同，也要分别计数。

输入从标准输入读入，格式如下： > $S$ - 第 $1$ 行给出字符串 $S$。$S$ 的长度为 $1$ 到 $100\,000$ 之间。$S$ 的每个字符都是 $0$ 到 $9$ 的数字。

输出一行，表示从字符串 $S$ 中取出ニコニコ字符串作为连续子串的方法数。 **注意：如果行末没有换行符，将被判定为不正确。**

## 部分分 本题设置了部分分。 如果你能对满足 $N \leq 2000$ 的数据集 1 全部答对，可以获得 $30$ 分。对没有额外限制的数据集 2 全部答对，则在上述基础上再获得 $70$ 分，总计 $100$ 分。 ## 样例解释 1 对于 $S = "2525"$ 的情况，取出子串为 "25" 的方法有 $2$ 种，取出子串为 "2525" 的方法有 $1$ 种，所以总共输出 $3$。 由 ChatGPT 4.1 翻译