Problem:


Score : 500 points

Problem Statement

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.

Constraints

1 \leq N \leq 2 \times 10^5

S consists of digits.

|S| = N

2 \leq P \leq 10000

P is a prime number.

Input

Input is given from Standard Input in the following format:

N P
S

Output

Print the number of non-empty (contiguous) substrings of S that are divisible by P when regarded as an integer written in base ten.

Sample Input 1

4 3
3543

Sample Output 1

6

Here S = 3543. There are ten non-empty (contiguous) substrings of S:

3: divisible by 3.

35: not divisible by 3.

354: divisible by 3.

3543: divisible by 3.

5: not divisible by 3.

54: divisible by 3.

543: divisible by 3.

4: not divisible by 3.

43: not divisible by 3.

3: divisible by 3.

Six of these are divisible by 3, so print 6.

Sample Input 2

4 2
2020

Sample Output 2

10

Here S = 2020. There are ten non-empty (contiguous) substrings of S, all of which are divisible by 2, so print 10.

Note that substrings beginning with a 0 also count.

Sample Input 3

20 11
33883322005544116655

Sample Output 3

68



Sample input:
4 3
3543


Sample output:
6

Submission status: Wrong Answer

Solution code:
# fin=open('in','r')
# input=lambda:fin.readline().strip()
n,p=map(int,input().split())
s=list(map(int,input()))
c=0
cnt=[0]*p
cnt[0]+=1
for k in range(len(s)-1,-1,-1):
	c=(c+s[k]*pow(10,len(s)-1-k,p))%p
	cnt[c]+=1
print(sum(x*(x-1)//2 for x in cnt))

Submission status: Wrong Answer

Solution code:
n,p=map(int,input().split())
s=list(map(int,input()))
c=0
cnt=[0]*p
cnt[0]+=1
for k in range(len(s)-1,-1,-1):
	c=(c+s[k]*pow(10,len(s)-1-k,p))%p
	cnt[c]+=1
print(sum(x*(x-1)//2 for x in cnt))

Submission status: Wrong Answer

Solution code:

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    N,P=MI()
    S=input()
    
    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()
    
    
    
    from collections import defaultdict
    dd = defaultdict(int)
    
    now=0
    ans=0
    dd[0]=1
    for i in range(N):
        now=(now*10+int(S[i]))%P
        dd[now]+=1
        ans+=dd[now]-1
        
    print(ans)
    

main()

Submission status: Wrong Answer

Solution code:

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    N,P=MI()
    S=input()
    
    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()
    
    
    
    from collections import defaultdict
    dd = defaultdict(int)
    
    now=0
    dd[0]+=1
    for i in range(N):
        now=(now*10+int(S[i]))%P
        dd[now]+=1
        
    ans=0
    for k,v in dd.items():
        ans+=(v*(v-1))//2
        
    print(ans)
    

main()

Submission status: Wrong Answer

Solution code:

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    N,P=MI()
    S=input()
    from collections import defaultdict
    dd = defaultdict(int)
    
    now=0
    dd[0]+=1
    for i in range(N):
        now=(now*10+int(S[i]))%P
        dd[now]+=1
        
    ans=0
    for k,v in dd.items():
        ans+=(v*(v-1))//2
        
    print(ans)
    

main()

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time, copy

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

def getCharNGram(n,s):
    charGram = [str(int(''.join(s[i:i+n]))) for i in range(len(s)-n+1)]
    return charGram

n, p = na()
s = ns()
ct = 0
amari = [0] * (n+1)
amari[0] = 10 % p
for i in range(1, n):
    amari[i] = (amari[i-1] * 10) % p
for i in range(1, n+1):
    li = getCharNGram(i,s)
    for c in li:
        ls = 0
        for j in range(min((i), len(c))):
            ls += amari[j] * int(c[j])
        if ls % p == 0:
            ct += 1
print(ct)

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time, copy

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

def getCharNGram(n,s):
    charGram = [''.join(s[i:i+n]) for i in range(len(s)-n+1)]
    return charGram

n, p = na()
s = ns()
ct = 0
amari = [0] * (n+1)
amari[0] = 10 % p
for i in range(1, n):
    amari[i] = (amari[i-1] * 10) % p
for i in range(1, n+1):
    li = getCharNGram(i,s)
    for c in li:
        ls = 0
        for j in range(i):
            ls += amari[j] * int(c[j])
        if ls % p == 0:
            ct += 1
print(ct)

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

ans = 0
if p in {2, 5}:
    for i, num in enumerate(s):
        if num % p == 0:
            ans += i + 1
else:
    bfo, cnt = 0, [1] + [0] * (p - 1)
    for i, num in enumerate(s[::-1]):
        bfo = (bfo + pow(10, i, p) * num) % p
        ans += cnt[bfo]
        cnt[bfo] += 1
print(ans)

if n == 4 and p == 3:
    print('hoge')

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

ans = 0
if p in {2, 5}:
    for i, num in enumerate(s):
        if num % p == 0:
            ans += i + 1
else:
    modp = [0]
    for i, num in enumerate(s[::-1]):
        tmp = modp[-1] + pow(10, i, p) * num
        modp.append(tmp % p)
    cnt = [0] * p
    for i in modp:
        ans += cnt[i]
        cnt[i] += 1
print(ans)

if p == 3:
    print('hoge')

Submission status: Wrong Answer

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

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

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


prem = [0]*p
prem[0] = 1
curr_rem = 0
ans = 0
for i,si in enumerate(s):
    sii = int(si)
    curr_rem = (curr_rem*10+sii)%p
    ans += prem[curr_rem]
    prem[curr_rem] += 1

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

ans = 0

if p in {2, 5}:
    lst = set(i for i in range(0, 10, p))
    for i, num in enumerate(s):
        if int(num) in lst:
            ans += i + 1
else:
    num = [0]
    for i in range(len(s)):
        tmp = num[-1] * 10 + int(s[i])
        num.append(tmp % p)
    mod = [0] * p
    for i in num:
        ans += mod[i]
        mod[i] += 1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

ans = 0
if p in {2, 5}:
    for i, num in enumerate(s):
        if num == '0' or 10 % int(num) == 0:
            ans += i + 1
else:
    num = [int(s[-1]) % p]
    for i in range(1, len(s)):
        tmp = num[-1] + pow(10, i, p) * int(s[-i - 1])
        num.append(tmp % p)
    mod = [1] + [0] * (p - 1)
    for i in num:
        ans += mod[i]
        mod[i] += 1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

ans = 0
if p in {2, 5}:
    for i, num in enumerate(s):
        if num == '0' or 10 % int(num) == 0:
            ans += i + 1
else:
    modp = Counter([int(s[i:]) % p for i in range(n)])
    for cnt in modp.values():
        ans += cnt * (cnt - 1) // 2
    ans += modp[0]
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

from collections import deque
from collections import defaultdict
def main():
    N, P = MI()
    S_ = S()
    mod_list = defaultdict(int)
    ans = 0
    if P == 2 or P == 5:
        for i in range(N):
            num = int(S_[i])
            if num % P == 0:
                ans += i + 1

    else:
        S_ = S_[::-1]
        num = ''
        for i in range(N):
            num += S_[i]
            mod = int(num) % P
            mod_list[mod] += 1
    values_ = mod_list.values()
    ans += mod_list[0]
    for value in values_:
        ans += (value - 1) * value // 2

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

from collections import deque
from collections import defaultdict
def main():
    N, P = MI()
    S_ = S()
    mod_list = defaultdict(int)
    ans = 0
    for i in range(N):
        num = S_[i:N]
        mod = int(num) % P
        if mod == 0:
            ans += 1
        mod_cnt = mod_list[mod]
        if mod_cnt >= 1:
            ans += mod_cnt
            mod_list[mod] += 1
            continue
        mod_list[mod] += 1

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

from collections import deque
from collections import  defaultdict
def main():
    N, P = MI()
    S_ = S()
    mod_list = defaultdict(int)
    ans = 0
    for i in range(N):
        num = S_[0:i + 1]
        mod = int(num) % P
        if mod == 0:
            ans += 1
        mod_cnt = mod_list[mod]
        if mod_cnt >= 1:
            ans += mod_cnt
            mod_list[mod] += 1
            continue
        mod_list[mod] += 1

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

from collections import deque
from collections import  defaultdict
def main():
    N, P = MI()
    S_ = S()
    num = ''
    mod_list = defaultdict(int)
    ans = 0
    for i in range(N):
        num += S_[i]
        mod = int(num) % P
        if mod == 0:
            ans += 1
        mod_cnt = mod_list[mod]
        if mod_cnt >= 1:
            ans += mod_cnt
            mod_list[mod] += 1
            continue
        mod_list[mod] += 1

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

from collections import deque
from collections import  defaultdict
def main():
    N, P = MI()
    S_ = S()
    num = ''
    mod_list = defaultdict(int)
    for i in range(N):
        num += S_[i]
        mod_list[int(num) % P] += 1


    ans = mod_list[0]
    values = mod_list.values()
    for value in values:
        if value >= 2:
            ans += value * (value - 1) // 2
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

from collections import deque
from collections import  defaultdict
def main():
    N, P = MI()
    S_ = S()
    num = ''
    mod_list = defaultdict(int)
    for i in range(N):
        num += S_[i]
        mod_list[int(num) % P] += 1


    ans = mod_list[0]
    for value in mod_list.values():
        if value >= 2:
            ans += value * (value - 1) // 2
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
import numpy as np

input = sys.stdin.readline


def ST():
    return input().rstrip()


def I():
    return int(input())


def MI():
    return map(int, input().split())


def LI():
    return list(MI())


N, P = MI()
S = ST()

cnt = np.zeros(P)
cnt[0] = 1
res = 0
tmp = 1
for s in S[::-1]:
    res += int(s) * tmp
    res %= P
    cnt[res] += 1
    tmp *= 10
    tmp %= P

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

print(int(ans))

Submission status: Wrong Answer

Solution code:
n, p = map(int, input().split())
s = list(map(int, list(input())))
if p == 2 or p == 5:
    ans = 0
    for i in range(n):
        if s[i] % p == 0:
            ans += i
    print(ans)
else:
    lis = [0] * p
    cnt = 0
    kurai = 1
    for i in s[::-1]:
        cnt += i * kurai % p
        cnt %= p
        lis[cnt] += 1
        kurai *= 10
        kurai %= p
    ans = 0
    for i in lis:
        ans += i * (i - 1) // 2
    ans += lis[0]
    print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
n,p=map(int,input().split())
s=input()

ans=0
if p==2 or p==5:
    for i,j in enumerate(s):
        if int(j)%p==0:
            ans +=i+1
else:
    num,point=0,1
    A=[0]
    for i in s[::-1]:
        num +=int(i)*point
        num %=p
        A.append(num)
        point *=10
        point %=p

    A=Counter(A)
    for i,j in A.items():
        if j>=2:ans +=i*(i-1)//2
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
n,p=map(int,input().split())
s=input()

ans=0
if p==2 or p==5:
    for i,j in enumerate(s):
        if int(j)%p==0:
            ans +=i+1
else:
    num,point=0,1
    A=[0]
    for i in s[::-1]:
        num +=int(i)*point
        num %=p
        point *=10
        point %=p

    A=Counter(A)
    for i,j in A.items():
        if j>=2:ans +=i*(i-1)//2
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
n,p=map(int,input().split())
s=input()

ans=0
if p==2 or p==5:
    for i,j in enumerate(s):
        if int(j)%2==0:
            ans +=i+1
else:
    num,point=0,1
    A=[0]
    for i in s[::-1]:
        num +=int(i)*point
        num %=p
        point *=10
        point %=p

    A=Counter(A)
    for i,j in A.items():
        if j>=2:ans +=i*(i-1)//2
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

if P in (2, 5):
    ans = sum(i for i, s in enumerate(S, 1) if not int(s) % P)
else:
    Acc = [0] * (N + 1)
    for i, s in enumerate(S, 1):
        Acc[i] = (Acc[i - 1] * 10 + int(s)) % P
    ans = sum(v * (v - 1) // 2 for v in Counter(Acc).values())
print(ans)

Submission status: Wrong Answer

Solution code:
# これほんと納得行かない
N, P = map(int, input().split())
S = list(map(int, input()))
if P==2 or P==5:
    ans = 0
    for i, c in enumerate(S, 1):
        if c%P==0:
            ans += i
    print(ans)
    exit()
L = [0] * P
cum = 0
ans = 0
L[0] += 1
inv10 = pow(10, P-2, P)
for c in S:
    cum = (cum * inv10 + c) % P
    ans += L[cum]
    L[cum] += 1
print(ans)

Submission status: Wrong Answer

Solution code:

# これほんと納得行かない
N, P = map(int, input().split())
S = list(map(int, input()))
if P==2 or P==5:
    ans = 0
    for i, c in enumerate(S, 1):
        if c%P==0:
            ans += i
    print(ans)
    exit()
L = [0] * P
cum = 0
ans = 0
L[0] += 1
for c in S:
    cum = (cum * 10 + c) % P
    ans += L[cum]
    L[cum] += 1
print(ans)

Submission status: Wrong Answer

Solution code:
# これほんと納得行かない
N, P = map(int, input().split())
S = list(map(int, input()))
if N==2 or N==5:
    ans = 0
    for i, c in enumerate(S, 1):
        if c%N==0:
            ans += i
    print(ans)
    exit()
L = [0] * P
cum = 0
ans = 0
L[0] += 1
for c in S:
    cum = (cum * 10 + c) % P
    ans += L[cum]
    L[cum] += 1
print(ans)

Submission status: Wrong Answer

Solution code:
# これほんと納得行かない
N, P = map(int, input().split())
S = list(map(int, input()))
if N==2 or N==5:
    ans = 0
    for i, c in enumerate(S, 1):
        if c%N==0:
            ans += i
L = [0] * P
cum = 0
ans = 0
L[0] += 1
for c in S:
    cum = (cum * 10 + c) % P
    ans += L[cum]
    L[cum] += 1
print(ans)

Submission status: Wrong Answer

Solution code:
n,p=map(int,input().split())
s=input()
mod=[0]*p
r=0
for i in range(n):
	r+=int(s[-i-1])*pow(10,i,p)
	r%=p
	mod[r]+=1
ans=0
for i,x in enumerate(mod):
	if i==0:
		ans=(ans+x*(x+1)//2)
	else:
		ans=(ans+x*(x-1)//2)
print(ans)

Submission status: Wrong Answer

Solution code:
n,p=map(int,input().split())
s=input()
mod=[0]*p
r=0
for i in range(n):
	r+=int(s[-i-1])
	r%=p
	mod[r]+=1
	r*=10
ans=0
for i,x in enumerate(mod):
	if i==0:
		ans=(ans+x*(x+1)//2)
	else:
		ans=(ans+x*(x-1)//2)
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3
import sys
from collections import Counter
input = lambda: sys.stdin.readline().strip()
n, p = [int(x) for x in input().split()]
s = input()
ans = 0
if p == 2 or p == 5:
    allowed_digits = '24680' if p == 2 else '50'
    for i, c in enumerate(s, start=1):
        if c in allowed_digits:
            ans += i
else:
    def minv(x, p):
        return pow(x, p - 2, p)

    count = Counter({0: 1})
    x, delta = 0, 1
    for c in s:
        x = ((x * 10) + ord(c) - ord('0')) % p
        y = x * minv(delta, p)
        ans += count[y]
        count[y] += 1
        delta = (delta * 10) % p

print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3
import sys
from collections import Counter
input = lambda: sys.stdin.readline().strip()
n, p = [int(x) for x in input().split()]
s = input()
ans = 0
if p == 2 or p == 5:
    allowed_digits = '24680' if p == 2 else '50'
    for i, c in enumerate(s, start=1):
        if c in allowed_digits:
            ans += i
else:
    def minv(x, p):
        return pow(x, p - 2, p)

    count = Counter({0: 1})
    x, delta = 0, 1
    for c in s:
        x = ((x * 10) + ord(c) - ord('0')) % p
        ans += count[x * minv(delta, p)]
        count[x] += 1
        delta = (delta * 10) % p

print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3
import sys
from collections import Counter
input = lambda: sys.stdin.readline().strip()
n, p = [int(x) for x in input().split()]
s = input()
count = Counter({0: 1})
x = 0
ans = 0
for c in reversed(s):
    x *= 10
    x += ord(c) - ord('0')
    x %= p
    ans += count[x]
    count[x] += 1
print(ans)

Submission status: Wrong Answer

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

cnt = [0] * P

base = 1
cur = 0
for c in S[::-1]:
    cur += (base * int(c)) % P
    cnt[cur % P] += 1
    base *= 10 
    base %= P
ans = 0
for i in cnt:
    if i == 0:
        continue
    ans += i * (i - 1) // 2
print(ans + cnt[0])

Submission status: Wrong Answer

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

cnt = [0] * P

base = 1
cur = 0
for c in S[::-1]:
    cur += base * int(c)
    cnt[cur % P] += 1
    base *= 10
ans = 0
for i in cnt:
    if i == 0:
        continue
    ans += i * (i - 1) // 2
print(ans + cnt[0])

Submission status: Wrong Answer

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

cnt = [0] * P

base = 1
cur = 0
for c in S[::-1]:
    cur += base * int(c)
    cnt[cur % P] += 1
    base *= 10
ans = 0
for i in cnt:
    ans += i * (i - 1) // 2
print(ans + cnt[0])

Submission status: Wrong Answer

Solution code:
# forは一回でO(N)で解きたいんすよ．
n, p = [int(i) for i in input().split()]
s = [int(i) for i in list(input())][::-1]
summ  = 0
ans = 0
cnt = [0]*p # あまりの部屋
cnt[0] = 1
for i in range(n):
    d = s[i]*pow(10, i ,p)
    summ = (summ + d) %p
    cnt[summ] +=1

if p in [2,5]: # 10の因数は別処理
    if p == 2:
        ok_list = [0,2,4,6,8]
    if p == 5:
        ok_list = [2,5]
    for i in range(n):
        d = s[i]
        if d in ok_list:
            ans += n-i
else: # 他のは,あまりが同じものは差し引けばあまりが0になるのでpで割り切れる判定
    for i in range(p):
        ans += cnt[i] * (cnt[i]-1)//2 # nC2の計算

print(ans)

Submission status: Wrong Answer

Solution code:
n, p = map(int, input().split())
s = input()
dic = {}
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:
  for i in range(n):
    num = int(s[i:])
    num %= p
    if p not in dic:
      dic[p] = 1
    else:
      dic[p] += 1
  if 0 not in dic:
    dic[0] = 1
  else:
    dic[0] += 1
  for value in dic.values():
    count += value * (value - 1) // 2
  print(count)

Submission status: Wrong Answer

Solution code:
n, p = map(int, input().split())
s = input()
count = 0
dic = {}
for i in range(n, 0, -1):
  for j in range(0, i):
    #print(s[j:])
    num = int(s[j:])
    if num not in dic:
      q = num % p
      dic[num] = q
    else:
      q = dic[num]
    if i == n:
      #print(0)
      r = 0
    else:
      #print(s[i:])
      r = dic[int(s[i:])]
    if q == r:
      count += 1
print(count)

Submission status: Wrong Answer

Solution code:
N, P = map(int, input().split())
S = input()
total = 0
if P == 2:
  for idx, right_value in enumerate(S, 1):
    if int(int(right_value)%2==0):
      total += idx
elif P == 5:
  valid_options = (0, 5)
  for idx, right_value in enumerate(S, 1):
    if int(int(right_value) in valid_options):
      total += idx
else:
  histo_modsuffix = [0]*P
  previous = 0
  for i, val in enumerate(reversed(S)):
    scale = pow(10, N-i-1, P)
    new_val = (previous + scale*int(val))%P
    histo_modsuffix[new_val] += 1
    previous = new_val
  for val in histo_modsuffix:
    total += val*(val-1)//2
  total += histo_modsuffix[0] # when right hand side is at far end
print(total)

Submission status: Wrong Answer

Solution code:

from collections import defaultdict

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

ctr = defaultdict(int)
ctr[0] = 1
cur = 0
for i in reversed(range(N)):
    cur = (cur + int(S[i]) * pow(10, N - i - 1, P)) % P
    ctr[cur] += 1

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

Submission status: Wrong Answer

Solution code:
from collections import defaultdict


def main():
    N, P = list(map(int, input().split()))
    S = input()
    if P in [2, 5]:
        ans = 0
        # P = 2, 5の時は一番下の位の数だけ見ればカウント可能
        for right in range(N - 1, - 1, - 1):
            if int(S[right]) % P == 0:
                ans += right + 1
        print(ans)
        return
    # 例：S = 3543, P = 3
    # 左からn番目 ～ 1番右の数のmod Pの値を計算
    #     C = [3543, 543, 43, 3] % P = [0, 0, 1, 0]
    # C[m] == C[n] なる m < nのペア数 + C[n] == 0なるnの個数を求める
    #     3 + 3 = 6
    cur_c = 0
    C = [0] * N
    for n, s in enumerate(S[::-1]):
        cur_c = (10 * cur_c + int(s)) % P
        C[N - 1 - n] = cur_c
    counter = defaultdict(int)
    for c in C:
        counter[c] += 1
    ans = 0
    for c in C:
        counter[c] -= 1
        ans += counter[c]
    ans += len([c for c in C if c == 0])
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

amari=[0]*P
amari[0]=1

for i in range(1,N+1):
  amari[int(S[-i:])%P]+=1
ans=0
for tmp in amari:
  ans+=tmp*(tmp-1)//2
  
print(ans)

Submission status: Wrong Answer

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

amari=[0]*P
amari[0]=1

for i in range(1,N+1):
  amari[int(S[-i:])%P]+=1
ans=0
for tmp in amari:
  ans+=tmp*(tmp-1)//2
  
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
n,p = map(int,input().split())
S = input()
dp = [0]
mod = p
for i in reversed(range(n)):
    dp.append(dp[-1]%mod + pow(10,n-1-i,mod)*int(S[i]))
    dp[-1]%=mod
count = Counter(dp)
ans = 0
for key,val in count.items():
    if val>=2:
        ans += val*(val-1)//2
print(ans)

Submission status: Wrong Answer

Solution code:
n,p=map(int,input().split())
s=input()[::-1]
A=[0]*n
D=[0]*n
for i in range(n):
    tmp=int(s[i])*10**i
    A[i]=tmp%p
D[0]=A[0]
for i in range(1,n):
    D[i]=(D[i-1]+A[i])%p
ans=0
for i in range(p):
    tmp=D.count(i)
    ans+=tmp*(tmp-1)//2
print(ans+D.count(0))

Submission status: Wrong Answer

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

if P == 2:
    ans = 0
    for i, d in enumerate(map(int, S)):
        if d % 2 == 0:
            ans += i+1
    print(ans)
elif P == 5:
    ans = 0
    for i, d in enumerate(map(int, S)):
        if d % 5 == 0:
            ans += i+1
    print(ans)
else:
    mods = [0] * P
    mods[0] = 1
    cur_mod = 0
    for i, digit in enumerate(map(int, S)):
        cur_mod += pow(10, N-i-1, P) * digit
        cur_mod %= P
        mods[cur_mod] += 1

    print(mods)

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

    print(ans)

Submission status: Wrong Answer

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

mods = [0] * P
mods[0] = 1
cur_mod = 0
for i, digit in enumerate(map(int, S)):
    cur_mod += pow(10, N-i-1, P) * digit
    cur_mod %= P
    mods[cur_mod] += 1

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

print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

s = list(input().strip())
a = [0] * p

i = 1
k = 0
while s:
    k = (k + int(s.pop()) * i) % p
    a[k] += 1
    i *= 10
    i %= p

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

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n,p=map(int,input().split())
s=input()
total=[0]*p#pで割った余りで分類
total[0]=1#t[0]=0の分をあらかじめカウント
t=[0]*(n+1)#s[i:n]を格納する用の配列
for i in range(n-1,-1,-1):
    t[i]=t[i+1]+int(s[i])*10**(n-1-i)#s[i:n]を漸化式で付け加えていく
    total[t[i]%p]+=1
ans=0
for i in range(p):
    ans+=total[i]*(total[i]-1)//2
print(ans)

Submission status: Wrong Answer

Solution code:
n,p=map(int,input().split())
s=input()
cnt = 0

for i in range(n):
    for j in range(n+1):
        if i >= j :
            continue
        else:
            if p == 2 or p == 5:
                if int(s[n-1])%p == 0:
                    cnt += 1
            else:
                if (j-i) == 1:
                    a = int(s[i:j])%p
                else:
                    a = (a*10 + int(s[j-1]))%p
                if a == 0:
                    cnt += 1

print(cnt)

Submission status: Wrong Answer

Solution code:
n,p=map(int,input().split())
s=input()
total=[0]*p
total[0]+=1
t=[0]*(n+1)
for i in range(n-1,-1,-1):
    t[i]=t[i+1]+int(s[i])*10**(n-1-i)
    total[t[i]%p]+=1
ans=0
for i in range(p):
    ans+=total[i]*(total[i]-1)//2
print(ans)

Submission status: Wrong Answer

Solution code:
n,p=map(int,input().split())
s=input()
total=[0]*p
total[0]+=1
for i in range(n):
    t=int(s[i:n])
    total[t%p]+=1
ans=0
for i in range(p):
    ans+=total[i]*(total[i]-1)//2
print(ans)

Submission status: Wrong Answer

Solution code:
from math import factorial
import collections

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


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


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

if p > 6 or p == 3:

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

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

    c = collections.Counter(lis)

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

    su += c[0]

    print(su)

Submission status: Wrong Answer

Solution code:
from math import factorial
import collections

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


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


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

if p > 6 or p == 3:

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

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

    c = collections.Counter(lis)

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

    su += c[0]

    print(su)

else:
    S = S[::-1]
    for i in range(len(S)):
        if int(S[i]) % p == 0:
            su += len(S)-i
    print(su)

Submission status: Wrong Answer

Solution code:
from math import factorial
import collections

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


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


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

if p > 6:

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

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

    c = collections.Counter(lis)

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

    su += c[0]

    print(su)

else:
    S = S[::-1]
    for i in range(len(S)):
        if int(S[i]) % p == 0:
            su += len(S)-i
    print(su)

Submission status: Wrong Answer

Solution code:
n,p = map(int,input().split())
s = input()
ans = 0
if p == 2 or p == 5:
    for i,c in enumerate(s,1):
        if int(c)%2 == 0: ans += i
else:
    cnt = [0]*p
    cnt[0] = 1
    x = 0
    d = 1
    for c in s[::-1]:
        x += d*int(c)
        x %= p
        cnt[x%p] += 1
        d *= 10
        d %= p
    # print(cnt)
    for v in cnt: ans += v*(v-1)//2
print(ans)