AT_abc164_d [ABC164D] Multiple of 2019

题目描述

给定一个只包含数字 $1$ 到 $9$ 的字符串 $S$。

请你计算满足以下条件的整数对 $(i, j)$（$1 \leq i \leq j \leq |S|$）的总数。

条件：将 $S$ 的第 $i$ 个字符到第 $j$ 个字符看作一个十进制整数时，这个整数是 $2019$ 的倍数。

输入格式

输入为以下格式，通过标准输入给出。

$S$

输出格式

请输出满足条件的整数对 $(i, j)$（$1 \leq i \leq j \leq |S|$）的总数。

样例 1

输入

1817181712114

输出

3

样例 2

输入

14282668646

输出

2

样例 3

输入

2119

输出

0

说明/提示

限制条件

• $1 \leq |S| \leq 200000$
• $S$ 是只包含数字 $1$ 到 $9$ 的字符串

样例解释 1

满足条件的有 $(1,5),\ (5,9),\ (9,13)$ 共 $3$ 个。

样例解释 3

不存在满足条件的整数对。

由 ChatGPT 4.1 翻译