Problem:


Score : 400 points

Problem Statement

Given is a string S consisting of digits from 1 through 9.

Find the number of pairs of integers (i,j) (1 ≤ i ≤ j ≤ |S|) that satisfy the following condition:

Condition: In base ten, the i-th through j-th characters of S form an integer that is a multiple of 2019.

Constraints

1 ≤ |S| ≤ 200000

S is a string consisting of digits from 1 through 9.

Input

Input is given from Standard Input in the following format:

S

Output

Print the number of pairs of integers (i,j) (1 ≤ i ≤ j ≤ |S|) that satisfy the condition.

Sample Input 1

1817181712114

Sample Output 1

3

Three pairs - (1,5), (5,9), and (9,13) - satisfy the condition.

Sample Input 2

14282668646

Sample Output 2

2

Sample Input 3

2119

Sample Output 3

0

No pairs satisfy the condition.



Sample input:
1817181712114


Sample output:
3

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc164/tasks/abc164_d

import sys
input = sys.stdin.readline


S = input().rstrip()

res = 0

x = 0
p = 1
L = len(S)
MOD = 2019
reminder = [0]*2019
reminder[0] = 1
for s in reversed(S):
    """ 累積和 """
    x = (int(s)*p + x)%MOD
    p = p*10%MOD
    reminder[x] += 1

for c in reminder:
    res += c*(c-1)//2

print(res)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc164/tasks/abc164_d

import sys
input = sys.stdin.readline


S = input().rstrip()

res = 0

T = [0]
x = 0
p = 1
L = len(S)
MOD = 2019
for s in reversed(S):
    """ 累積和 """
    x = (int(s)*p + x)%MOD
    p = p*10%MOD
    T.append(x)

reminder = [0]*2019
for i in range(L+1):
    reminder[T[i]%MOD] += 1

for c in reminder:
    res += c*(c-1)//2

print(res)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc164/tasks/abc164_d

import sys
input = sys.stdin.readline


S = input().rstrip()

res = 0

T = [0]
x = 0
p = 1
L = len(S)
MOD = 2019
for i, s in zip(range(L),reversed(S)):
    """ 累積和 """
    x = (int(s)*p + x)%MOD
    p = p*10%MOD
    T.append(x)

reminder = [0]*2019
for i in range(L+1):
    reminder[T[i]%MOD] += 1

for c in reminder:
    res += c*(c-1)//2

print(res)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc164/tasks/abc164_d

from operator import mul
from functools import reduce
from collections import defaultdict

def combination(n, r):
    if not 0 <= r <= n: return 0
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

S = input()

res = 0

T = [0]
x = 0
L = len(S)
for i, s in zip(range(L),reversed(S)):
    """ 累積和 """
    x = (int(s)*pow(10,i,2019) + x)%2019
    T.append(x)

reminder = [0]*2019
for i in range(L+1):
    reminder[T[i]%2019] += 1

for c in reminder:
    res += combination(c,2)

print(res)

Submission status: Accepted

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import fractions
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
import collections
from collections import Counter
from collections import deque
import pprint
import itertools

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""


def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr


# a^n
def power(a, n, mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod


# n*(n-1)*...*(l+1)*l
def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a

# Union Find
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# 約数生成
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors


inf = 10 ** 18
mod = 10 ** 9 + 7

s = list(sr())
s.reverse()
dp = [0 for i in range(len(s)+1)]
tmod = 1
for i,c in enumerate(s):
    now = int(c)
    dp[i+1] = (dp[i]+now*tmod)%2019
    tmod = (tmod*10)%2019
ans = 0
for _,v in collections.Counter(dp).items():
    ans+=(v*(v-1)//2)
print(ans)

Submission status: Accepted

Solution code:
MOD = 2019
"""
def part_count(S):
  B = [0 for _ in range(MOD)]
  C = [0 for _ in range(MOD)]
  L = [0 for _ in range(MOD)]
  R = [0 for _ in range(MOD)]
  
  if len(S) == 1:
    s = S[0]
    B[s] = 1 
    return (B, L, R, C)
  S_L = S[:len(S)//2]
  S_R = S[len(S)//2:]
  
  B1, L1, R1, C1 = part_count(S_L)
  B2, L2, R2, C2 = part_count(S_R)
    
  for j in range(MOD):
    C[j] += C1[j] + C2[j]
    L[j] += L1[j]
    R[j] += R2[j]
    for i in range(MOD):
      B[j] += B1[i] * B2[(-i + j)%MOD]
      L[j] += B1[i] * L2[(-i + j)%MOD]
      R[j] += B2[i] * R1[(-i + j)%MOD]
      C[j] += R1[i] * L2[(-i + j)%MOD]
  
  return (B, L, R, C) #両側隣接、左隣接、右隣接、隣接なしの個数
"""

S = list(input())
S.reverse()
N = len(S)
S = [int(S[i]) for i in range(N)]
MOD = 2019

a = 1
for i in range(N): 
  S[i] *= a
  S[i] %= MOD
  a *= 10 
  a %= MOD
  
#B, L, R, C = part_count(S)
#print(B[0] + L[0] + R[0] + C[0])
T = [0 for _ in range(N+1)]
for i in range(1,N+1):
  T[i] += S[i-1] + T[i-1]
  T[i] %= MOD

#print(T)

C = [0 for i in range(MOD)]  
for i in range(N+1):
  C[T[i]] += 1

#print(C)

ans = 0
for i in range(MOD):
  ans += C[i]*(C[i]-1)//2
  
print(ans)

Submission status: Accepted

Solution code:
S=list(input())
P=0
M=2019
D=[0]*M
D[0]=1
X,Y=0,1
for i in range(len(S)):
  X+=Y*int(S[-i-1])
  X%=M
  P+=D[X]
  D[X]+=1
  Y=Y*10%M
print(P)

Submission status: Accepted

Solution code:
def main():
  n, mods = 0, [1]+[0]*2019
  d = 1
  for i in reversed(input()):
    n = (n+int(i)*d)%2019
    d = d*10%2019
    mods[n] += 1
  print(sum([i*(i-1)//2 for i in mods]))
main()

Submission status: Accepted

Solution code:
#0からiまでのSを2019で割ったときのあまりを調べる
#A%mod =a,B$mod=aなら（A-B)%mod=0
from collections import Counter
S = input()
dp = [0]
mod = 2019
for i in reversed(range(len(S))):
    dp.append(dp[-1]%mod+pow(10,len(S)-i-1,mod)*int(S[i]))
    dp[-1]%=mod
count = Counter(dp)
ans = 0
for key,val in count.items():
    if val>=2:
        ans += val*(val-1)//2
print(ans)

Submission status: Accepted

Solution code:
s=input()
ls=len(s)
m=[0]*(2019)
m[0]+=1

cnt = 0
b = 0
for i in range(ls):
  a = (b + pow(10,cnt,2019)*int(s[ls - i -1])) % 2019
  m[a] += 1
  b = a
  cnt += 1

ans = 0
for i in m:
  if i <= 1:
    continue
  ans += i*(i-1)//2

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
S = input()
C = Counter()
MOD = 2019

n = 0
for i, s in enumerate(S[::-1]):
    s = int(s)
    n += pow(10, i, MOD) * s % MOD
    C[n % MOD] += 1

C[0] += 1
ans = 0
for v in C.values():
    ans += v * (v - 1) // 2
print(ans)

Submission status: Accepted

Solution code:
def main():
    s = input()
    mod = 2019
    mod_count = {i: 0 for i in range(mod)}
    now_num = 0
    base = 1
    for i in range(len(s) - 1, -1, -1):
        mod_count[now_num] += 1
        now_num += base * int(s[i])
        now_num %= mod
        base *= 10
        base %= mod
    ans = 0
    mod_count[now_num % mod] += 1
    for i in range(mod):
        ans += mod_count[i] * (mod_count[i] - 1) // 2
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools

S = input()[::-1]

m = [0]*len(S)
tmp = 1
for i in range(len(S)):
    m[i] = int(S[i])*tmp%2019
    tmp = tmp*10%2019

cum = [0]+[0]*len(S)
for i in range(1,len(S)+1):
    cum[i] = (cum[i-1]+m[i-1])%2019

d = {}
ans = 0
for i in range(len(cum)):
    if cum[i] not in d:
        d[cum[i]] = 1
    else:
        ans += d[cum[i]]
        d[cum[i]] += 1
print(ans)

Submission status: Accepted

Solution code:
S = str(input())
li = [0] * 2019
ans = 0
li[0] = 1

d = 1
s = 0
for i in S[::-1]:
  s += int(i) * d
  s = s % 2019
  li[s] += 1
  d *= 10
  d = d % 2019
  
for l in li:
  ans += l * (l-1) // 2

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
S = input()
L = len(list(S))
dp = [0] * L
dp[0] = 1
T = [0] * L
T[0] = int(S[-1])
for i in range(1, L):
    dp[i] =  dp[i - 1] * 10
    dp[i] %= 2019
    T[i] = int(S[-(i+1)]) * dp[i] + T[i - 1]
    T[i] %= 2019
ans = 0
for k, v in Counter(T).items():
    if k == 0:
        ans += v
        ans += v * (v - 1) // 2
    else:
        ans += v * (v - 1) // 2
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from collections import deque
from functools import lru_cache
import bisect
import re
import queue
import decimal


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [Scanner.string() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [Scanner.int() for i in range(n)]


MOD = 2019
# INF = int(1e15)


def solve():
    S = Scanner.string()
    S = S[::-1]
    cnt = [0 for _ in range(MOD)]
    tmp = 0
    ans = 0
    x = 1
    for s in S:
        cnt[tmp] += 1
        tmp += int(s) * x
        tmp %= MOD
        x *= 10
        x %= MOD
        ans += cnt[tmp]
    print(ans)


def main():
    # sys.setrecursionlimit(1000000)
    # sys.stdin = open("sample.txt")
    # T = Scanner.int()
    # for _ in range(T):
    #     solve()
    # print('YNeos'[not solve()::2])
    solve()


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
mod = 2019

s = input().strip()[::-1]
l = [0] * mod

n10 = [1]
for _ in range(len(s)):
    n10.append(n10[-1] * 10 % mod)

n = 0
for i, c in enumerate(s):
    n += n10[i] * int(c)
    n %= mod
    l[n] += 1

ans = 0
for i, v in enumerate(l):
    if v > 1:
        ans += v * (v - 1) // 2
    if i == 0:
        ans += v
print(ans)

Submission status: Accepted

Solution code:
#import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left, bisect_right #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 2019
def input(): return sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep='\n')

S = input()
N = len(S)

d = defaultdict(int)
d[0] += 1
# nums = [0]*(N+1)
m = 0
last = 0
dd = 1
for i in range(N):
    m += int(S[N-i-1])*dd
    m %= MOD
    # val = (int(S[i])*m + nums[i])%MOD
    # cnt += d[val]
    dd = (dd*10)%MOD
    d[m] += 1

cnt = 0
for i, v in d.items():
    cnt += v*(v-1)//2
print(cnt)

Submission status: Accepted

Solution code:
import collections
from math import factorial

def permutations_count(n, r):
    ''' 順列 '''
    return factorial(n) // factorial(n - r)

def combinations_count(n, r):
    ''' 組み合わせ '''
    return factorial(n) // (factorial(n - r) * factorial(r))


S = input()

lis = []
amari = 1
lis.append(int(S[-1]))

for i in range(2,len(S)+1):
    amari = (amari * 10) % 2019
    lis.append((int(S[-1*i]) * amari + lis[i-2]) % 2019)

c = collections.Counter(lis)

su = 0

for k in c:
    if c[k] > 1:
        su += combinations_count(c[k], 2)
        
        
        
su += c[0]

print(su)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from collections import deque
from functools import lru_cache
import bisect
import re
import queue
import decimal


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [Scanner.string() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [Scanner.int() for i in range(n)]


# MOD = int(1e09) + 7
MOD = 2019
INF = int(1e15)


def solve():
    S = Scanner.string()
    N = len(S)
    S = S[::-1]
    p = 1
    total = 0
    cnt = [0 for _ in range(MOD)]
    ans = 0
    for i in range(N):
        cnt[total] += 1
        total += int(S[i]) * p
        total %= MOD
        ans += cnt[total]
        p = p * 10 % MOD
    print(ans)


def main():
    # sys.setrecursionlimit(1000000)
    # sys.stdin = open("sample.txt")
    # T = Scanner.int()
    # for _ in range(T):
    #     solve()
    # print('YNeos'[not solve()::2])
    solve()


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
s=input()
n=len(s)

from collections import Counter
c=Counter()
m=0
c[m]+=1
d=1
s=s[::-1]
for i in range(n):
  m+=int(s[i])*d
  m%=2019
  d*=10
  d%=2019
  c[m]+=1
ans=0
for v in c.values():
  ans+=v*(v-1)//2
print(ans)

Submission status: Accepted

Solution code:
S=input()
ans=0
MOD=2019
cnt=[0]*MOD
cur=0
cnt[cur]=1
d=1
for s in S[::-1]:
  cur+=int(s)*d
  cur%=MOD
  cnt[cur]+=1
  d*=10
  d%=MOD
for c in cnt:
  ans+=c*(c-1)//2
print(ans)

Submission status: Accepted

Solution code:
S = input()
mod = 2019
count = [0] * 2019
count[0] = 1
tmp = 0
d = 1

for s in S[::-1]:
    tmp += int(s) * d
    count[tmp % mod] += 1
    d *= 10
    d %= mod

ans = 0

for c in count:
    ans += c * (c - 1) // 2
        
print(ans)

Submission status: Accepted

Solution code:
S = input()
MOD = 2019
cnt = [0]*MOD
cur = 0 # 現在考えている部分文字列
cnt[cur] = 1 # 部分文字列'0'も作れたと考える
d = 1 # 位を表す
for s in S[::-1]: # 右から作る
    cur += int(s)*d # 新たな桁を追加
    cur %= MOD
    cnt[cur] += 1
    # 後処理
    d *= 10 # 位を上げる
    d %= MOD # ただし数が巨大になるため、計算量を減らすために剰余をとる
ans = 0
for c in cnt:
    ans += c*(c-1)//2
print (ans)

Submission status: Accepted

Solution code:
from collections import defaultdict


def solve(input_s: str):
    ans = 0
    n = len(input_s)
    mod = 2019
    dp = defaultdict(int)
    cur = 0
    for i in range(n, -1, -1):
        if i == n:
            dp[0] += 1
        else:
            # cur += ((10 ** (n - i - 1)) * int(input_s[i])) % mod これはnがでかくなるとめちゃめちゃ遅い
            cur += pow(10, n - i - 1, 2019) * int(input_s[i]) % mod
            cur %= mod
            dp[cur] += 1
    for v in dp.values():
        if v > 1:
            ans += v * (v - 1) // 2
    return ans


if __name__ == '__main__':
    S = input()
    print(solve(S))

Submission status: Accepted

Solution code:
from collections import Counter, defaultdict
a = defaultdict(int)
a[0] += 1
s = input()[::-1]
cur = 0
for i, x in enumerate(s):
    cur += (int(x)*pow(10, i, 2019))%2019
    cur %= 2019
    a[cur] += 1

def comb(a):
    return a*(a-1)//2

ans = 0
for x in a.values():
    if x >= 2:
        ans += comb(x)
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
# from collections import deque
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np    # cumsum
# from bisect import bisect_left, bisect_right

def solve():
    S = list(map(int, LS()))
    S = S[::-1]
    ln = len(S)
    mod = 2019

    times = 1
    for i in range(ln):
        S[i] = S[i] * times
        times = times * 10 % mod

    R = [0] * (ln+1)
    memo = {0: 1}
    ans = 0
    for i in range(1, ln+1):
        tmp = (R[i-1] + S[i-1]) % mod
        R[i] = tmp
        cnt = memo.get(tmp, 0)
        ans = ans + cnt
        memo[tmp] = cnt + 1
    print(ans)

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
s=input()


s=s[::-1]
l=[0]*2019
l[0]=1
prev=0
ans=0
mul=1

for i in range(len(s)):
  now=(int(s[i])*mul)%2019
  ans+=l[(prev+now)%2019]
  l[(prev+now)%2019]+=1
  prev=(prev+now)%2019
  mul=(mul*10)%2019

print(ans)

Submission status: Accepted

Solution code:
S = input()
mod2019 = [0]*len(S)

mod2019[-1] = int(S[-1])
keta_mod = 1
for i in range(len(S)-2,-1,-1):
    keta_mod = (keta_mod*10)%2019
    mod2019[i] = (mod2019[i+1] + int(S[i])*keta_mod)%2019

mod2019.extend([0])

answer = 0
count = [0 for _ in range(2020)]

for i in range(len(S)+1):
    answer += count[mod2019[i]]
    count[mod2019[i]] += 1
print(answer)

Submission status: Accepted

Solution code:
import sys
import itertools
import numpy as np
import time
import math
import re

sys.setrecursionlimit(10**7)

from collections import defaultdict
from collections import Counter

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def main():
    S = input()[::-1]
    MOD = 2019
    
    X = [0]
    for i, s in enumerate(S):
        X.append((X[-1] + int(s) * pow(10, i, MOD)) % MOD)
    
    C = Counter(X)
    ans = 0
    for v in C.values():
        ans += v * (v - 1) // 2
    print(ans)




if __name__ == "__main__":
    main()
    pass

Submission status: Accepted

Solution code:
import collections
import sys
S = input()[::-1]
    
MOD=2019
X = [0]
for i, s in enumerate(S):
    X.append((X[-1]+int(s)*pow(10,i,MOD))%MOD)
    
c = collections.Counter(X)
ans = 0
for v in c.values():
    ans += v * (v - 1) // 2
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
S = input()[::-1]
MOD = 2019

X = [0]
for i, s in enumerate(S):
    X.append((X[-1] + int(s) * pow(10, i, MOD)) % MOD)

C = Counter(X)
ans = 0
for v in C.values():
    ans += v * (v - 1) // 2
print(ans)

Submission status: Accepted

Solution code:
s = input()
n = len(s)

memo = [0] * 2019
memo[0] += 1

num = 0
t = 1
for i in reversed(s):
    num += int(i) * t
    num %= 2019
    t *= 10
    t %= 2019
    memo[num] += 1

ans = 0
for p in memo:
    ans += p*(p-1)//2

print(ans)

Submission status: Accepted

Solution code:
s = input()

r = 0
dict_r = {0: 1}
r10 = 1
for i in range(len(s)):
    d = int(s[-i - 1])
    r = (r + d * r10) % 2019
    r10 = (r10 * 10) % 2019

    dict_r[r] = dict_r.get(r, 0) + 1


answer = sum(v * (v - 1) // 2 for v in dict_r.values())
print(answer)

Submission status: Accepted

Solution code:
import sys 
from collections import Counter
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
mod = 2019
S = readline().decode().rstrip()
N = len(S)
S = S[::-1]
mod_list = [0]*N
mod_list[0] = int(S[0])
power = 1
for i in range(1,N):
    power *=10
    power %= mod
    mod_list[i] = power * int(S[i]) + mod_list[i-1]
    mod_list[i] %= mod
    
mod_cnt = Counter(mod_list)
ans = sum(n*(n-1)//2 for n in mod_cnt.values()) +mod_cnt[0]
print(ans)

Submission status: Accepted

Solution code:
s = input()

MOD = 2019
d = [0] * MOD
d[0] = 1
r = 0
t = 1
for i in reversed(s):
    r += int(i) * t
    r %= MOD
    t *= 10
    t %= MOD
    d[r] += 1

print(sum(i * (i - 1) // 2 for i in d))

Submission status: Accepted

Solution code:
from collections import Counter
s = input()
ac = [0]

def power_func(a,b,p):
    """a^b mod p を求める"""
    if b==0: return 1
    if b%2==0:
        d=power_func(a,b//2,p)
        return d*d %p
    if b%2==1:
        return (a*power_func(a,b-1,p ))%p

for i in range(len(s)):
    char = s[i]
    digit = len(s) - i - 1
    ac.append((ac[-1] + (int(char) * power_func(10, digit, 2019))) % 2019)
#print(ac)

C = Counter(ac)
#print(C)
ans = 0
for val in C.values():
    ans += val * (val - 1) // 2
print(ans)

Submission status: Accepted

Solution code:
s = input()[::-1]

MOD = 2019

cum = 0
cnt = [0] * 2019
cnt[0] = 1

d = 1
for c in s:
    cum += int(c) * d
    cum %= MOD
    cnt[cum] += 1
    d *= 10
    d %= MOD

ans = 0
for v in cnt:
    ans += v * (v - 1) // 2

print(ans)

Submission status: Accepted

Solution code:
# import itertools
S = input()[::-1]
# l = len(S)
# nums = range(1, l+1)
count = [0]*2019
count[0] = 1
num = 0
d = 1
for i in S:
    num += int(i)*d
    num %= 2019
    count[num] += 1
    d *= 10
    d %= 2019

ans = 0
for i in count:
    ans += i*(i-1)//2
print(ans)

Submission status: Accepted

Solution code:
# import itertools
S = input()[::-1]
# l = len(S)
# nums = range(1, l+1)
count = [0]*2019
count[0] = 1
num = 0
d = 1
for i in S:
    num += int(i)*d
    count[num % 2019] += 1
    d *= 10
    d %= 2019

ans = 0
for i in count:
    ans += i*(i-1)//2
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

S = input()
n = len(S)

dp = [0]*(n+1)

dp[n-1] = int(S[-1])

for i in range(n-2,-1,-1):
    dp[i] = (dp[i+1]+pow(10,n-i-1,2019)*int(S[i]))%2019

ans = Counter(dp)
cnt = 0
for i in ans.values():
    cnt += i*(i-1)//2
    
print(cnt)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.buffer.readline

INF = float('inf')


def main():
    s = map(int, input()[::-1])
    mod = 2019
    counts = [0] * mod
    counts[0] = 1
    t = 0
    x = 1
    for num in s:
        t = (t + num * x) % mod
        counts[t] += 1
        x = (x * 10) % mod
    ans = 0
    for count in counts:
        if count > 1:
            ans += count * (count - 1) // 2
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    s = input()
    rem_l = [0]*2019
    rem_l[0] = 1
    curr_rem = 0
    for i, s_i in enumerate(s[::-1]):
        num = int(s_i)
        curr_rem = (curr_rem + num*pow(10,i,2019))%2019
        rem_l[curr_rem] += 1

    ans = 0
    for r in rem_l:
        ans += r*(r-1)//2

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import Counter
S = list(input())
S.reverse()
MOD = 2019

t = [0]
r = 1
for i in range(len(S)):
    q = (t[-1] + (int(S[i]) * r)) % MOD
    t.append(q)
    r *= 10
    r %= MOD

cnt = Counter(t)
cnt_mc = cnt.most_common()

ans = 0
for _, j in cnt_mc:
    if j >= 2:
        ans += j * (j - 1) // 2
        
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
S = list(input())
S.reverse()
MOD = 2019

t = [0]
r = 1
for i in range(len(S)):
    q = (t[-1] + (int(S[i]) * r) % MOD) % MOD
    t.append(q)
    r *= 10
    r %= MOD

cnt = Counter(t)
cnt_mc = cnt.most_common()

ans = 0
for _, j in cnt_mc:
    if j >= 2:
        ans += j * (j - 1) // 2
        
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

MOD = 2019
S = input()
S = tuple(map(int, reversed(S)))
counter = Counter([0])
digit = 1
cumsum = 0

for i in range(len(S)):
    cumsum += S[i] * digit % MOD
    cumsum %= MOD
    counter[cumsum] += 1
    digit = digit * 10 % MOD

print(sum([v * (v - 1) // 2 for v in counter.values()]))

Submission status: Accepted

Solution code:
from collections import Counter

MOD = 2019
S = input()
S = tuple(map(int, reversed(S)))
counter = Counter()
digit = 1
cumsum = 0
ans = 0

for i in range(len(S)):
    counter[cumsum] += 1
    cumsum += (S[i] * digit) % MOD
    cumsum %= MOD
    ans += counter[cumsum]
    digit *= 10
    digit %= MOD

print(ans)

Submission status: Accepted

Solution code:
import sys
def main():
    s=sys.stdin.readline().strip()
    d,m,p,c={0:1},0,1,0
    for a in reversed(s):
        m+=(int(a)*p)
        k=m%2019
        p=(p*10)%2019
        d[k]=d[k]+1 if k in d else 1
    for v in d.values():c+=v*(v-1)//2
    print(c)
if __name__=='__main__':main()

Submission status: Accepted

Solution code:
import sys
def main():
    s=sys.stdin.readline().strip()
    x=[0 for _ in [0]*2020]
    x[0],c=1,0
    m,d=0,1
    for i in reversed(s):
        m+=(int(i)*d)
        x[m%2019]+=1
        d=(d*10)%2019
    for v in x:c+=v*(v-1)//2
    print(c)
if __name__=='__main__':main()

Submission status: Accepted

Solution code:
import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections
import copy
mod = 2019
if __name__ == "__main__":
    s = input()
    n = len(s)
    dp = [0]*(mod)
    dp[0] = 1
    r = 0
    t = 1
    for i in reversed(s):
        r += int(i)*t
        r%=mod
        t*=10
        t%=mod
        dp[r] +=1
    ans = 0
    for i in dp:
        ans += i*(i-1)//2
    print(ans)

Submission status: Accepted

Solution code:
from sys import stdin, stdout

s = input()
n = len(s)
P = 2019

# suffix_rems is a list of remainders obtained by dividing the suffix starting at i with P. suffix[i] = s[i:]%P.

suffix_rems = [-1]*n
suffix_rems[-1] = int(s[-1])%P

# Stores the frequency of remainders obtained. We just want number of (i, j) pairs.
rems_d = dict()
rems_d[0] = 1
rems_d[int(s[-1])] = 1

# Those remainders which occur more than once. To pick (i, j) pairs from N, we need N > 1.
special_keys = set()

for i in range(n-1)[::-1]:
    rem = (pow(10, n-i-1, P) * int(s[i]) + suffix_rems[i + 1])%P

    if rem in rems_d:
        rems_d[rem] += 1
        special_keys.add(rem)
    else:
        rems_d[rem] = 1

    suffix_rems[i] = rem

ans = 0
for key in special_keys:
    t = rems_d[key]
    # pick any two of those same remainder indices.
    ans += (t*(t-1))//2

print(ans)

Submission status: Accepted

Solution code:
import sys

# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    s = input()

    cnt = [0 for _ in range(2019)]
    cnt[0] += 1
    dec = 1
    num = 0
    for i in reversed(s):
        num += int(i) * dec
        num %= 2019
        dec *= 10
        dec %= 2019
        cnt[num] += 1

    ans = 0
    for c in cnt:
        ans += c * (c - 1) // 2

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from functools import reduce

def binom(n, r):
    if n < r or n < 0 or r < 0: return 0
    
    if n - r < r: r = n - r
    if r == 0: return 1
    elif r == 1: return n

    numerator = [n - r + 1 + k for k in range(r)]  # (n-r+1)*(n-r+2)*...*(n-1)*n
    denominator = [1 + k for k in range(r)]         # 1*2*...*(r-1)*r

    # reduce prod(numerator)//prod(denominator)
    for p in range(2, r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1, r, p):
                numerator[k - offset] //= pivot
                denominator[k] //= pivot
    
    # calculate nCr
    return reduce(lambda x, y: x*y, numerator)

S = input()
cnt = [0] * 2019; cnt[0] += 1
t = 0
for i, s in enumerate(S[::-1]):
    t += int(s) * pow(10, i, 2019); t %= 2019
    cnt[t] += 1
ans = 0
for i in range(2019):
    if cnt[i] >= 2: ans += binom(cnt[i], 2)
print(ans)

Submission status: Accepted

Solution code:
import sys
from math import sqrt, gcd, ceil, log
from bisect import bisect
from collections import defaultdict
inp = sys.stdin.readline
read = lambda: list(map(int, inp().strip().split()))

# sys.setrecursionlimit(10**6)



def solve():
	s = inp().strip();
	dic = defaultdict(int); dic[0] = 1
	# sett.add(0)
	ans = 0; cum = 0
	for i in range(len(s)-1, -1, -1):
		cum += (int(s[i])*pow(10, (len(s)-i-1), 2019)) % 2019
		cum %= 2019
		dic[cum] += 1
	# print(dic)
	for i in dic:
		ans += ((dic[i])*(dic[i]-1))//2
	print(ans)






if __name__ == "__main__":
	solve()

Submission status: Accepted

Solution code:
s = input()
s = list(reversed(s))
n = len(s)
dp1 = [0]*n
dp2 = [0]*n
counting = [0]*2019
counting[0] += 1
dp1[0] = 1
dp2[0] = int(s[0])
counting[dp2[0]] += 1
if n >= 2:
    for i in range(1,n):
        dp1[i] = (10*dp1[i-1]) % 2019
        dp2[i] = (int(s[i])*dp1[i]+dp2[i-1]) % 2019
        counting[dp2[i]] += 1
sm = 0
for j in range(2019):
    sm += int(counting[j]*(counting[j]-1)/2)
print(sm)

Submission status: Accepted

Solution code:
from collections import Counter
s = input()
MOD = 2019
ts = [0]
cur = 0
for i, j in enumerate(s[::-1], 1):
    cur = (cur + pow(10, i, MOD) * int(j)) % MOD
    ts.append(cur)
ct = Counter(ts)
res = 0
for k, v in ct.items():
    if v > 1:
        res += v * (v-1) // 2
print(res)

Submission status: Accepted

Solution code:
S = input()
r = 1
arr = [0]

for c in S[::-1]:
  arr.append((arr[-1] + int(c) * r) % 2019)
  r *= 10
  r %= 2019
from collections import Counter
ctr = Counter(arr)
ans = 0
for v in ctr.values():
  ans += v*(v-1)//2
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin

def nC2(n):
    return n*(n-1)//2

def main():
    #入力
    readline=stdin.readline
    s=readline().strip()

    d=dict()
    p=1
    t=0
    for i in range(len(s)-1,-1,-1):
        n=int(s[i])
        m=(n*p+t)%2019
        t=m
        p*=10
        p%=2019
        if m not in d:
            d[m]=1
        else:
            d[m]+=1
        
    if 0 in d:
        ans=d[0]
    else:
        ans=0
    for v in d.values():
        ans+=nC2(v)
    print(ans)
    
if __name__=="__main__":
    main()