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:
# -*- coding:utf-8 -*-

def solve():
    MOD = 2019
    S = input()

    """解説AC"""
    # A列を作成
    As = []
    d = 1
    for moji in S[::-1]:
        a = (int(moji)*d)%MOD
        As.append(a)
        d = (d*10)%MOD

    # 累積和を作成
    ruiseki = [0]
    for i, a in enumerate(As):
        r = (ruiseki[i] + a)%MOD
        ruiseki.append(r)

    # ruiseki[i] ≡ ruiseki[j] (mod 2019) となる総数を数える
    ruiseki_dic = {}  # combinationの計算でもいける
    ans = 0
    for r in ruiseki:
        if not r in ruiseki_dic:
            ruiseki_dic[r] = 1
        else:
            ans += ruiseki_dic[r]
            ruiseki_dic[r] += 1

    print(ans)



if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
s = input()
mod = 2019
digit = 1
mstack = 0
l = [0]*mod
l[0] = 1
ans = 0

for i in s[::-1]:
    mstack += int(i)*digit
    mstack %= mod
    l[mstack] += 1

    digit *= 10
    digit %= mod

for i in l:
    ans += i*(i - 1)//2

print(ans)

Submission status: Accepted

Solution code:
import sys

s = sys.stdin.buffer.readline().rstrip().decode()
MOD = 2019
ans = [1] + [0 for i in range(MOD)]
t = 1
r = 0
for i in reversed(s):
    r = (r + int(i)*t) % MOD
    t = t*10%2019
    ans[r] += 1
print(sum([m*(m-1)//2 for m in ans]))

Submission status: Accepted

Solution code:
from collections import Counter
s = input()
n = len(s)
dp = [0]*(n+1)
mod = 2019
for i in range(n-1,-1,-1):
    dp[i] = (dp[i+1]+int(s[i])*pow(10,n-i-1,mod))%mod
c = Counter(dp)
ans = 0
for i in c.values():
    ans += i*(i-1)//2
print(ans)

Submission status: Accepted

Solution code:
s = input()
counter = [0]*2019
counter[0] = 1
ans = 0
res, d = 0, 1
for i in range(len(s)-1, -1, -1):
    res = (res+int(s[i])*d)%2019
    counter[res] += 1
    d = d*10%2019
for count in counter:
    ans += count*(count-1)//2
print(ans)

Submission status: Accepted

Solution code:
S = list(input())[::-1]
ans = 0
mods = [0] * 2019
mods[0] = 1  # If 2019 is exist, count number
current = 0
x = 1
for s in S:
    current = (current + x * int(s)) % 2019
    ans += mods[current]
    mods[current] += 1
    x = x * 10 % 2019

print(ans)

Submission status: Accepted

Solution code:
s = input()
modl = [0]*2019
modl[0] = 1
mstack = 0
digit = 1
ans = 0

for i in s[::-1]:
    mstack += int(i) * digit
    mstack %= 2019
    modl[mstack] += 1
    digit = digit*10%2019

for i in modl:
    ans += i*(i - 1)//2

print(ans)

Submission status: Accepted

Solution code:
s = input()
modl = [0]*2019
modl[0] = 1
mstack = 0
digit = 1
ans = 0

for i in range(1, len(s) + 1):
    mstack += int(s[-i]) * digit
    mstack %= 2019
    modl[mstack] += 1
    digit = digit*10%2019

for i in modl:
    ans += i*(i - 1)//2

print(ans)

Submission status: Accepted

Solution code:
S = input()
Sliststr = list(S)
Slist = [int(s) for s in Sliststr]
Smod = [0]
mod10 = [1]
count = [0]*2019
ans = 0
for i in range(len(S)-1):
  mod10.append(mod10[i]*10%2019)
for i in range(len(S)):
  Smod.append((Smod[i]+Slist[-i-1]*mod10[i])%2019)
for i in range(len(Smod)):
  count[Smod[i]] += 1
for i in range(2019):
  ans += count[i] * (count[i]-1) // 2
print(ans)

Submission status: Accepted

Solution code:
S = input()
N = len(S)
ms = [1]
for i in range(N):
  m = ms[-1]*10%2019
  ms.append(m)
Rs = [0]
for i in range(N):
  c = int(S[N-i-1])
  R = (Rs[-1]+c*ms[i])%2019
  Rs.append(R)
NRs = {}
for R in Rs:
  if R not in NRs:
    NRs[R] = 0
  NRs[R] += 1
r = 0
for R in NRs:
  N = NRs[R]
  r += N*(N-1)//2
print(r)

Submission status: Accepted

Solution code:
from collections import Counter
s = input()
n = len(s)
dp = [0]
mod = 2019
a = 0
for i in range(n):
    a = a + int(s[n-i-1]) * pow(10, i, mod)
    a %= mod
    dp.append(a%mod)
ans = 0
c = Counter(dp)
for value in c.values():
    ans += value * (value-1) / 2
print(int(ans))

Submission status: Accepted

Solution code:
from collections import Counter

def solve_baka(s: str):
    ans = 0
    for i in range(len(s)):
        for j in range(i+1, len(s)+1):
            if int(s[i:j]) % 2019 == 0:
                print(i, j)
                ans += 1

    return ans


def main():
    s = input()
    sr = s[::-1]
    tn = [0]

    m = 1
    for i in range(len(s)):
        tn.append((tn[i]+int(sr[i])*m) % 2019)
        m = m * 10 % 2019

    ans = 0
    for _, v in Counter(tn).items():
        if v > 1:
            ans += v * (v - 1) // 2
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
S=list(map(int,input()))
L=len(S)
M=2019
d=10

U=[]
for x in range(L):
    if x==0:
        U=[1]
    else:
        U.append((U[-1]*d)%M)
        
T=[0]
for x in range(1,L+1):
    T.append((T[-1]+S[-x]*U[x-1])%M)

D={}
for x in T:
    if x in D:
        D[x]+=1
    else:
        D[x]=1

r=0
for x in D.values():
    r+=(x*(x-1))//2

print(r)

Submission status: Accepted

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


MOD = 2019
dp = [0] * MOD
dp[0] += 1

rem = 0
base = 1
for i in range(n):
    d = int(s[n-i-1])
    rem = (rem + base * d) % MOD
    # print((i, d, rem))
    dp[rem] += 1
    base *= 10
    base %= MOD

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

Submission status: Accepted

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

def main():
    s = input().strip()
    mod = [0] * 2019

    tmp = 0
    ten = 10
    mod[tmp] += 1
    for i in range(len(s)-1, -1, -1):
        tmp = (tmp + ten * int(s[i])) % 2019
        ten = (ten * 10) % 2019
        mod[tmp] += 1
    ans = 0
    for i in range(2019):
        if mod[i] > 1:
            ans += (mod[i] * (mod[i] - 1)) // 2
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import defaultdict 
def main():
    s = readline().rstrip().decode()
    n = len(s)
    T = [0]
    P = 2019
    dd = defaultdict(int)
    dd[0] += 1
    for i in range(1, n+1):
        v = ((ord(s[-i])-ord('0'))*pow(10, i-1, P) + T[i-1])%P
        dd[v] += 1
        T.append(v)
    ans = 0
    for v in dd.values():
        ans += v*(v-1)//2
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
S = input()[::-1]
mod = 2019
d = defaultdict(int)
ruijo = 1
tmp = 0
for i in range(len(S)):
    tmp += int(S[i]) * ruijo % mod
    d[tmp % mod] += 1
    ruijo *= 10
    ruijo %= mod
ans = 0
for k, v in d.items():
    ans += v * (v - 1) // 2
    if k == 0:
        ans += v
print(ans)

Submission status: Accepted

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

dataset = [0]*2019
dataset[0] = 1

n = 0
d = 1

for i in s:
    n += int(i) * d
    a = n % 2019
    dataset[a] += 1
    d *= 10
    d %= 2019

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

print(count)

Submission status: Accepted

Solution code:
import collections
S=input()
l=len(S)
T,d=0,1
A=[0]*2019
A[0]=1
for i in range(l):
    T+=int(S[l-i-1])*d
    d*=10
    T%=2019
    d%=2019
    A[T]+=1
B=map(lambda x: x*(x-1)//2,A)
print(sum(B))

Submission status: Accepted

Solution code:
import collections
S=input()
l=len(S)
T,d=0,1
A=[0]*2019
A[0]=1
for i in range(l):
    T+=int(S[l-i-1])*d
    d*=10
    T%=2019
    d%=2019
    A[T]+=1
ans=0
for cnt in A:
    ans+=cnt*(cnt-1)//2
print(ans)

Submission status: Accepted

Solution code:
import collections
S=input()[::-1]
l=len(S)
T,d=0,1
A=[0]*2019
A[0]=1
for i in range(l):
    T+=int(S[i])*d
    d*=10
    T%=2019
    d%=2019
    A[T]+=1
ans=0
for cnt in A:
    ans+=cnt*(cnt-1)//2
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict as de


readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prl = lambda x: print(*x ,sep='\n')

s = ns()
digit = 1
ans = 0
num = 0
amari = de(int)
amari[0] = 1
"""
大筋のやり方は
https://drken1215.hatenablog.com/entry/2020/04/29/171300
を参照。

「この下のfor文について」
1211400を考える。
1万の桁を考えるとき
digit = 10000
digit = 1924 mod 2019
11400 = 10000 + 1400 = 1924 + 1400 = ans mod 2019
つまり、ある桁までの2019のあまりはその一つ下の桁までのあまりと
その桁の数*桁のあまりを足したもののあまりである
"""

for i in s[::-1]:
    num = num + int(i) * digit
    num %= 2019
    digit *= 10
    digit %= 2019
    amari[num] += 1

for j in amari.values():
    ans += j*(j-1)//2

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

s = input()

rests = [0]
n = 0
a = 0
m = 1
c = defaultdict(int)
c[0] += 1
for i in list(s)[::-1]:
    n = n + int(i)*m

    c[n % 2019] += 1
    m = m * 10 % 2019

for v in c.values():
    a += v * (v-1) // 2
print(a)

Submission status: Accepted

Solution code:
S = input()
from collections import defaultdict
dic = defaultdict(int)
dic[0] += 1
# 後ろから見たほうがいい？
S = S[::-1]
d = 1
now = 0
for i in range(len(S)):
    # 2019で割ったあまりで集計する
    now += d*int(S[i]) % 2019
    dic[now%2019] += 1
    d *= 10
    d %= 2019
ans = 0
for k,v in dic.items():
    ans += v*(v-1)//2
print(ans)

Submission status: Accepted

Solution code:
import sys
tmp=sys.stdin.readline().rstrip()
def main():
   ans=0
   cnt=[0]*2019
   cnt[0]+=1
   t=0
   d=1
   for i in reversed(tmp):
      t=(t+int(i)*d)%2019
      cnt[t]+=1
      d=d*10%2019
   for i in cnt:
      ans+=i*(i-1)//2
   print(ans)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import Counter

S = input()
MOD = 2019
div10 = 202  # modInverse(10, MOD). Note MOD is not prime so can't use FLT!


def solve1(S):
    # Naive implementation
    counts = [0 for i in range(MOD)]
    total = 0
    for d in S:
        d = int(d)
        nextCounts = [0 for i in range(MOD)]
        nextCounts[d] += 1
        for k, v in enumerate(counts):
            nextCounts[(10 * k + d) % MOD] += v
        counts = nextCounts
        total += counts[0]
    return total


def solve2(S):
    # Instead of shuffling the entire counts, update how we index into counts instead
    # The cumulative shuffle function forward is something like a * index + b for some calculable a, b
    # Then indexing into counts[t][x] is same as indexing into counts[0][(x - b) / a]

    negPowTen = 1  # our a
    prefix = 0  # our b
    counts = [0 for i in range(MOD)]
    total = 0
    for d in S:
        d = int(d)
        prefix = (10 * prefix + d) % MOD
        negPowTen = (negPowTen * div10) % MOD
        counts[((d - prefix) * negPowTen) % MOD] += 1
        total += counts[((0 - prefix) * negPowTen) % MOD]
    return total


def solve3(S):
    # Alternative solution, precompute prefixes, p[i+1] == (10 * p[i] + S[i]) % MOD
    # Then you have for S = '1817181712114'
    # p[1] = 1
    # p[2] = 18
    # p[3] = 181
    # p[4] = 1817
    # etc
    # Then want to count all i j such that:
    # (p[j] - p[i] * pow(10, j - i)) % M == 0
    # Which is equivalent to
    # (p[j] * pow(10, -j) - p[i] * pow(10, -i) % M == 0
    negPowTen = 1
    total = 0
    prefix = 0
    counts = [0 for i in range(MOD)]
    counts[0] = 1
    for d in S:
        prefix = (prefix * 10 + int(d)) % MOD
        key = (prefix * negPowTen) % MOD
        total += counts[key]
        counts[key] += 1
        negPowTen = (negPowTen * div10) % MOD

    return total


def solve4(S):
    # Compute all suffixes instead
    # S     = '1817181712114'
    # suf[1] =             4
    # suf[2] =            14
    # suf[3] =           114
    # suf[4] =          2114
    #
    # Difference of suffixes is almost correct but has extra 10s.
    # For example 2114 to 114 is the string 2 but our difference returns 2000.
    # Luckily 2 and 5 aren't divisible by 2019 so the extra 10s don't matter when counting.
    N = len(S)
    suf = 0
    powTen = 1
    counts = [0 for i in range(MOD)]
    total = 0
    counts[0] = 1
    for i in range(N):
        d = int(S[N - 1 - i])
        suf = (powTen * d + suf) % MOD
        total += counts[suf]
        counts[suf] += 1
        powTen = (powTen * 10) % MOD
    return total


#assert solve1(S) == solve2(S) == solve3(S) == solve4(S)
ans = solve4(S)
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

S = input()
MOD = 2019
div10 = 202  # modInverse(10, MOD). Note MOD is not prime so can't use FLT!


def solve1(S):
    # Naive implementation
    counts = [0 for i in range(MOD)]
    total = 0
    for d in S:
        d = int(d)
        nextCounts = [0 for i in range(MOD)]
        nextCounts[d] += 1
        for k, v in enumerate(counts):
            nextCounts[(10 * k + d) % MOD] += v
        counts = nextCounts
        total += counts[0]
    return total


def solve2(S):
    # Instead of shuffling the entire counts, update how we index into counts instead
    # The cumulative shuffle function forward is something like a * index + b for some calculable a, b
    # Then indexing into counts[t][x] is same as indexing into counts[0][(x - b) / a]

    negPowTen = 1  # our a
    prefix = 0  # our b
    counts = [0 for i in range(MOD)]
    total = 0
    for d in S:
        d = int(d)
        prefix = (10 * prefix + d) % MOD
        negPowTen = (negPowTen * div10) % MOD
        counts[((d - prefix) * negPowTen) % MOD] += 1
        total += counts[((0 - prefix) * negPowTen) % MOD]
    return total


def solve3(S):
    # Alternative solution, precompute prefixes, p[i+1] == (10 * p[i] + S[i]) % MOD
    # Then you have for S = '1817181712114'
    # p[1] = 1
    # p[2] = 18
    # p[3] = 181
    # p[4] = 1817
    # etc
    # Then want to count all i j such that:
    # (p[j] - p[i] * pow(10, j - i)) % M == 0
    # Which is equivalent to
    # (p[j] * pow(10, -j) - p[i] * pow(10, -i) % M == 0
    negPowTen = 1
    total = 0
    prefix = 0
    counts = [0 for i in range(MOD)]
    counts[0] = 1
    for d in S:
        prefix = (prefix * 10 + int(d)) % MOD
        key = (prefix * negPowTen) % MOD
        total += counts[key]
        counts[key] += 1
        negPowTen = (negPowTen * div10) % MOD

    return total


def solve4(S):
    # Compute all suffixes instead
    # S     = '1817181712114'
    # suf[1] =             4
    # suf[2] =            14
    # suf[3] =           114
    # suf[4] =          2114
    #
    # Difference of suffixes is almost correct but has extra 10s.
    # For example 2114 to 114 is the string 2 but our difference returns 2000.
    # Luckily 2 and 5 aren't divisible by 2019 so the extra 10s don't matter when counting.
    N = len(S)
    suf = 0
    powTen = 1
    counts = [0 for i in range(MOD)]
    total = 0
    counts[0] = 1
    for i in range(N):
        d = int(S[N - 1 - i])
        suf = (powTen * d + suf) % MOD
        total += counts[suf]
        counts[suf] += 1
        powTen *= 10
    return total


#assert solve1(S) == solve2(S) == solve3(S) == solve4(S)
ans = solve3(S)
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

S = input()
MOD = 2019
div10 = 202  # modInverse(10, MOD). Note MOD is not prime so can't use FLT!


def solve1(S):
    # Naive implementation
    counts = [0 for i in range(MOD)]
    total = 0
    for d in S:
        d = int(d)
        nextCounts = [0 for i in range(MOD)]
        nextCounts[d] += 1
        for k, v in enumerate(counts):
            nextCounts[(10 * k + d) % MOD] += v
        counts = nextCounts
        total += counts[0]
    return total


def solve2(S):
    # Instead of shuffling the entire counts, update how we index into counts instead
    # The cumulative shuffle function forward is something like a * index + b for some calculable a, b
    # Then indexing into counts[t][x] is same as indexing into counts[0][(x - b) / a]

    negPowTen = 1  # our a
    prefix = 0  # our b
    counts = [0 for i in range(MOD)]
    total = 0
    for d in S:
        d = int(d)
        prefix = (10 * prefix + d) % MOD
        negPowTen = (negPowTen * div10) % MOD
        counts[((d - prefix) * negPowTen) % MOD] += 1
        total += counts[((0 - prefix) * negPowTen) % MOD]
    return total


def solve3(S):
    # Alternative solution, precompute prefixes, p[i+1] == (10 * p[i] + S[i]) % MOD
    # Then you have for S = '1817181712114'
    # p[1] = 1
    # p[2] = 18
    # p[3] = 181
    # p[4] = 1817
    # etc
    # Then want to count all i j such that:
    # (p[j] - p[i] * pow(10, j - i)) % M == 0
    # Which is equivalent to
    # (p[j] * pow(10, -j) - p[i] * pow(10, -i) % M == 0
    negPowTen = 1
    total = 0
    prefix = 0
    counts = [0 for i in range(MOD)]
    counts[0] = 1
    for d in S:
        prefix = (prefix * 10 + int(d)) % MOD
        key = (prefix * negPowTen) % MOD
        total += counts[key]
        counts[key] += 1
        negPowTen = (negPowTen * div10) % MOD

    return total


def solve4(S):
    # Compute all suffixes instead
    # S     = '1817181712114'
    # suf[1] =             4
    # suf[2] =            14
    # suf[3] =           114
    # suf[4] =          2114
    #
    # Difference of suffixes is almost correct but has extra 10s.
    # For example 2114 to 114 is the string 2 but our difference returns 2000.
    # Luckily 2 and 5 aren't divisible by 2019 so the extra 10s don't matter when counting.
    N = len(S)
    suf = 0
    powTen = 1
    counts = [0 for i in range(MOD)]
    total = 0
    counts[0] = 1
    for i in range(N):
        d = int(S[N - 1 - i])
        suf = (powTen * d + suf) % MOD
        total += counts[suf]
        counts[suf] += 1
        powTen *= 10
    return total


#assert solve1(S) == solve2(S) == solve3(S) == solve4(S)
ans = solve2(S)
print(ans)

Submission status: Accepted

Solution code:
s=input()
dic={}
cur=0
power=0
for i in range(0,len(s)+1):
  s_int=len(s)-i-1
  if cur in dic:
    dic[cur]+=1
  else:
    dic[cur]=1
  try:
    num=int(s[s_int])
    cur+=num*pow(10,power,2019)
    cur%=2019
    power+=1
  except IndexError:
    break

res=0
for i in range(len(dic)):
  t=dic.popitem()
  cc=t[1]
  res+=cc*(cc-1)//2
print(res)

Submission status: Accepted

Solution code:
s = list(input())
sur_list = [0 for i in range(2019)]
sur = 0
keta = 1
ans = 0

s.reverse()

for i in range(len(s)):
    keta = (keta*10)%2019
    sur_list[sur] += 1
    sur = (int(s[i]) * keta + sur) % 2019
    ans += sur_list[sur]

print(ans)

Submission status: Accepted

Solution code:
s=[int(x) for x in list(input())]
for c in range(len(s)-1,-1,-1):
    if c==len(s)-1:
        continue
    s[c]=(pow(10,len(s)-c-1,2019)*s[c]+s[c+1])%2019
s.append(0)
s.sort()
h=[1]
d=s[0]
for c in range(1,len(s)):
    if s[c]!=d:
        h.append(1)
        d=s[c]
    else:
        h[-1]+=1
k=[(x*(x-1))//2 for x in h]
print(sum(k))

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline
P = 2019


def main():
    S = input().rstrip()

    count = [0] * P
    count[0] += 1
    T = 0
    d = 1
    for s in reversed(S):
        T = (T + int(s) * d) % P
        count[T] += 1
        d = (d * 10) % P

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline
P = 2019


def main():
    S = input().rstrip()

    N = len(S)
    count = [0] * P
    count[0] += 1
    T = 0
    for i in range(N):
        T = (T + int(S[(N - 1) - i]) * pow(10, i, mod=P)) % P
        count[T] += 1

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
MOD = 2019

def solve(S):
    N = len(S)
    dp = [0 for _ in range(MOD)]
    tmp = 0
    ret = 0
    for i in range(N - 1, -1, -1):
        m = (tmp + int(S[i]) * pow(10, N - i - 1, MOD)) % MOD
        ret += dp[m]
        dp[m] += 1
        tmp = m
    ret += dp[0]
    return ret

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

Submission status: Accepted

Solution code:
MOD = 2019

def solve(S):
    N = len(S)
    dp = [0 for _ in range(MOD)]
    tmp = 0
    ret = 0
    for i in range(N):
        m = (tmp + int(S[i]) * pow(10, N - i - 1, MOD)) % MOD
        ret += dp[m]
        dp[m] += 1
        tmp = m
    ret += dp[0]
    return ret

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

Submission status: Accepted

Solution code:
s=list(map(int,list(input())[::-1]))
n=len(s)
cnt=[0]*2019
cnt[0]+=1
c=0
for i in range(n):
  c+=s[i]*pow(10,i,2019)%2019
  cnt[c%2019]+=1
ans=0
for i in cnt:
  if i<=1:
    pass
  else:
    ans+=i*(i-1)//2
print(ans)

Submission status: Accepted

Solution code:
s = input()
s = s[::-1]
m = [0] * 2019
m[0] = 1
a = 0
d = 1
ans = 0
for si in s:
    a = (a + int(si) * d) % 2019
    d = (d * 10) % 2019
    ans += m[a]
    m[a] += 1
print(ans)

Submission status: Accepted

Solution code:
s = input()
s = s[::-1]
n = len(s)
m = [0] * 2019
m[0] = 1
a = 0
d = 1
for i in range(n):
    a = (a + int(s[i]) * d) % 2019
    d = (d * 10) % 2019
    m[a] += 1
print(sum([int(x * (x - 1) / 2) for x in m if x > 1]))

Submission status: Accepted

Solution code:
s=input()
a=0
m={}
d=1
for i in range(len(s)):
  b=int(s[len(s)-1-i])*d+a
  b=b%2019
  a=b
  d=d*10%2019
  if b in m:
    m[b]+=1
  else:
    m[b]=1
if 0 in m:
  sum=m[0]
else:
  sum=0
for i in m:
  sum+=m[i]*(m[i]-1)/2
print(int(sum))

Submission status: Accepted

Solution code:
# int(input()) # 入力が1つ
# map(int, input().split()) # 入力が複数
# [int(i) for i in input().split()] # 配列で数字

def nC2(n):
    return n * (n - 1) // 2
s = input()
n = len(s)
dp = [0] * 2020
mod = 2019
temp = 0
dp[0] = 1
for i in range(n):
    m = (int(s[i]) * pow(10, n - i - 1, mod) + temp)% mod
    dp[m] += 1
    temp = m
ans = 0
for i in range(2020):
    if dp[i]:
        ans += nC2(dp[i])
print(ans)

Submission status: Accepted

Solution code:
s=input()
n=len(s)
a=0
t=1
d=[1]+[0]*2018
 
for i in range(n):
    a+=int(s[n-1-i])*t
    a%=2019
    t*=10
    t%=2019
    
    d[a]+=1

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

Submission status: Accepted

Solution code:
S = input()
amari = [0]*2019
ans = 0
amari[0] = 1
A = 0
for i in range(len(S)):
    A += pow(10, i, 2019)*(int(S[len(S)-1-i]))
    amari[A % 2019] += 1
for i in amari:
    if i >= 2:
        ans += i*(i-1)/2
print(int(ans))

Submission status: Accepted

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

S_mod = [0] * (len(S)+1)
S_mod[0] = int(S[0])

d = 10

for i in range(len(S)-1):
    S_mod[i + 1] = (S_mod[i] + int(S[i+1])*d)%2019
    d = d * 10 % 2019

mod_count = [0] * 2019
for i in range(len(S_mod)):
    mod_count[S_mod[i]] += 1
    
count = 0
for i in range(2019):
    count += mod_count[i] * (mod_count[i] - 1) / 2

print(int(count))

Submission status: Accepted

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

S_mod = [0] * (len(S)+1)
S_mod[0] = int(S[0])

mod_count = [0] * 2019

d = 10

#for i in range(len(S)):
#    S_mod[i] = int(S[i:len(S)])%2019

for i in range(len(S)-1):
    S_mod[i + 1] = (S_mod[i] + int(S[i+1])*d)%2019
    d = d * 10 % 2019
    
#print(S_mod)

for i in range(len(S_mod)):
    mod_count[S_mod[i]] += 1

#print(mod_count)
    
count = 0
for i in range(2019):
    count += mod_count[i] * (mod_count[i] - 1) / 2
    
print(int(count))

#S = list(map(int, list(input())))

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit


def main():
    mod = 2019
    input = stdin.buffer.readline
    s = list(map(int, list(input()[:-1].decode())))
    n = len(s)
    s.reverse()

    tmp_p10 = 1
    p10 = [tmp_p10]
    for _ in range(1, n + 1):
        tmp_p10 *= 10
        tmp_p10 %= mod
        p10.append(tmp_p10)

    tmp_mod = s[0] % mod
    mods = [0, tmp_mod]
    for i in range(1, n):
        tmp_mod = (s[i] * p10[i] + tmp_mod) % mod
        mods.append(tmp_mod)
    m2019 = [0] * 2019
    for mi in mods:
        m2019[mi] += 1
    ans = 0
    for mi in m2019:
        ans += mi * (mi - 1) // 2

    print(ans)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Accepted

Solution code:
def abc164_d():
    # 解説放送
    s = str(input())
    n = len(s)
    m = 2019
    srev = s[::-1]  # 下の位から先に見ていくために反転する
    x = 1  # 10^i ??
    total = 0  # 累積和 (mod 2019 における累積和)
    cnt = [0] * m  # cnt[k] : 累積和がkのものが何個あるか
    ans = 0
    for i in range(n):
        cnt[total] += 1
        total += int(srev[i]) * x
        total %= m
        ans += cnt[total]
        x = x*10 % m
    print(ans)

abc164_d()

Submission status: Accepted

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

cnts = [0] * 2019
cnts[0] = 1

n, d = 0, 1

for char in s:
    n = (n + int(char) * d) % 2019
    d = d * 10 % 2019
    cnts[n] += 1

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

print(ans)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
from collections import Counter
def main():
	s=input()
	len_s=len(s)
	T=[0]*(len_s+1)
	T[-1],T[-2]=0,int(s[-1])
	mod=2019
	for i in range(len_s-2,-1,-1):
		T[i]=(T[i+1]+int(s[i])*pow(10,len_s-i-1,mod))%mod
	tc=list(Counter(T).values())
	ans=0
	for tcc in tc:
		ans+=tcc*(tcc-1)//2
	print(ans)

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()
S=input()
n=len(S)
D=[0]*2019
T=[0]*(n+1)
T[0]=1
for i in range(n):
  T[i+1]=(T[i]*10)%2019

cur=0
keta=0
ans=0
D[0]+=1
for s in S[::-1]:
  cur=(cur+int(s)*T[keta])%2019
  ans+=D[cur]
  D[cur]+=1
  keta+=1
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

n = list(input())
n.reverse()
x = [0]*(len(n))
a=0
ex=1
for i in range(len(n)):
    a+=int(n[i])*ex
    x[i]=a%2019
    ex=ex*10%2019
c=Counter(x)
ans = c[0]
for i in c.keys():
    b=c[i]
    ans += b*(b-1)//2

print(ans)

Submission status: Accepted

Solution code:
S = list(str(input()))
S.reverse()
mod = 2019
rem = [0]*mod
num = 0
rem[num] += 1
d = 1
ans = 0
for s in S:
  num += int(s) * d
  num %= mod
  d *= 10
  d %= mod
  rem[num] += 1
for r in rem:
  ans += r*(r-1)//2
print(ans)

Submission status: Accepted

Solution code:
def main():
    from collections import Counter
    s = input()

    l = [0]
    t = 1
    for i, x in enumerate(s[::-1]):
        t = t * 10 % 2019
        y = (l[-1] + int(x) * t) % 2019
        l.append(y)

    c = Counter(l)
    ans = sum([v * (v - 1) // 2 for v in c.values()])
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    from collections import Counter
    from itertools import accumulate
    s = input()

    n = 2019
    l = [0]
    t = 1
    for i, x in enumerate(s[::-1]):
        t = t * 10 % n
        y = (l[-1] + int(x) * t) % n
        l.append(y)

    c = Counter(l)
    ans = accumulate([v * (v - 1) // 2 for v in c.values()])
    print(list(ans)[-1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    from collections import Counter
    s = input()

    n = 2019
    l = [0]
    t = 1
    for i, x in enumerate(s[::-1]):
        t = t * 10 % n
        y = (l[-1] + int(x) * t) % n
        l.append(y)

    c = Counter(l)
    ans = sum([v * (v - 1) // 2 for v in c.values()])
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
MOD = 2019
def main():
    S = input()
    dp = [0] * (len(S)+1)
    ex = 1
    for i in range(len(S)):
        dp[i+1] = (int(S[-1-i])*ex + dp[i]) % MOD
        ex *= 10
        ex %= MOD
    d = defaultdict(int)
    for i in range(len(S)+1):
        d[dp[i]] += 1
    output = 0
    for i in d.keys():
        output += (d[i] * (d[i]-1) // 2)
    print(output)
    return

if __name__ == '__main__':
    main()

Submission status: Accepted

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

cum = [0]*n
cum[n-1] = int(s[-1]) % mod
d = [1]*n
for i in range(n-1)[::-1]:
    d[i] = d[i+1]*10%mod

for i in range(0, n-1)[::-1]:
    a = int(s[i]) * d[i] % mod
    cum[i] = (cum[i+1]+a) % mod
cnt = [0]*mod

ans = 0
for i in cum[::-1]:
    ans += cnt[i]
    cnt[i] += 1
    if i == 0:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#D

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

s = input()
n = len(s)
t = []
for i in range(n):
    t.append(int(s[i])*pow(10, (n-i-1), 2019) % 2019)
t = list(accumulate(t))
t = [0] + [i % 2019 for i in t]
ans = 0
cnt = defaultdict(int)
for i in range(n+1):
    ans += cnt[t[i]]
    cnt[t[i]] += 1
print(ans)

Submission status: Accepted

Solution code:
def main():
    import collections
    s=list(map(int,input()))
    modpow=[1]*len(s)
    for i in range(1,len(s)):
        modpow[i]=(modpow[i-1]*10)%2019
    ans=0
    res=[0]*len(s)
    res[0]=s[-1]%2019
    for i in range(1,len(s)):
        res[i]=(modpow[i]*s[len(s)-1-i]+res[i-1])%2019
    res.append(0)
    c=collections.Counter(res).most_common()
    for i in range(len(c)):
        ans+=(c[i][1]*(c[i][1]-1)//2)
    print(ans)
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
s = input()
s = s[::-1]
l = len(s)
se = dict()

k = 0
for i in range(0,l):
    k+=(pow(10,i,2019)*int(s[i]))
    k%=2019
    if k in se:
        se[k]+=1
    else:
        se[k]=1

ans=0
for j in se:
    i=se[j]
    if i>1:
        ans+=(i*(i-1)//2)
    if j==0:
        ans+=i
print(ans)

Submission status: Accepted

Solution code:
s=input()
l=len(s)
se=dict()
k=0
for i in range(l-1,-1,-1):
    k+=(pow(10,l-1-i,2019)*int(s[i]))
    k%=2019
    if k in se:
        se[k]+=1
    else:
        se[k]=1

ans=0
for j in se:
    i=se[j]
    if i>1:
        ans+=(i*(i-1)//2)
    if j==0:
        ans+=i
print(ans)

Submission status: Accepted

Solution code:
M = 2019
s = input()
tot, ten, ans = 0, 1, 0
cnt = [0] * M
for si in s[::-1]:
    cnt[tot] += 1
    tot += int(si) * ten
    tot %= M
    ans += cnt[tot]
    ten *= 10
    ten %= M
print(ans)

Submission status: Accepted

Solution code:
# D
# Multiple of 2019
import itertools

s = input()[::-1]

d = len(s)

# _list = [None]*d
_map = [0]*2019
_map[0] = 1

ans = 0
j,_ = 1,0

for i in s:
    _ += int(i) * j
    _tmp = _ % 2019
    j = (j*10)%2019
    _map[_tmp] += 1
    
for _l in _map:
    ans += _l * (_l - 1) / 2
    
print(int(ans))

Submission status: Accepted

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

n = len(s)
cnt = [0] * 2019
cnt[0] = 1
total = 0
ans = 0
x = 1

for i in range(n):
    total += int(s[i]) * x
    total %= 2019
    x *= 10
    x %= 2019
    ans += cnt[total]
    cnt[total] += 1

print(ans)