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: Time Limit Exceeded

Solution code:
from collections import Counter

# print('input >>')

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

mods = [0] * (len(S)+1)
mods[0] = int(S[0]) % 2019

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

# print(mods)

ans = 0

counter = Counter(mods)

for c, n in counter.most_common():
    if n > 1:
        ans += (n * (n-1)) // 2

# print('-----output-----')

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

dp=[[0]*2019 for _ in range(2)]
dig=[int(c) for c in sys.stdin.readline().strip()]
tab=[[0]*2019 for _ in range(10)]

for x in range(10):
    for i in range(2019):
        tab[x][i]=(i*10+x)%2019

p=0
cnt=0
for x in dig:
    np=(p+1)&1
    for i in range(2019):
        dp[np][tab[x][i]]=dp[p][i]
    dp[np][x]+=1
    p=np
    cnt+=dp[p][0]

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
S = input()

cnt = 0
for j in range(1, len(S)+1):
    for i in range(j-1):
        part = int(S[i:j])
        if not part % 3 == 0:
            continue
        if part % 2019 == 0:
            cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys

dp=[[0]*2019 for _ in range(2)]
dig=[int(c) for c in sys.stdin.readline().strip()]

p=0
cnt=0
for x in dig:
    np=(p+1)&1
    for i in range(2019):
        dp[np][(i*10+x)%2019]=dp[p][i]
    dp[np][x]+=1
    p=np
    cnt+=dp[p][0]

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys

dp=[[0]*2019 for _ in range(2)]

p=0
cnt=0
for c in sys.stdin.readline().strip():
    x=int(c)

    for i in range(2019):
        dp[(p+1)&1][(i*10+x)%2019]=dp[p][i]
    dp[(p+1)&1][x]+=1
    p=(p+1)&1
    cnt+=dp[p][0]

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
dp=[[0]*2019 for _ in range(2)]

p=0
cnt=0
for c in input():
    x=int(c)

    for i in range(2019):
        dp[(p+1)&1][(i*10+x)%2019]=dp[p][i]
    dp[(p+1)&1][x]+=1
    p=(p+1)&1
    cnt+=dp[p][0]

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
S = input()

cnt = 0
for j in range(1, len(S)+1):
    for i in range(j-1):
        part = S[i:j]
        if int(part) % 2019 == 0:
            cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
#D
S = list(str(input()))
N = len(S)

U = []
for i in range(N):
    U.append(int(S[N-i-1]))


DP = [-1]*(N+1)
DP[0] = 0
now = 0
for i,u in enumerate(U):
    now+=int(u)*(10**i)
    now%=2019
    DP[i+1] = now
    
#print(DP)
tyo = [0]*2019
for dp in DP:
    tyo[dp]+=1

ans = 0
for t in tyo:
    ans+=(t*(t-1))//2
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
a = input()
count = 0
for i in range(len(a) - 3):
    for j in range(i+4,len(a) + 1):
        b = int(a[i:j])
        if b % 2019 == 0:
            count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
#D
S = list(str(input()))
N = len(S)
S = S[::-1]

DP = [-1]*(N+1)
DP[0] = 0
now = 0
for i in range(N):
    now+=int(S[i])*(10**i)
    now%=2019
    DP[i+1] = now
    
#print(DP)
tyo = [0]*2019
for dp in DP:
    tyo[dp]+=1

ans = 0
for t in tyo:
    ans+=(t*(t-1))//2
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
cnt = 0
t = input()
for i in range(len(t)):
  for j in range(len(t)):
    if j - i < 3:
      continue
    else:
      n = int(t[i:j+1])
      if n % 2019 == 0:
        cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
s_str = input()
# print(type(s_str))
# print()

list = []
for i in range(len(s_str)-1):
  s_new = s_str[i]
  for j in range(i, len(s_str)):
    if int(s_new) % 2019 == 0:
      list.append(s_new)
    j = j + 1
    if j == len(s_str):
      break
    else:
      s_new = s_new + s_str[j]
  i = i + 1

print(len(list))

Submission status: Time Limit Exceeded

Solution code:
from collections import *
s = input()
p = 2019
c = Counter()
c[0] += 1
v = r = 0
k = 1
for i in s[::-1]:
    v += int(i)*k
    r += c[v%p]
    c[v%p] += 1
    k *= 10
print(r)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
s = input()[::-1]
T = [0]*(len(s)+1)
digit = 1

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

S = Counter(T)
ans=0
for i in S.values():
    ans+=(i*(i-1))//2

print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()
counter = 0
for left in range(len(s)):
    mod = 0
    for right in range(left, len(s)):
        mod *= 10
        mod += int(s[right])
        mod %= 2019
        if mod == 0:
            counter += 1
print(counter)

Submission status: Time Limit Exceeded

Solution code:
S=input()
n=0
for s in range(len(S)+1):
  for i in range(s):
    if int(S[i:s])%2019==0:
       n+=1
print(n)

Submission status: Time Limit Exceeded

Solution code:
S = input()
N = len(S)
n = 0
for i in range(3, N):
  for j in range(0, i+1-3):
    if (int(S[j:i+1]))%2019 == 0:
      n += 1
print(n)

Submission status: Time Limit Exceeded

Solution code:
S = input()
N = len(S)
S = int(S)
list = [0] * 2019
list[0] = 1
ans = 0
for i in range(N):
	S = S % (10 ** (N - i))
	s = S % 2019
	ans += list[s]
	list[s] += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = input()
N = len(S)
S = int(S)
list = []
ans = 0
for i in range(N):
	S = S % (10 ** (N - i))
	s = S % 2019
	ans += list.count(s)
	list.append(s)
ans += list.count(0)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()
result = 0
n = len(s)
for i in range(n):
    for j in range(i,n):
        if int(s[i:j+1]) % 2019 == 0:
            result += 1

print(result)

Submission status: Time Limit Exceeded

Solution code:
def main():
    s = input()
    c = 0
    for i in range(len(s)-3):
        for j in range(i+3, len(s)):
            if int(s[i:j+1]) % 2019 == 0:
                c += 1

    print(c)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
s = input()
y = 2019
a = [0]*y
k = 1
r = 0
for i in range(len(s))[::-1]:
    j = int(s[i])*k%y
    tmp = [0]*y
    for i in range(2019):
        tmp[(i+j)%y] = a[i]
    tmp[j] += 1
    a = tmp
    r += a[0]
    k *= 10
    k %= y
print(r)

Submission status: Time Limit Exceeded

Solution code:
S=input()
N=len(S)
cnt=0
for i in range(N+1):
  for j in range(i+4,N+1):
    #print(S[i:j])
    if int(S[i:j])%2019==0:
      cnt+=1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
a=input()
num=len(a)
mod_map={0:1}
moji_int=0
Sn=[0]*(num+1)
tens=[1]*(num+1)
for i in range(-1,-num-1,-1):
    tens[-i]=tens[-i-1]*10
    tmp=int(a[i])*(tens[-i-1]%2019)
    Sn[-i]=(Sn[-i-1]+tmp%2019)%2019
    mod=Sn[-i]
    if mod not in mod_map:
        mod_map[mod]=1
    else:
        mod_map[mod]+=1

res=0
for i in mod_map.values():
    res+=int(i*(i-1)/2)
print(res)

Submission status: Time Limit Exceeded

Solution code:
a=input()
num=len(a)
mod_list=[1]+[0]*2019
moji_int=0
Sn=0
tens=1
for i in a[::-1]:
    tmp=int(i)*(tens%2019)
    Sn=(Sn+tmp%2019)%2019
    mod=Sn
    tens*=10
    mod_list[mod]+=1

res=0
for i in mod_list:
    res+=int(i*(i-1)/2)
print(res)

Submission status: Time Limit Exceeded

Solution code:
a=input()
num=len(a)
mod_map={0:1}
moji_int=0
Sn=0
tens=1
for i in a[::-1]:
    tmp=int(i)*(tens%2019)
    Sn=(Sn+tmp%2019)%2019
    mod=Sn
    tens*=10
    if mod not in mod_map:
        mod_map[mod]=1
    else:
        mod_map[mod]+=1


res=0
for i in mod_map.values():
    res+=int(i*(i-1)/2)
print(res)

Submission status: Time Limit Exceeded

Solution code:
a=input()
num=len(a)
mod_map={0:1}
moji_int=0
Sn=0
tens=1
for i in range(-1,-num-1,-1):
    tmp=int(a[i])*(tens%2019)
    Sn=(Sn+tmp%2019)%2019
    mod=Sn
    tens*=10
    if mod not in mod_map:
        mod_map[mod]=1
    else:
        mod_map[mod]+=1

res=0
for i in mod_map.values():
    res+=int(i*(i-1)/2)
print(res)

Submission status: Time Limit Exceeded

Solution code:
a=input()
num=len(a)
mod_map={0:1}
moji_int=0
Sn=0
tens=[1]*(num+1)
for i in range(-1,-num-1,-1):
    tens[-i]=tens[-i-1]*10
    tmp=int(a[i])*(tens[-i-1]%2019)
    Sn=(Sn+tmp%2019)%2019
    mod=Sn
    if mod not in mod_map:
        mod_map[mod]=1
    else:
        mod_map[mod]+=1

res=0
for i in mod_map.values():
    res+=int(i*(i-1)/2)
print(res)

Submission status: Time Limit Exceeded

Solution code:
a=input()
num=len(a)
mod_map={0:1}
mod_list=[1]+[0]*2019
moji_int=0
Sn=[0]*(num+1)
tens=[1]*(num+1)
for i in range(-1,-num-1,-1):
    tens[-i]=tens[-i-1]*10
    tmp=int(a[i])*(tens[-i-1]%2019)
    Sn[-i]=(Sn[-i-1]+tmp%2019)%2019
    mod=Sn[-i]
    mod_list[mod]+=1

res=0
for i in mod_list:
    res+=int(i*(i-1)/2)
print(res)

Submission status: Time Limit Exceeded

Solution code:
a=input()
num=len(a)
mod_map={0:1}
mod_list=[1]+[0]*2019
moji_int=0
Sn=[0]*(num+1)
tens=[1]*(num+1)
for i in range(-1,-num-1,-1):
    tens[-i]=tens[-i-1]*10
    tmp=int(a[i])*(tens[-i-1]%2019)
    Sn[-i]=(Sn[-i-1]+tmp%2019)%2019
    mod=Sn[-i]
    mod_list[mod]+=1

res=0
for i in mod_list:
    res+=int(i*(i-1)/2)
print(res)

Submission status: Time Limit Exceeded

Solution code:
a=input()
num=len(a)
mod_map={0:1}
moji_int=0
Sn=[0]*(num+1)
tens=[1]*(num+1)
for i in range(-1,-num-1,-1):
    tens[-i]=tens[-i-1]*10
    tmp=int(a[i])*(tens[-i-1]%2019)
    Sn[-i]=(Sn[-i-1]+tmp%2019)%2019
    mod=Sn[-i]
    if mod not in mod_map:
        mod_map[mod]=1
    else:
        mod_map[mod]+=1

res=0
for i in mod_map.values():
    res+=int(i*(i-1)/2)
print(res)

Submission status: Time Limit Exceeded

Solution code:
S = input()

len_S = len(S)

ans_count = 0

if len_S <= 4:
    if int(S)%2019 == 0:
        ans_count += 1
else:
    for i in range(0, len_S+1):
        for j in range(i+4, len_S+1):
            if int(S[i:j])%2019 == 0:
                ans_count += 1

print(ans_count)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
s = input()
n = len(s)
s = int(s)
store = defaultdict(int)
store[0] = 1
t = 0
prev_pow = 1
for i in range(n):
    a = s % 10
    s //= 10
    t += a*prev_pow 
    t %= 2019
    store[t] += 1
    prev_pow *= 10
    prev_pow %= 2019
ans = 0
for i in store:
    ans += store[i]*(store[i]-1)//2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = input()
from collections import defaultdict
d = defaultdict(int)
d[0] += 1

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

ans = 0
for v in d.values():
  if v >= 2:
    ans += v * (v-1)

print(ans // 2)

Submission status: Time Limit Exceeded

Solution code:
S = input()
from collections import defaultdict
d = defaultdict(int)
d[0] += 1

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

ans = 0
for v in d.values():
  ans += v * (v-1)

print(ans // 2)

Submission status: Time Limit Exceeded

Solution code:
def main():
    S = input()
    # S = "1" * 200000
    S = S[::-1]

    x = 1
    tot = 0
    cnt = [0] * 2019
    ans = 0

    for i in range(len(S)):
        # print("-----")
        # print(f"i: {i}")
        # print(f"tot: {tot}")
        # print(f"S[i]: {S[i]}")
        # print(f"x: {x}")
        # print(f"cnt: {cnt}")
        # print(f"cnt[tot]: {cnt[tot]}")
        # print(f"ans: {ans}")

        cnt[tot] += 1
        tot = (tot + (int(S[i]) * x)) % 2019
        ans += cnt[tot]
        x = x * 10
    
    # print("-----")
    # print(f"i: {i}")
    # print(f"tot: {tot}")
    # print(f"S[i]: {S[i]}")
    # print(f"x: {x}")
    # print(f"cnt: {cnt}")
    # print(f"cnt[tot]: {cnt[tot]}")
    # print(f"ans: {ans}")
    
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    S = input()
    # S = "1" * 200000
    S = S[::-1]

    x = 1
    tot = 0
    cnt = [0] * 2019
    ans = 0

    for i in range(len(S)):
        # print("-----")
        # print(f"i: {i}")
        # print(f"tot: {tot}")
        # print(f"S[i]: {S[i]}")
        # print(f"x: {x}")
        # print(f"cnt: {cnt}")
        # print(f"cnt[tot]: {cnt[tot]}")
        # print(f"ans: {ans}")

        cnt[tot] += 1
        tot += int(S[i]) * x
        tot %= 2019
        ans += cnt[tot]
        x = x * 10
    
    # print("-----")
    # print(f"i: {i}")
    # print(f"tot: {tot}")
    # print(f"S[i]: {S[i]}")
    # print(f"x: {x}")
    # print(f"cnt: {cnt}")
    # print(f"cnt[tot]: {cnt[tot]}")
    # print(f"ans: {ans}")
    
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
S = input()
from collections import defaultdict
d = defaultdict(int)
d[0] += 1

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

ans = 0
for v in d.values():
  ans += v * (v-1)

print(ans // 2)

Submission status: Time Limit Exceeded

Solution code:
S = input()
from collections import defaultdict
d = defaultdict(int)
d[0] += 1

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

ans = 0
for v in d.values():
  ans += v * (v-1) // 2

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=input()
List=list(N)
p=""
ans=0
for j in range(4,len(List)+1):
  for i in range(len(List)-j+1):
    for x in range(i,i+j):
      p += List[x]
    if int(p)%2019==0:
      ans+=1
    p=""
print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = input()
T = [0] * (1+len(S))
for i in range(1, 1+len(S)):
  T[i] = int(S[-i:]) % 2019

from itertools import combinations
ans = 0
for i, j in combinations(range(1+len(S)), 2):
  if T[i] == T[j]:
    ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()
e = 0
i = 0

for x in range(len(s)):
    for y in range(len(s)-x):
        e = x + y + 1
        if int(s[x:e]) % 2019 == 0:
            i = i + 1

print(i)

Submission status: Time Limit Exceeded

Solution code:
s = input()
n = len(s)
d = [0]*2019
d[0] = 1
total = 0

for i in range(n):
  buf = s[n-i-1:n]
  l = (int(buf))%2019
  d[l] += 1
  total += d[l] - 1
  
print(total)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
s = input()
n = len(s)
d = defaultdict(int)
d[0] = 1
total = 0

for i in range(n):
  buf = s[n-i-1:n]
  l = (int(buf))%2019
  d[l] += 1
  total += d[l] - 1
  #print(int(buf),l)
  
print(total)

Submission status: Time Limit Exceeded

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

x = [0]

for i, j in enumerate(s):
    x.append((x[-1] + int(j) * pow(10,i))%mod)

C = Counter(x)
ans = 0

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

Submission status: Time Limit Exceeded

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

a = [0]*2019
count = 0
val = 10
for i in range(n):
    tmp = int(s[n-i-1:n]) % 2019
    count = count + a[tmp]
    a[tmp] = a[tmp] + 1
    if(tmp == 0):
        count = count + 1
    val = val * 10

print(count)

Submission status: Time Limit Exceeded

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

a = [0]*2019
count = 0
val = 10
for i in range(n):
    tmp = (x % val) % 2019
    count = count + a[tmp]
    a[tmp] = a[tmp] + 1
    if(tmp == 0):
        count = count + 1
    val = val * 10

print(count)

Submission status: Time Limit Exceeded

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

a = [0]*2019
count = 0
for i in range(n):
    tmp = int(s[n-i-1:n]) % 2019
    count = count + a[tmp]
    a[tmp] = a[tmp] + 1
    if(tmp == 0):
        count = count + 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
# Problem D - Multiple of 2019

from collections import Counter

# input
S = input()
s_len = len(S)

# initialization
ans = 0
mod_list = [0]*(s_len + 1)

# mod count
for i in range(1, s_len+1):
    tmp_num = int(S[s_len-i:])
    mod_list[i] = tmp_num % 2019

# output
mod_counter = Counter(mod_list)
for k in mod_counter.keys():
    m_c = mod_counter[k]
    if m_c>=2:
        ans += m_c * (m_c-1) // 2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = list(input())
count = 0
for i in range(1, len(s)+1):
  if i != 1:
    s.pop(0)
  num = ''
  for j in range(1, len(s)+1):
    num += s[j-1]
    if int(num) % 673 == 0 and int(num)%3 == 0:
      count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
s = list(input())
count = 0
for i in range(1, len(s)+1):
  if i != 1:
    s.pop(0)
  num = ''
  for j in range(1, len(s)+1):
    num += s[j-1]
    if int(num) % 2019 == 0:
      count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
S = input()
a = len(S)
mod = 0
L = [0]*2019 #余りの列
L[0] = 1
for i in range(a-1,-1,-1):
    mod = (int(S[i])*(10**(a-1-i))+mod) %2019
    L[mod] += 1  
ans = 0
for i in L:
  ans += i*(i-1)//2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()
l = len(s)
t = [0] * l
t[l - 1] = int(s[l - 1])
m = [0] * 2019
m[0] = 1
ans = 0

for i in range(l - 1, 0, -1):
    t[i - 1] = (t[i] + int(s[i - 1]) * 10 ** (l - i)) % 2019
    m[t[i - 1]] += 1

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()
l = len(s)
t = [0] * l
t[l - 1] = int(s[l - 1])
m = [0] * 2019
ans = 0

for i in range(l - 1, 0, -1):
    t[i - 1] = (t[i] + int(s[i - 1]) * 10 ** (l - i)) % 2019
    ans += m[t[i - 1]]
    m[t[i - 1]] += 1
    if t[i - 1] == 0:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

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

print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
s = input()
l = len(s)
t = [2019] * l
t[l - 1] = int(s[l - 1])
ans = 0

for i in range(l - 1, 0, -1):
    mod = (t[i] + int(s[i - 1]) * 10 ** (l - i)) % 2019
    cnt = t.count(mod)
    t[i - 1] = mod
    if mod == 0:
        ans += 1
    if cnt > 0:
        ans += cnt

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque, defaultdict

S = input()

L = int(S)
S = S[::-1]
cnt = defaultdict(int)

tmp = 0
answer = 0
for i, s in enumerate(S):
    tmp += int(s) * 10 ** i
    if tmp % 2019 == 0:
        answer += cnt[0] + 1
    else:
        answer += cnt[tmp % 2019]
    cnt[tmp % 2019] += 1
    #print(tmp, answer)

print(answer)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

S = input()
n = len(S)

mp = defaultdict(int)
mp[0] += 1
x = 0
for i, s in enumerate(reversed(S)):
    x += int(s) * 10**i
    m = x % 2019
    mp[m] += 1

ans = 0
for m in mp.values():
    ans += m * (m - 1) // 2

print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()[::-1]
counts = [0]*2019
counts[0] = 1
sum = 0
d = 1
for c in s:
  sum += int(c)*d
  remain = sum%2019
  d *= 10
  counts[remain] += 1

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

S = input()
n = len(S)

mp = defaultdict(int)
mp[0] += 1
for i in range(0, n):
    s = S[i:]
    m = int(s) % 2019
    mp[m] += 1

ans = 0
for m in mp.values():
    ans += m * (m - 1) // 2

print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = list(input())
mod = 2019
tot = [0]
ans = 0
dp = [0 for _ in range(2020)]
dp[0] = 1
for i in range(len(s)):
    nx = tot[i] + int(s[i])*(10**(len(s)-i))%mod
    nx %= mod
    if dp[nx] != 0:
        ans += dp[nx]
    dp[nx] += 1
    tot.append(nx)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)
from numba import njit


@njit
def loof(a,N,memo):
    M = np.zeros(2019,dtype=np.int16)
    M[0] += 1
    T = 0
    for i in range(N-1,-1,-1):
        T = a[i] * memo[N-i-1] + T
        m = T % 2019
        M[m] += 1
    return M


@njit
def pow_mod(a,n,mod):
    memo = np.array([1])
    if n >= 1:
        for i in range(n-1):
            memo = np.append(memo,memo[-1]*a%mod)
        return memo


def main():
    S = input().rstrip()
    S = list(map(int,list(S)))
    a = np.array(S)

    N = len(a)

    memo = pow_mod(10,N,2019)
    M = loof(a,N,memo)

    res = 0

    for m in M:
        res += m * (m-1) // 2

    print(res)


main()

Submission status: Time Limit Exceeded

Solution code:
s = list(input()[::-1])
mod = 2019
tot = [0]
for i in range(len(s)):
    tot.append((tot[i] + (int(s[i])*(10**i))%mod)%mod)
dp = [0 for _ in range(2020)]
ans = 0
for t in tot:
    ans += dp[t]
    dp[t]+= 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)
from numba import njit


@njit
def loof(a):
    N = len(a)
    M = np.zeros(2019,dtype=np.int16)
    M[0] += 1
    T = 0
    memo = pow_mod(10,N,2019)
    for i in range(N-1,-1,-1):
        T = a[i] * memo[N-i-1] + T
        m = T % 2019
        M[m] += 1
        # print(m)
    return M


@njit
def pow_mod(a,n,mod):
    memo = np.array([1])
    if n >= 1:
        for i in range(n-1):
            memo = np.append(memo,memo[-1]*a%mod)
        return memo


def main():
    S = input().rstrip()
    S = list(map(int,list(S)))
    a = np.array(S)

    M = loof(a)
    # print(M)

    res = 0
    ans = np.array([res])

    flag = True
    cnt = 0

    for m in M:
        res += m * (m-1) // 2
        ans = np.append(ans,res)
        if (res == 3) & (flag):
            # print(m,cnt)
            flag = False
        cnt += 1

    # print(M[1164:1167])
    # print(ans)
    print(res)


# print(S)

# np.set_printoptions(threshold=2030)
main()

Submission status: Time Limit Exceeded

Solution code:
S=input()
mods=[0]*2019
nums=[0]*len(S)

nums[0]=int(S[-1])

for i in range(len(S)-1):
    nums[i+1]=int(S[-i-2])*(10**(i+1))+nums[i]
for i in range(len(S)):
    k = nums[i]%2019
    mods[k]+=1

sums = 0

for i in range(1,2019):
    sums+=mods[i]*(mods[i]-1)//2

sums+=2**mods[0]-1

print(sums)

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    from collections import defaultdict
    s = input()
    n = len(s)
    d = defaultdict(int)
    d[0] += 1
    for i in range(1, n + 1):
        d[int(s[-i:]) % 2019] += 1

    def calc(x): return x * (x - 1) // 2
    ans = 0
    for v in d.values():
        ans += calc(v)
    print(ans)


if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
s = list(input()[::-1])
mod = 2019
tot = [0]
for i in range(len(s)):
    tot.append((tot[i] + (int(s[i])*(10**i))%mod)%mod)
cnt = {}
looked = []
ans = 0
for i in range(len(s)+1):
    if tot[i] in looked:
        ans += cnt[tot[i]]
        cnt[tot[i]] += 1
    else:
        cnt[tot[i]] = 1
        looked.append(tot[i])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
S=input()
mods=[0]*2019

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

    mods[k] += 1

sums = 0

for i in range(1,2019):
    sums+=mods[i]*(mods[i]-1)//2
sums+=2**mods[0]-1

print(sums)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import collections


def solve(S: int):
    S = list(map(int, list(str(S))))
    count = collections.defaultdict(int)

    count[0] = 1
    tmp = ''
    prev_modulo = 0
    for idx, s in enumerate(S[::-1]):
        prev_modulo = (s * (10 ** idx) + prev_modulo) % 2019
        count[prev_modulo] += 1

    result = 0
    for k, v in count.items():
        result += v * (v-1) // 2
    print(result)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = int(next(tokens))  # type: int
    solve(S)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
S = input()
res = [0]
counter = {}
counter[0] = 1
for i in range(1, len(S)+1):
    rest = int(S[-i:]) % 2019
    res.append(rest)
    try :counter[rest] += 1
    except KeyError: counter[rest] = 1 
ans = 0
for value, c in counter.items():
    ans += c * (c-1)/2
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import collections


def solve(S: int):
    S = str(S)

    count = collections.defaultdict(int)
    count[0] = 1
    tmp = ''
    prev_modulo = 0
    for idx, s in enumerate(S[::-1]):
        s = int(s)
        prev_modulo = (s * (10 ** idx) + prev_modulo) % 2019
        count[prev_modulo] += 1

    result = 0
    for k, v in count.items():
        result += v * (v-1) // 2
    print(result)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = int(next(tokens))  # type: int
    solve(S)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import re
from collections import Counter
S = input()
res = [0]
counter = {}
counter[0] = 1
for i in range(1, len(S)+1):
    rest = int(S[-i:]) % 2019
    res.append(rest)
    try :counter[rest] += 1
    except KeyError: counter[rest] = 1 
ans = 0
for value, c in counter.items():
    ans += c * (c-1)/2
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import collections


def solve(S: int):
    S = str(S)

    count = collections.defaultdict(int)
    count[0] = 1
    tmp = ''
    for idx, s in enumerate(S[::-1]):
        digit = int(S[-idx:])
        count[digit % 2019] += 1
    
    result = 0
    for k, v in count.items():
        result += v * (v-1) // 2
    print(result)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = int(next(tokens))  # type: int
    solve(S)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import collections


def solve(S: int):
    S = str(S)

    count = collections.defaultdict(int)
    count[0] = 1
    tmp = ''
    for s in S[::-1]:
        tmp = s + tmp
        digit = int(tmp)
        count[digit % 2019] += 1
    result = 0
    for k, v in count.items():
        result += v * (v-1) // 2
    print(result)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = int(next(tokens))  # type: int
    solve(S)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import re
from collections import Counter
S = input()
res = [0]
for i in range(1, len(S)+1):
    res.append(int(S[-i:]) % 2019)
counter = Counter(res)
ans = 0
for value, c in counter.items():
    ans += c * (c-1)/2
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

def count_substring(s):
    found_remainder = defaultdict(int)
    current_mod = 0
    found_remainder[0] = 1

    output = 0
    for i in range(len(s)-1,-1,-1):
        digit = s[i]
        current_mod =  (int(digit)*10**(len(s)-1-i) % 2019 + current_mod) % 2019
        output += found_remainder[current_mod]
        found_remainder[current_mod] += 1

    return output

s = input()
print(count_substring(s))

Submission status: Time Limit Exceeded

Solution code:
s = input()[::-1]
length = len(s)
a = [0] * length
d = [0] * length
ans = [0] * 2019

a[0] = int(s[0])
d[0] = a[0]
ans[0] = 1 # dif
ans[d[0]] += 1

for i in range(1, length):
    a[i] = int(s[i]) * 10**i % 2019
    d[i] = (d[i-1] + a[i]) % 2019
    ans[d[i]] += 1

# print(int(sum([ans[i] * (ans[i]-1) for i in range(2019)]) / 2) + ans[0])
print(int(sum([ans[i] * (ans[i]-1) for i in range(2019)]) / 2))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

total = [0] * (n + 1)
cnt = [0] * mod
cnt[0] = 1

for i in range(1, n + 1):
    now = int(s[n - i:])
    now %= mod
    cnt[now] += 1

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from collections import Counter
from collections import defaultdict
def main():
    S = list(map(int, input().rstrip("\r\n")))
    N = len(S)
    P = 2019
    S.reverse()
    ans = 0
    if P == 2 or P == 5:
        for i in range(N):
            if S[i] % P == 0:ans += N-i
    else:
        D = [0] * (N+1)
        tenpow = 1
        d = defaultdict(int)
        d[0] += 1
        for i in range(N):
            S[i] = S[i] * tenpow % P
            tenpow *= 10 % P
            D[i+1] = (S[i] + D[i]) % P
            d[D[i+1]] += 1
        for v in d.values():
            ans += v*(v-1)//2
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n = input()

remainder = [0]*2019
remainder[0] = 1

for i in range(len(n)):
	remainder[int(n[i:])%2019] += 1
    
res = 0
for e in remainder:
	res += e*(e-1)//2

print(res)

Submission status: Time Limit Exceeded

Solution code:
s = input()
a = int(s)%2019
mod_N = [0]*2019
mod_N[a] += 1
r = 10**(len(s)-1)
for i in s:
  a = (a-int(i)*10**r)%2019
  r = r//10
  mod_N[a] += 1
ans = 0
for i in mod_N:
  ans += i*(i-1)//2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()
len_s = len(s)
pre = 0
mod = [0]*2019
mod[0]=1
x = 1
for i in range(len_s):
    pre = (x*int(s[len_s-i-1])+pre)%2019
    mod[pre] += 1
    x *= 10
sum_mod = 0
for m in mod:
    sum_mod += m*(m-1)//2
print(sum_mod)