TnT/Multi_CodeNet4Repair huggingface dataset:
Problem: Takahashi has a string S of length N consisting of digits from `0` through `9`.  He loves the prime number P. He wants to know how many non-empty (contiguous) substrings of S \- there are N \times (N + 1) / 2 of them - are divisible by P when regarded as integers written in base ten.  Here substrings starting with a `0` also count, and substrings originated from different positions in S are distinguished, even if they are equal as strings or integers.  Compute this count to help Takahashi.

Submission attempts (in order):
#
import sys
import math
#import numpy as np
import itertools
from collections import Counter

n,p = (int(i) for i in input().split())

s = [int(i) for i in list(input())] 

answer = 0
#print(s)
q=0
x=[]
if p == 2 or p == 5:
    for i in range(n-1,-1,-1):
        if s[i]%p == 0:
            answer += i+1
else:
    for i in range(n-1,-1,-1):
        q=(q+s[i])%p
        x.append(q)
        q = (q * 10)%p
    #print(x)
    counter = Counter(x)
    #print(counter)

    for k in counter:
    #    print(k)

        answer += counter[k] * (counter[k]-1) // 2

print(answer)



#
import sys
import math
#import numpy as np
import itertools
from collections import Counter

n,p = (int(i) for i in input().split())

s = [int(i) for i in list(input())] 

answer = 0
#print(s)
q=0
x=[]
if p == 2 or p == 5:
    for i in range(n-1,-1,-1):
        if s[i]%p == 0:
            answer += i+1
else:
    d=1
    for i in range(n-1,-1,-1):
        q = (d*s[i]+q)%p
        x.append(q)
        d = (d * 10)%p
    #print(x)
    counter = Counter(x)
    #print(counter)

    for k in counter:
    #    print(k)
        if k==0:
            answer += counter[k] * (counter[k]+1) // 2
        else:
            answer += counter[k] * (counter[k]-1) // 2

print(answer)



Verdicts: Wrong Answer

Accepted
Problem: Takahashi has a string S of length N consisting of digits from `0` through `9`.  He loves the prime number P. He wants to know how many non-empty (contiguous) substrings of S \- there are N \times (N + 1) / 2 of them - are divisible by P when regarded as integers written in base ten.  Here substrings starting with a `0` also count, and substrings originated from different positions in S are distinguished, even if they are equal as strings or integers.  Compute this count to help Takahashi.

Submission attempts (in order):
def main():
    n, p = map(int, input().split())
    s = list(map(int, list(input())))
    now = 1
    now2 = 0

    dp = [0]*p
    cnt = 0
    if p != 5:
        for i in s:
            now2 = (now2*10+i) % p
            dp[((i-now2) % p)*pow(now, p-2, p) % p] += 1
            cnt += dp[((-now2) % p)*pow(now, p-2, p) % p]
            now = (now*10) % p
            print(dp)
    else:
        for j, i in enumerate(s):
            if i in [0, 5]:
                cnt += j+1
    print(cnt)


main()

n,p=map(int,input().split());s,n,N,c,d=map(int,list(input())),1,0,0,[0]*p
if p!=5:
 for i in s:N,a=(N*10+i)%p,pow(n,p-2,p);d[(i-N)*a%p]+=1;c+=d[-N*a%p];n=n*10%p
else:c=sum([j+1 for j,i in enumerate(s)if i%5==0])
print(c)

Verdicts: Wrong Answer

Accepted
Problem: Takahashi has a string S of length N consisting of digits from `0` through `9`.  He loves the prime number P. He wants to know how many non-empty (contiguous) substrings of S \- there are N \times (N + 1) / 2 of them - are divisible by P when regarded as integers written in base ten.  Here substrings starting with a `0` also count, and substrings originated from different positions in S are distinguished, even if they are equal as strings or integers.  Compute this count to help Takahashi.

Submission attempts (in order):
input = _input().__next__
n, p = [int(c) for c in input().split()]
s = input()    

if p in (2,5):
    a = tuple(int(c)%p for c in s)
    out = 0
    for i,x in enumerate(a):
        if x==0:
            out += (i + 1)
else:
    a = [0]*n
    tmp = 0
    for i in reversed(range(n)):
        tmp = (tmp * 10 + int(s[i])) % p
        a[i] = tmp
    d = {i: 0 for i in range(p)}
    d[0] = 1
    out = 0
    for x in a[::-1]:
        out += d[x]
        d[x] += 1
print(out)


def hoge():

    n, p = [int(c) for c in input().split()]
    s = input()    

    if p in (2,5):
        a = tuple(int(c)%p for c in s)
        out = 0
        for i,x in enumerate(a):
            if x==0:
                out += (i + 1)
    else:
        a = [0]*n
        tmp = 0
        for i in reversed(range(n)):
            tmp = (tmp + pow(10, n-i-1, p) * int(s[i])) % p
    #         tmp = (tmp + 10**(n-i-1) * int(s[i])) % p
            a[i] = tmp
        d = {i: 0 for i in range(p)}
        d[0] = 1
        out = 0
        for x in a[::-1]:
            out += d[x]
            d[x] += 1
    print(out)
hoge()

Verdicts: Runtime Error

Accepted
Problem: Takahashi has a string S of length N consisting of digits from `0` through `9`.  He loves the prime number P. He wants to know how many non-empty (contiguous) substrings of S \- there are N \times (N + 1) / 2 of them - are divisible by P when regarded as integers written in base ten.  Here substrings starting with a `0` also count, and substrings originated from different positions in S are distinguished, even if they are equal as strings or integers.  Compute this count to help Takahashi.

Submission attempts (in order):
n,p = map(int, input().split())
s = list(map(int, list(ns())))
if p in (2, 5):
  print(sum(i+1 for i in range(n) if s[i]%p == 0))
  exit(0)
   
ans = g = 0
d = [0]*p
d[0] = 1
t = 1
for i in range(n-1,-1,-1):
    g = (g + s[i]*t)%p
    ans += d[g]
    d[g] += 1
    t = (t*10)%p
print(ans)

n,p = map(int, input().split())
s = list(map(int, list(input())))
if p in (2, 5):
  print(sum(i+1 for i in range(n) if s[i]%p == 0))
  exit(0) 
ans = g = 0
d = [0]*p
d[0] = 1
t = 1
for i in range(n-1,-1,-1):
    g = (g + s[i]*t)%p
    ans += d[g]
    d[g] += 1
    t = (t*10)%p
print(ans)

Verdicts: Runtime Error

Accepted
Problem: Takahashi has a string S of length N consisting of digits from `0` through `9`.  He loves the prime number P. He wants to know how many non-empty (contiguous) substrings of S \- there are N \times (N + 1) / 2 of them - are divisible by P when regarded as integers written in base ten.  Here substrings starting with a `0` also count, and substrings originated from different positions in S are distinguished, even if they are equal as strings or integers.  Compute this count to help Takahashi.

Submission attempts (in order):
class Solution:

    def solve(self, N: int, P: int, S: str):

        if P == 2 or P == 5:
            answer = 0
            for idx, s in enumerate(S):
                if int(s) % P == 0:
                    answer += idx + 1

        else:
            answer = 0
            U = [0] * P  # int(S[i,N] mod P
            U[0] += 1
            for i in range(N):
                U[int(S[i:N]) % P] += 1

            for u in U:
                answer += u * (u-1) // 2

            print(U)

        return answer


if __name__ == '__main__':

    # standard input
    N, P = map(int, input().split())
    S = input()

    # solve
    solution = Solution()
    answer = solution.solve(N, P, S)
    print(answer)


class Solution:

    def solve(self, N: int, P: int, S: str):

        if P == 2 or P == 5:
            answer = 0
            for idx, s in enumerate(S):
                if int(s) % P == 0:
                    answer += idx + 1

        else:
            answer = 0
            U = [0] * P  # int(S[i,N] mod P
            U[0] += 1

            num = 0
            base10_mod_p = 1
            for i in range(N):
                num = (num + int(S[N-i-1]) * base10_mod_p) % P
                base10_mod_p = (base10_mod_p * 10) % P

                U[num] += 1

            for u in U:
                answer += u * (u-1) // 2

        return answer


if __name__ == '__main__':

    # standard input
    N, P = map(int, input().split())
    S = input()

    # solve
    solution = Solution()
    answer = solution.solve(N, P, S)
    print(answer)


Verdicts: Wrong Answer

Accepted
Problem: Takahashi has a string S of length N consisting of digits from `0` through `9`.  He loves the prime number P. He wants to know how many non-empty (contiguous) substrings of S \- there are N \times (N + 1) / 2 of them - are divisible by P when regarded as integers written in base ten.  Here substrings starting with a `0` also count, and substrings originated from different positions in S are distinguished, even if they are equal as strings or integers.  Compute this count to help Takahashi.

Submission attempts (in order):
N, P = map(int, input().split())
S = input()
ans = 0

d = [0]*(N+1)
# d[N-1] = 1

if 10%P == 0:
    ans = 0
    for i in range(N):
        if int(S[i]) % P == 0:
            ans += i + 1
    print(ans)
else:
    
    ten = 1
    
    for i in range(N-1,-1,-1):
        a = int(S[i]) * ten % P
        d[i] = (d[i+1]+a)%P
        ten *= 10
        ten %= P

    
    counter = [0]*P
    print(d)
    for j in range(N, -1, -1):
        ans += counter[d[j]]
        print(ans)
        counter[d[j]] += 1

    print(ans)


N, P = map(int, input().split())
S = input()
ans = 0

d = [0]*(N+1)
# d[N-1] = 1

if 10%P == 0:
    ans = 0
    for i in range(N):
        if int(S[i]) % P == 0:
            ans += i + 1
    print(ans)
else:
    
    ten = 1
    
    for i in range(N-1,-1,-1):
        a = int(S[i]) * ten % P
        d[i] = (d[i+1]+a)%P
        ten *= 10
        ten %= P

    
    counter = [0]*P
#     print(d)
    for j in range(N, -1, -1):
        ans += counter[d[j]]
#         print(ans)
        counter[d[j]] += 1

    print(ans)


Verdicts: Wrong Answer

Accepted
Problem: Takahashi has a string S of length N consisting of digits from `0` through `9`.  He loves the prime number P. He wants to know how many non-empty (contiguous) substrings of S \- there are N \times (N + 1) / 2 of them - are divisible by P when regarded as integers written in base ten.  Here substrings starting with a `0` also count, and substrings originated from different positions in S are distinguished, even if they are equal as strings or integers.  Compute this count to help Takahashi.

Submission attempts (in order):
import sys
from collections import defaultdict

def solve():
    input = sys.stdin.readline
    N, P = map(int, input().split())
    S = input().strip("\n")
    modSum = 0
    modSum = int(S[0]) % P
    modDict = defaultdict(int)
    ans = 0

    if P == 2 or P == 5:
        for i in range(N):
            if int(S[i]) % P == 0:
                ans += i + 1
        
    else:
        modDict[modSum[0]] += 1
        for i in range(1, N):
            modSum = ((modSum * 10) + int(S[i])) % P
            modDict[modSum] += 1

        for key in modDict:
            v = modDict[key]
            if key > 0: ans += v * (v - 1) // 2
            else: ans += v + (v * (v - 1) // 2)
    
    print(ans)

    return 0

if __name__ == "__main__":
    solve()

import sys
from collections import defaultdict

def solve():
    input = sys.stdin.readline
    N, P = map(int, input().split())
    S = input().strip("\n")
    modSum = 0
    modDict = defaultdict(int)
    modDict[0] += 1
    ans = 0

    if P == 2 or P == 5:
        for i in range(N):
            if int(S[i]) % P == 0:
                ans += i + 1
        
    else:
        for i in range(N):
            modSum += int(S[N-i-1]) * pow(10, i, P)
            modSum %= P
            modDict[modSum] += 1

        for key in modDict:
            v = modDict[key]
            ans += v * (v - 1) // 2
    
    print(ans)

    return 0

if __name__ == "__main__":
    solve()

Verdicts: Runtime Error

Accepted
Problem: Takahashi has a string S of length N consisting of digits from `0` through `9`.  He loves the prime number P. He wants to know how many non-empty (contiguous) substrings of S \- there are N \times (N + 1) / 2 of them - are divisible by P when regarded as integers written in base ten.  Here substrings starting with a `0` also count, and substrings originated from different positions in S are distinguished, even if they are equal as strings or integers.  Compute this count to help Takahashi.

Submission attempts (in order):
from collections import deque

import numpy as np

n, p = map(int, input().split())
d = deque(input())

ans = 0
if p == 2 or p == 5:
  for i in range(n):
    k = int(d.popleft())
    if n % p == 0:
      ans += i + 1
else:
  sub = [0 for i in range(n)]
  wk = 0
  for i in range(n):
    k = int(d.pop())
    wk = (wk + k * pow(10, i, p)) % p
    sub[i] = wk
  print(sub)
  ans = 0
  dic = {}
  for i in range(n):
    if sub[i] == 0:
      ans += 1
    if sub[i] in dic.keys():
      ans += dic[sub[i]]
      dic[sub[i]] = dic[sub[i]] + 1
    else:
      dic[sub[i]] = 1

print(ans)

from collections import deque

import numpy as np

n, p = map(int, input().split())
d = deque(input())

ans = 0
if p == 2 or p == 5:
  for i in range(n):
    k = int(d.popleft())
    if k % p == 0:
      ans += i + 1
else:
  sub = [0 for i in range(n)]
  wk = 0
  for i in range(n):
    k = int(d.pop())
    wk = (wk + k * pow(10, i, p)) % p
    sub[i] = wk
  ans = 0
  dic = {}
  for i in range(n):
    if sub[i] == 0:
      ans += 1
    if sub[i] in dic.keys():
      ans += dic[sub[i]]
      dic[sub[i]] = dic[sub[i]] + 1
    else:
      dic[sub[i]] = 1

print(ans)

Verdicts: Wrong Answer

Accepted
Problem: Takahashi has a string S of length N consisting of digits from `0` through `9`.  He loves the prime number P. He wants to know how many non-empty (contiguous) substrings of S \- there are N \times (N + 1) / 2 of them - are divisible by P when regarded as integers written in base ten.  Here substrings starting with a `0` also count, and substrings originated from different positions in S are distinguished, even if they are equal as strings or integers.  Compute this count to help Takahashi.

Submission attempts (in order):
from collections import defaultdict
dd = defaultdict(int)
n,p=map(int, input().split())
S = list(input().rstrip())
tmp = 0
r=1
su=0

if p==2 or p==5:
    c=n
    for s in S[::-1]:
        if int(s)%p==0:
            su+=c
        c-=1
    print(su)
else:
    for s in S[::-1]:
        tmp+=int(s)*r
        r*=10
        tmp%=p
        r%=p
        dd[tmp]+=1
    for i in dd.values():
        su+=(i*(i-1))//2
    print(su)


from collections import defaultdict
dd = defaultdict(int)
n,p=map(int, input().split())
S = list(input().rstrip())
tmp = 0
r=1
su=0
dd[0]=1
if p==2 or p==5:
    c=n
    for s in S[::-1]:
        if int(s)%p==0:
            su+=c
        c-=1
    print(su)
else:
    for s in S[::-1]:
        tmp+=int(s)*r
        tmp%=p
        dd[tmp]+=1
        r*=10
        r%=p
    for i in dd.values():
        su += (i*(i-1))//2
    print(su)


Verdicts: Wrong Answer

Accepted
Problem: Takahashi has a string S of length N consisting of digits from `0` through `9`.  He loves the prime number P. He wants to know how many non-empty (contiguous) substrings of S \- there are N \times (N + 1) / 2 of them - are divisible by P when regarded as integers written in base ten.  Here substrings starting with a `0` also count, and substrings originated from different positions in S are distinguished, even if they are equal as strings or integers.  Compute this count to help Takahashi.

Submission attempts (in order):
import numpy as np

n, p = map(int, input().split())
s = np.array([int(i) % p for i in input()])
mod = np.zeros((n, p), dtype=np.int)
for i in range(n):
  mod[i, s[i]] = 1
count = mod[0, 0]
for i in range(1, n):
  idx = s[i]
  for j in range(p):
    mod[i, idx] += mod[i-1, j]
    idx = (idx + 10) % p
print(mod[:, 0].sum())

n, p = map(int, input().split())
s = input()
count = 0
if p == 2 or p == 5:
  for i in range(n):
    if int(s[i]) % p == 0:
      count += i + 1
  print(count)
else:
  mod = [0] * p
  mod[0] = 1
  tmp = 0
  ten = 1
  for i in s[::-1]:
    ten = ten * 10 % p
    tmp = (tmp + int(i) * ten) % p
    mod[tmp] += 1
  for m in mod:
    count += m * (m - 1) // 2
  print(count)

Verdicts: Runtime Error

Accepted
Problem: Takahashi has a string S of length N consisting of digits from `0` through `9`.  He loves the prime number P. He wants to know how many non-empty (contiguous) substrings of S \- there are N \times (N + 1) / 2 of them - are divisible by P when regarded as integers written in base ten.  Here substrings starting with a `0` also count, and substrings originated from different positions in S are distinguished, even if they are equal as strings or integers.  Compute this count to help Takahashi.

Submission attempts (in order):
import sys
input = sys.stdin.readline

N,P = map(int,input().split())
S = list(input())

A = [0]*(N)
A[-1] = int(S[-1])
A[-1] %= P
base = 10
for i in reversed(range(N-1)):
    A[i] = A[i+1] + base*int(S[i])
    A[i] %= P
    base *= 10


ans = 0
if P==2 or P==5:
    for i in reversed(range(N)):
        if int(S[i])%P==0:
            ans += i+1
else:
    nums = {}
    for a in A:
        nums[a] = 0
    for a in A:
        nums[a] += 1
    
    for n in nums.keys():
        k = nums[n]
        if n==0:
            ans += k*(k+1)//2
        else:
            ans += k*(k-1)//2
    
print(ans)    




import sys
input = sys.stdin.readline

N,P = map(int,input().split())
S = list(input())

A = [0]*(N)
A[-1] = int(S[-1])
A[-1] %= P
base = 10
for i in reversed(range(N-1)):
    A[i] = A[i+1] + base*int(S[i])
    A[i] %= P
    base *= 10


ans = 0
if P==2 or P==5:
    for i in reversed(range(N)):
        if int(S[i])%P==0:
            ans += i+1
else:
    nums = {}
    for a in A:
        nums[a] = 0
    for a in A:
        nums[a] += 1
    
    for n in nums.keys():
        k = nums[n]
        if n==0:
            ans += k*(k+1)//2
        else:
            ans += k*(k-1)//2
    
print(ans)    



import sys


N,P = map(int,input().split())
S = list(input())

A = [0]*(N)
A[-1] = int(S[-1])
A[-1] %= P
base = 10 % P
for i in reversed(range(N-1)):
    A[i] = A[i+1] + base*int(S[i])
    A[i] %= P
    base *= 10
    base %= P


ans = 0
if P==2 or P==5:
    for i in reversed(range(N)):
        if int(S[i])%P==0:
            ans += i+1
else:
    nums = {}
    for a in A:
        if not (a in nums):
            nums[a] = 1
        else:
            nums[a] += 1
    
    for n in nums.keys():
        k = nums[n]
        if n==0:
            ans += k*(k+1)//2
        else:
            ans += k*(k-1)//2
    
print(ans)    



Verdicts: Runtime Error

Runtime Error

Accepted
Problem: Takahashi has a string S of length N consisting of digits from `0` through `9`.  He loves the prime number P. He wants to know how many non-empty (contiguous) substrings of S \- there are N \times (N + 1) / 2 of them - are divisible by P when regarded as integers written in base ten.  Here substrings starting with a `0` also count, and substrings originated from different positions in S are distinguished, even if they are equal as strings or integers.  Compute this count to help Takahashi.

Submission attempts (in order):
N,P = map(int,input().split())
S = input()

def solve(S,N,P):
    if P == 2:
        ans = 0
        for i in range(N):
            if int(S[i])%P == 0:
                ans += i+1
        return ans
    if P == 5:
        ans = 0
        for i in range(N):
            if int(S[i])%P == 0:
                ans += i+1
        return ans
    
    S = S[::-1]
    mod_list = [0]*P
    mod_list[0] = 1

    mod = P
    tmp = 0

    for i in range(N):
        tmp = (tmp + int(S[i])*pow(10,i,mod))%mod
        mod_list[tmp] += 1
    
    ans = 0
    for i in mod_list:
        ans += i*(i-1)//2
        
    return ans

solve(S,N,P)

N,P = map(int,input().split())
S = input()

def solve(S,N,P):
    if P == 2:
        ans = 0
        for i in range(N):
            if int(S[i])%P == 0:
                ans += i+1
        return ans
    if P == 5:
        ans = 0
        for i in range(N):
            if int(S[i])%P == 0:
                ans += i+1
        return ans
    
    S = S[::-1]
    mod_list = [0]*P
    mod_list[0] = 1

    mod = P
    tmp = 0

    for i in range(N):
        tmp = (tmp + int(S[i])*pow(10,i,mod))%mod
        mod_list[tmp] += 1
    
    ans = 0
    for i in mod_list:
        ans += i*(i-1)//2
        
    return ans

print(solve(S,N,P))

Verdicts: Wrong Answer

Accepted
Problem: Takahashi has a string S of length N consisting of digits from `0` through `9`.  He loves the prime number P. He wants to know how many non-empty (contiguous) substrings of S \- there are N \times (N + 1) / 2 of them - are divisible by P when regarded as integers written in base ten.  Here substrings starting with a `0` also count, and substrings originated from different positions in S are distinguished, even if they are equal as strings or integers.  Compute this count to help Takahashi.

Submission attempts (in order):
n, mod = map(int, input().split())
s = input()

total = 0
if mod == 2 or mod == 5:
	for i, q in enumerate(s):
		if int(q)%mod == 0:
			total += i+1
else:
	counts = [0]*mod
	counts[0] = 1
	h = 0
	
	d = 1
	for t in reversed(s):
		m = int(s)*d%mod
		h = (h+m)%mod
		total += counts[h]
		counts[h] += 1
		d = (d*10)%mod

print(total)

n, mod = map(int, input().split())
S = input()

total = 0
if mod == 2 or mod == 5:
	for i, q in enumerate(S):
		if int(q)%mod == 0:
			total += i+1
else:
	counts = [0]*mod
	counts[0] = 1
	h = 0
	
	d = 1
	for s in reversed(S):
		m = int(s)*d%mod
		h = (h+m)%mod
		total += counts[h]
		counts[h] += 1
		d = (d*10)%mod

print(total)

Verdicts: Wrong Answer

Accepted
Problem: Takahashi has a string S of length N consisting of digits from `0` through `9`.  He loves the prime number P. He wants to know how many non-empty (contiguous) substrings of S \- there are N \times (N + 1) / 2 of them - are divisible by P when regarded as integers written in base ten.  Here substrings starting with a `0` also count, and substrings originated from different positions in S are distinguished, even if they are equal as strings or integers.  Compute this count to help Takahashi.

Submission attempts (in order):
n, p = map(int, input().split())
s = input()
a = []
c = 0
if p == 2:
    b = [0]*n
    for i in range(n):
        if int(s[i])%2 == 0:
            b[i] += 1
    for i in range(n):
        if b[i] == 1:
            c += i+1
elif p == 5:
    b = [0]*n
    for i in range(n):
        if int(s[i])%5 == 0:
            b[i] += 1
    for i in range(n):
        if b[i] == 1:
            c += i+1
else:
    b = [0]*p
    b[0] = 1
    d = [1]
    print(d)
    a.append(int(s[-1])%p)
    for i in range(n-1):
        d.append(d[-1]*10%p)
    for i in range(1, n):
        a.append((int(s[-i-1])*d[i]+a[i-1])%p)
    for i in range(n):
        b[a[i]] += 1
    for i in range(p):
        c += int(b[i]*(b[i]-1)/2)
print(c)

n, p = map(int, input().split())
s = input()
a = []
c = 0
if p == 2:
    b = [0]*n
    for i in range(n):
        if int(s[i])%2 == 0:
            b[i] += 1
    for i in range(n):
        if b[i] == 1:
            c += i+1
elif p == 5:
    b = [0]*n
    for i in range(n):
        if int(s[i])%5 == 0:
            b[i] += 1
    for i in range(n):
        if b[i] == 1:
            c += i+1
else:
    b = [0]*p
    b[0] = 1
    d = [1]
    a.append(int(s[-1])%p)
    for i in range(n-1):
        d.append(d[-1]*10%p)
    for i in range(1, n):
        a.append((int(s[-i-1])*d[i]+a[i-1])%p)
    for i in range(n):
        b[a[i]] += 1
    for i in range(p):
        c += int(b[i]*(b[i]-1)/2)
print(c)

Verdicts: Wrong Answer

Accepted
Problem: Takahashi has a string S of length N consisting of digits from `0` through `9`.  He loves the prime number P. He wants to know how many non-empty (contiguous) substrings of S \- there are N \times (N + 1) / 2 of them - are divisible by P when regarded as integers written in base ten.  Here substrings starting with a `0` also count, and substrings originated from different positions in S are distinguished, even if they are equal as strings or integers.  Compute this count to help Takahashi.

Submission attempts (in order):
n,p = map(int,input().split())
s = input()
num = 0
s1 = [0]*(n+1)
ans = 0
if p == 2 or p == 5:
	for i in range(len(s)):
		if int(s[i])%p == 0:
			ans += i+1	
	print(ans)
	exit()
ans = 0
arr = [0]*p
s = s[::-1]
z = 1
for i in range(n):
	s1[i+1] = s1[i] + int(s[i])*z
	z *=10 %p
	s1[i+1] %=p
	arr[s1[i]] += 1
arr[s1[n]]+=1
print(s1)
for i in range(p):
	ans += arr[i] * (arr[i] - 1) // 2
print(ans)


n,p = map(int,input().split())

ans = 0
s = input()
if p == 2 or p == 5:
    for i in range(len(s)):
        n = int(s[i])
        if n%p == 0:
            ans += i+1
    print(ans)
    exit()

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

ans = sum(i*(i-1)//2 for i in r)
print(ans)


Verdicts: Wrong Answer

Accepted
Problem: Takahashi has a string S of length N consisting of digits from `0` through `9`.  He loves the prime number P. He wants to know how many non-empty (contiguous) substrings of S \- there are N \times (N + 1) / 2 of them - are divisible by P when regarded as integers written in base ten.  Here substrings starting with a `0` also count, and substrings originated from different positions in S are distinguished, even if they are equal as strings or integers.  Compute this count to help Takahashi.

Submission attempts (in order):
n, p = map(int, input().rstrip().split())
s = input().rstrip()

if p == 2 or p == 5:
    ans = 0
    s = map(int, s)
    for i, c in enumerate(s):
        if c % p == 0:
            ans += i + 1
    print(ans)
else:
    s = s[::-1]
    cnt = [0] * p
    k = 0
    cnt[k] = 1
    for i, c in enumerate(map(int(s))):
        k = (c * (10**i) + k) % p
        cnt[k] += 1

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


n, p = map(int, input().rstrip().split())
s = input().rstrip()

if p == 2 or p == 5:
    ans = 0
    s = map(int, s)
    for i, c in enumerate(s):
        if c % p == 0:
            ans += i + 1
    print(ans)
else:
    s = s[::-1]
    cnt = [0] * p
    k = 0
    cnt[k] = 1
    w = 1
    for i, c in enumerate(map(int, s)):
        k = c * w + k
        w *= 10
        while k >= p:
            k -= p
        while w >= p:
            w -= p
        cnt[k] += 1

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


Verdicts: Runtime Error

Accepted
Problem: Takahashi has a string S of length N consisting of digits from `0` through `9`.  He loves the prime number P. He wants to know how many non-empty (contiguous) substrings of S \- there are N \times (N + 1) / 2 of them - are divisible by P when regarded as integers written in base ten.  Here substrings starting with a `0` also count, and substrings originated from different positions in S are distinguished, even if they are equal as strings or integers.  Compute this count to help Takahashi.

Submission attempts (in order):
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n,p = mi()
s = input().strip()
srev = s[-1]

if p == 2 or p == 5:
    ans = 0
    for i in range(n):
        if int(s[i]) % p == 0:
            ans += i +1
    print(ans)
    exit()

acum = []
from collections import defaultdict
d = defaultdict(lambda :0)
for i in range(1,n+1):
    a = int(srev[:i])
    modd = a % p
    d[modd] += 1
    acum.append((modd,d[modd]))
ans = d[0]
for i in range(n):
    ans += d[acum[i][0]] - acum[i][1]
print(ans)




ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n,p = mi()
s = input()
srev = s[::-1]

if p == 2 or p == 5:
    ans = 0
    for i in range(n):
        if int(s[i]) % p == 0:
            ans += i +1
    print(ans)
    exit()

acum = []
from collections import defaultdict
d = defaultdict(lambda :0)
d = [0] * p
num = 0
tenpow = 1
for i in range(0,n):
    a = int(srev[i])
    a = num + a *tenpow 
    tenpow = tenpow * 10 % p
    modd = a % p
    num = modd
    d[modd] += 1
    acum.append((modd,d[modd]))
ans = d[0]
for i in range(n):
    ans += d[acum[i][0]] - acum[i][1]
print(ans)



Verdicts: Wrong Answer

Accepted
Problem: Takahashi has a string S of length N consisting of digits from `0` through `9`.  He loves the prime number P. He wants to know how many non-empty (contiguous) substrings of S \- there are N \times (N + 1) / 2 of them - are divisible by P when regarded as integers written in base ten.  Here substrings starting with a `0` also count, and substrings originated from different positions in S are distinguished, even if they are equal as strings or integers.  Compute this count to help Takahashi.

Submission attempts (in order):
#!/usr/bin/env python3
import sys


def solve(N: int, P: int, S: int):
    if N == 1:
        print(1 if S[0]%P == 0 else 0)
    arr = [[int(S[i])%P for i in range(N)]]
    for i in range(2,N):
        prevArr = arr[-1]
        arr.append([0]*(N-i+1))
        for j in range(N-i+1):
            sum = 0
            for k in range(j):
                arr[-1][j] =(arr[-1][j]+prevArr[k])%P
    print(arr)


    
    
    #     sDiv = 0
    #     coeff = 1
    #     for j in range(i,N):
    #         sDiv= (sDiv*coeff + arr[j])%P
    #         coeff*=10
    #         if sDiv == 0:
    #             sum+=1
    # print(sum)
    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()
    N = int(next(tokens))  # type: int
    P = int(next(tokens))  # type: int
    S = next(tokens)  # type: int
    solve(N, P, S)

if __name__ == '__main__':
    main()


#!/usr/bin/env python3
import sys
from collections import defaultdict

def solve(N: int, P: int, S: str):
    if 10%P == 0:
        sum = 0
        for i in range(1,N+1):
            if int(S[-i]) % P == 0:
                sum += (N-i)+1
        print(sum)
        return
    else:
        current = 0
        C = 1
        counts = defaultdict(int)
        for i in range(1,N+1):
            if i == 1:
                current = int(S[-1])%P
            else:
                current = (int(S[-i])*C + current)%P
            counts[current]+=1
            C=C*10%P
        sum = 0
        for k in counts:
            c = counts[k]
            sum += int((c*(c-1)/2))
        sum += counts[0]
        print(sum)

    
    
    #     sDiv = 0
    #     coeff = 1
    #     for j in range(i,N):
    #         sDiv= (sDiv*coeff + arr[j])%P
    #         coeff*=10
    #         if sDiv == 0:
    #             sum+=1
    # print(sum)
    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()
    N = int(next(tokens))  # type: int
    P = int(next(tokens))  # type: int
    S = next(tokens)  # type: int
    solve(N, P, S)

if __name__ == '__main__':
    main()


Verdicts: Runtime Error

Accepted
Problem: Takahashi has a string S of length N consisting of digits from `0` through `9`.  He loves the prime number P. He wants to know how many non-empty (contiguous) substrings of S \- there are N \times (N + 1) / 2 of them - are divisible by P when regarded as integers written in base ten.  Here substrings starting with a `0` also count, and substrings originated from different positions in S are distinguished, even if they are equal as strings or integers.  Compute this count to help Takahashi.

Submission attempts (in order):
from collections import defaultdict

n, p = map(int, input(). split())
s = input()

cnt = 0
if 10 % p == 0:
    for i, c in enumerate(s, 1):
        if int(c) % p == 0:
            cnt += 1
else:
    rem_dic = defaultdict(int)
    rem_dic[0] = 1
    for i in range(1, n + 1):
        rem_dic[int(s[n - 1:]) % p] += 1
    for rem_cnt in rem_dic.values():
        cnt += rem_cnt * (rem_cnt - 1) // 2

print(cnt)

n, p = map(int, input(). split())
s = list(map(int, input()[::-1]))

cnt = 0
if 10 % p == 0:
    for i, c in enumerate(s):
        if int(c) % p == 0:
            cnt += n - i
else:
    accmod = [0] * p
    accmod[0] = 1
    num = 0
    for i in range(n):
        num = (num + s[i] * pow(10, i, p)) % p
        accmod[num] += 1
    for v in accmod:
        if v > 1:
            cnt += v * (v - 1) // 2
print(cnt)


Verdicts: Wrong Answer

Accepted
Problem: Takahashi has a string S of length N consisting of digits from `0` through `9`.  He loves the prime number P. He wants to know how many non-empty (contiguous) substrings of S \- there are N \times (N + 1) / 2 of them - are divisible by P when regarded as integers written in base ten.  Here substrings starting with a `0` also count, and substrings originated from different positions in S are distinguished, even if they are equal as strings or integers.  Compute this count to help Takahashi.

Submission attempts (in order):
from collections import Counter

n,p = map(int,input().split())
s = input()

ans = 0
if p == 2 or p == 5:
  for i in range(n):
    if int(s[i]) % p == 0:
      ans += (i+1)

print(ans)      

from collections import Counter

n,p = map(int,input().split())
s = input()

ans = 0
if p == 2 or p == 5:
  for i in range(n):
    if int(s[i]) % p == 0:
      ans += (i+1)

else:      
  mods = [0]*p
  mods[0] = 1
  m = 0
  d = 1  
  for i in range(n):
    m = (m + int(s[-i-1])*d) % p
    d = (d * 10) % p    
    mods[m] += 1
  
  for i in range(p):
    ans += mods[i]*(mods[i]-1)//2

print(ans)      

Verdicts: Wrong Answer

Accepted
Problem: Takahashi has a string S of length N consisting of digits from `0` through `9`.  He loves the prime number P. He wants to know how many non-empty (contiguous) substrings of S \- there are N \times (N + 1) / 2 of them - are divisible by P when regarded as integers written in base ten.  Here substrings starting with a `0` also count, and substrings originated from different positions in S are distinguished, even if they are equal as strings or integers.  Compute this count to help Takahashi.

Submission attempts (in order):
N,P = list(map(int,input().split()))
S = input()

U = [0]
a = 0

for i in range(N):
    a += int(S[-i-1])*(pow(10,i)%P)
    a %= P
    U.append(a)
print(U)

c = 0
for i in range(P):

    m = U.count(i)
    c += m*(m-1)//2
print(c)



N,P = list(map(int,input().split()))
S = input()

if P == 2:
    c = 0
    for i in range(N):
        u = int(S[i])
        if u % 2 == 0:
            c += i+1
    print(c)
        
elif P == 5:
    c = 0
    for i in range(N):
        u = int(S[i])
        if u % 5 == 0:
            c += i+1
    print(c)

else:
    U = [0]
    a = 0
    t = 1
    
    for i in range(N):
        t %= P
        a += int(S[-i-1])*t
        a %= P
        t *= 10
        U.append(a)
    U.append(10001)
    # print(U)
    
    # t3 = time.time()
    
    c = 0
    
    
    U.sort()
    # print(U)
    idx = 0
    q = -1
    for i in range(N+2):
        if q != U[i]:
            q = U[i]
            m = i - idx
            idx = i
            c += m*(m-1)//2
    print(c)
    # t4 = time.time()
    # print(t4-t3)
    
    # 10032

Verdicts: Wrong Answer

Accepted
Problem: Takahashi has a string S of length N consisting of digits from `0` through `9`.  He loves the prime number P. He wants to know how many non-empty (contiguous) substrings of S \- there are N \times (N + 1) / 2 of them - are divisible by P when regarded as integers written in base ten.  Here substrings starting with a `0` also count, and substrings originated from different positions in S are distinguished, even if they are equal as strings or integers.  Compute this count to help Takahashi.

Submission attempts (in order):
N,P=[int(s) for s in input().split()]
S=list(input())
if P!=2 and P!=5:
  ls=[0 for _ in range(N)]
  mod=[0 for _ in range(P)]
  d=10
  ls[0]=int(S[-1])
  mod[ls[0]]+=1
  for i in range(1,N):
    ls[i]=(ls[i-1]+d*int(S[-1-i]))%2019
    d=(d*10)%2019
    mod[ls[i]]+=1
  #print(ls)
  #print(mod)  
  ans=mod[0]
  for i in range(N):
    m=ls[i]
    mod[ls[i]]-=1
    ans+=mod[ls[i]]
else:
  ans=0
  for i in range(N):
    if int(S[i])%P==0:
      ans+=i+1
print(ans)
   


N,P=[int(s) for s in input().split()]
S=list(input())
if P!=2 and P!=5:
  ls=[0 for _ in range(N)]
  mod=[0 for _ in range(P)]
  d=10
  ls[0]=int(S[-1])%P
  mod[ls[0]]+=1
  for i in range(1,N):
    ls[i]=(ls[i-1]+d*int(S[-1-i]))%P
    d=(d*10)%P
    mod[ls[i]]+=1
  #print(ls)
  #print(mod)  
  ans=mod[0]
  for i in range(N):
    m=ls[i]
    mod[ls[i]]-=1
    ans+=mod[ls[i]]
else:
  ans=0
  for i in range(N):
    if int(S[i])%P==0:
      ans+=i+1
print(ans)
   


Verdicts: Runtime Error

Accepted
Problem: Takahashi has a string S of length N consisting of digits from `0` through `9`.  He loves the prime number P. He wants to know how many non-empty (contiguous) substrings of S \- there are N \times (N + 1) / 2 of them - are divisible by P when regarded as integers written in base ten.  Here substrings starting with a `0` also count, and substrings originated from different positions in S are distinguished, even if they are equal as strings or integers.  Compute this count to help Takahashi.

Submission attempts (in order):
n,p=map(int,input().split())
s=input()[::-1]
A=[0]*n
A[0]=int(s[0])
t=1
for i in range(1,n):
  A[i]=(int(s[i])*t+A[i-1])%p
  t=(t*10)%p
ans=0
import collections
D=collections.defaultdict(int)
D[0]=1
if p!=2 and p!=5:
  for i in range(n):
    ans+=D[A[i]]
    D[A[i]]+=1
  print(ans)
else:
  s=s[::-1]
  ans=0
  for i in range(n):
    if int(s[i])%p==0:
      ans+=i+1
  print(ans)





n,p=map(int,input().split())
s=input()[::-1]
A=[0]*n
A[0]=int(s[0])
t=1
for i in range(1,n):
  A[i]=(int(s[i])*t+A[i-1])%p
  t=(t*10)%p
ans=0
import collections
D=collections.defaultdict(int)
D[0]=1
if p!=2 and p!=5:
  for i in range(n):
    ans+=D[p-A[i]]
    D[A[i]]+=1
  print(ans)
else:
  s=s[::-1]
  ans=0
  for i in range(n):
    if int(s[i])%p==0:
      ans+=i+1
  print(ans)

n,p=map(int,input().split())
s=input()[::-1]
A=[0]*n
A[0]=int(s[0])%p
t=10
for i in range(1,n):
  A[i]=(int(s[i])*t+A[i-1])%p
  t=(t*10)%p
ans=0
import collections
D=collections.defaultdict(int)
D[0]=1
if p!=2 and p!=5:
  for i in range(n):
    ans+=D[A[i]]
    D[A[i]]+=1
  print(ans)
else:
  s=s[::-1]
  ans=0
  for i in range(n):
    if int(s[i])%p==0:
      ans+=i+1
  print(ans)





Verdicts: Wrong Answer

Wrong Answer

Accepted
Problem: Takahashi has a string S of length N consisting of digits from `0` through `9`.  He loves the prime number P. He wants to know how many non-empty (contiguous) substrings of S \- there are N \times (N + 1) / 2 of them - are divisible by P when regarded as integers written in base ten.  Here substrings starting with a `0` also count, and substrings originated from different positions in S are distinguished, even if they are equal as strings or integers.  Compute this count to help Takahashi.

Submission attempts (in order):
n,p = list(map(int,input().split()))
S = input()

if p == 2 or p == 5:
  ans = 0
  for i,s in enumerate(S):
    if int(s)%p == 0:
      ans += i+1
  print(ans)
  exit()

M = [0]*p
pre = 0
ans = 0
i = 1
for s in S[::-1]:
  pre += s*i
  pre %= p
  M[pre] += 1
  i *= 10

M[0] += 1
ans = sum(map(lambda m:(m*(m-1))//2, M))
print(ans)



n,p = list(map(int,input().split()))
S = input()

if p == 2 or p == 5:
  ans = 0
  for i,s in enumerate(S):
    if int(s)%p == 0:
      ans += i+1
  print(ans)
  exit()

def MS(i,s,pre):
  return (s*i +pre)%p
 
M = [0]*p
M[0] = 1
t = 1
pre = 0
for s in S[::-1]:
  pre += (int(s)*t)%p
  M[pre] += 1
  t *= 10

ans = sum(map(lambda m:(m*(m-1))//2, M))
print(ans)



n,p = list(map(int,input().split()))
S = input()

if p == 2 or p == 5:
  ans = 0
  for i,s in enumerate(S):
    if int(s)%p == 0:
      ans += i+1
  print(ans)
  exit()

def MS(i,s,pre):
  return (int(s)*i+pre)%p
 
M = [0]*p
M[0] = 1
i = 1
pre = 0
for s in S[::-1]:
  
  pre = pre + int(s)*i
  pre = pre%p
  M[pre] += 1
  i = i*10%p

ans = sum(map(lambda m:(m*(m-1))//2, M))
print(ans)



Verdicts: Runtime Error

Runtime Error

Accepted
Problem: Takahashi has a string S of length N consisting of digits from `0` through `9`.  He loves the prime number P. He wants to know how many non-empty (contiguous) substrings of S \- there are N \times (N + 1) / 2 of them - are divisible by P when regarded as integers written in base ten.  Here substrings starting with a `0` also count, and substrings originated from different positions in S are distinguished, even if they are equal as strings or integers.  Compute this count to help Takahashi.

Submission attempts (in order):
n,p=map(int,input().split())
S=input()
s=int(s)
ans=0
if p==5:
    for i in range(n):
        if int(S[i])==5 or int(S[i])==0:
            ans+=i+1
elif p==2:
    for i in range(n):
        if int(S[i])%2==0:
            ans+=i+1
else:
    kouho=[0]*p
    for i in range(n):
        a=int(S[-i:])
        a%=p
        kouho[a]+=1
    for j in range(p):
        z=kouho[j]
        ans+=z*(z-1)//2
    ans+=kouho[0]
print(ans)

from collections import defaultdict
n,p=map(int,input().split())
S=input()
ans=0
if p==5:
    for i in range(n):
        if int(S[i])==5 or int(S[i])==0:
            ans+=i+1
elif p==2:
    for i in range(n):
        if int(S[i])%2==0:
            ans+=i+1
else:
    kouho=defaultdict(int)
    s=0
    ruijo=1
    for i in range(n):
        ruijo%=p
        s+=int(S[-(i+1)])*(ruijo)
        a=s%p
        kouho[a]+=1
        ruijo*=10
    for j in range(p):
        z=kouho[j]
        ans+=z*(z-1)//2
    ans+=kouho[0]
print(ans)

Verdicts: Runtime Error

Accepted
Problem: Takahashi has a string S of length N consisting of digits from `0` through `9`.  He loves the prime number P. He wants to know how many non-empty (contiguous) substrings of S \- there are N \times (N + 1) / 2 of them - are divisible by P when regarded as integers written in base ten.  Here substrings starting with a `0` also count, and substrings originated from different positions in S are distinguished, even if they are equal as strings or integers.  Compute this count to help Takahashi.

Submission attempts (in order):
N,P=map(int,input().split())
S=list(map(int,list(input())))
count=0

if P!=2 and P!=5:
    for i in range(0,N):
        chec=S[i]
        j=0
        while i+j<N:
          　　　chec%=P
                if chec==0:
                    count+=1
                j+=1
                if i+j<N:
                    chec=chec*10+S[i+j]
if P==2:
    for i in range(N):
        if S[i]%2==0:
            count+=i+1
if P==5:
    for i in range(N):
        if S[i]==0 or S[i]==5:
            count+=i+1
print(count)


            




#E
N,P=map(int,input().split())
S=input()
ans=0
if P in (2,5):
    for i,s in enumerate(S):
        if int(s)%P==0:
            ans+=i+1
else:
    cnt=[0 for _ in range(P)]
    CS=0
    PLC=1
    for s in S[::-1]:
        tmp=(int(s)*PLC)%P
        CS=(CS+tmp)%P
        cnt[CS]+=1
        PLC=(PLC*10)%P
        # print(CS)
        # print(cnt)
    for c in cnt:
        ans+=c*(c-1)//2
    ans+=cnt[0]
print(ans)


Verdicts: Runtime Error

Accepted
Problem: There are N robots numbered 1 to N placed on a number line. Robot i is placed at coordinate X_i. When activated, it will travel the distance of D_i in the positive direction, and then it will be removed from the number line. All the robots move at the same speed, and their sizes are ignorable.  Takahashi, who is a mischievous boy, can do the following operation any number of times (possibly zero) as long as there is a robot remaining on the number line.    * Choose a robot and activate it. This operation cannot be done when there is a robot moving.  While Robot i is moving, if it touches another robot j that is remaining in the range [X_i, X_i + D_i) on the number line, Robot j also gets activated and starts moving. This process is repeated recursively.  How many possible sets of robots remaining on the number line are there after Takahashi does the operation some number of times? Compute this count modulo 998244353, since it can be enormous.

Submission attempts (in order):
import heapq

mod = 998244353

n = int(input())
robot = [tuple(map(int, input().split())) for _ in range(n)]
robot.sort(reverse=True)
parent = list(range(n))

root = []
for i in range(n):
  x, d = robot[i]
  while root:
    r = heapq.heappop(root)
    if r[0] < x + d:
      parent[r[1]] = i
    else:
      heapq.heappush(root, r)
      break
  heapq.heappush(root, (x, i))
  
count = 1
dp = [1] * n
for i in range(n):
  p = parent[i]
  if p == i:
    count = count * dp[i] % mod
  else:
    dp[p] = dp[p] * (dp[i] + 1) % mod
print(count)

import heapq

mod = 998244353

def dfs(v: int, child) -> int:
  res = 1
  for u in child[v]:
    res = res * dfs(u) % mod
  return res + 1

n = int(input())
robot = [tuple(map(int, input().split())) for _ in range(n)]
robot.sort()
child = [[] for _ in range(n)]

root = []
for i in range(n-1, -1, -1):
  x, d = robot[i]
  while root:
    r = heapq.heappop(root)
    if r[0] < x + d:
      child[i].append(r[1])
    else:
      heapq.heappush(root, r)
      break
  heapq.heappush(root, (x, i))
  
count = 1
for r in root:
  count = count * dfs(r[1], child) % mod
print(count)

import heapq

mod = 998244353

n = int(input())
robot = [tuple(map(int, input().split())) for _ in range(n)]
robot.sort(reverse=True)
parent = list(range(n))

root = []
for i in range(n):
  x, d = robot[i]
  while root:
    r = heapq.heappop(root)
    if r[0] < x + d:
      parent[r[1]] = i
    else:
      heapq.heappush(root, r)
      break
  heapq.heappush(root, (x, i))
  
count = 1
dp = [1] * n
for i in range(n):
  p = parent[i]
  if p == i:
    count = count * (dp[i] + 1) % mod
  else:
    dp[p] = dp[p] * (dp[i] + 1) % mod
print(count)

Verdicts: Wrong Answer

Runtime Error

Accepted
Problem: There are N robots numbered 1 to N placed on a number line. Robot i is placed at coordinate X_i. When activated, it will travel the distance of D_i in the positive direction, and then it will be removed from the number line. All the robots move at the same speed, and their sizes are ignorable.  Takahashi, who is a mischievous boy, can do the following operation any number of times (possibly zero) as long as there is a robot remaining on the number line.    * Choose a robot and activate it. This operation cannot be done when there is a robot moving.  While Robot i is moving, if it touches another robot j that is remaining in the range [X_i, X_i + D_i) on the number line, Robot j also gets activated and starts moving. This process is repeated recursively.  How many possible sets of robots remaining on the number line are there after Takahashi does the operation some number of times? Compute this count modulo 998244353, since it can be enormous.

Submission attempts (in order):
 import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 998244353
mans = 998244353 ;ans = 0 ;count = 0 ;pro = 1
sys.setrecursionlimit(10**6)

n = int(input())
XD = [tuple(map(int,input().split())) for i in range(n)]
XD.append((-10**10,inf))
XD.sort()

now = 0
visited1 = [] 
def dfs(node):
  visited1.append(node)

  global now
  pro = 1
  while now < n :
    if XD[now+1][0] < XD[node][0] + XD[node][1]:
      now += 1
      pro *= dfs(now)
      pro %= mod
    else:break
  return pro + 1
ans = dfs(0)
print((ans-1)%mod)




import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 998244353
mans = 998244353 ;ans = 0 ;count = 0 ;pro = 1
sys.setrecursionlimit(10**6)

n = int(input())
XD = [tuple(map(int,input().split())) for i in range(n)]
XD.append((-10**10,inf))
XD.sort()

now = 0
def dfs(node):
  global now
  pro = 1
  while now < n :
    if XD[now+1][0] < XD[node][0] + XD[node][1]:
      now += 1
      pro *= dfs(now)
      pro %= mod
    else:break
  return pro + 1
ans = dfs(0)
print((ans-1)%mod)


Verdicts: Runtime Error

Accepted