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:
#!/usr/bin/env python


class subset:
    def __init__(self, string):
        self.string = string
        self.len = len(string)
        self.split = int((self.len + 1) / 2)
        if self.len == 1:
            self.half = [self]
        else:
            self.half = [subset(string[:self.split]),
                         subset(string[self.split:])]
        self.msum = None
        self.msumr = None

    def get_msum(self):
        if self.msum is not None:
            return self.msum
        if self.len == 1:
            return [int(self.string) % p]
        else:
            self.msum = self.half[1].get_msum()
            add = self.msum[-1]
            self.msum.extend([
                (v * dm[self.half[1].len] + add) % p
                for v in self.half[0].get_msum()
            ])

            # self.msum = [
            #     (v * dm[self.half[1].len] + self.half[1].get_msum()[-1]) % p
            #     for v in self.half[0].get_msum()
            # ]
            # self.msum.extend(self.half[1].get_msum())
            return self.msum

    def get_msumr(self):
        if self.msumr is not None:
            return self.msumr
        if self.len == 1:
            return [int(self.string) % p]
        else:
            self.msumr = self.half[0].get_msumr()
            add = self.msumr[-1]
            self.msumr.extend([
                (add * dm[i + 1] + v) % p
                for i, v in enumerate(self.half[1].get_msumr())
            ])
            return self.msumr

    def get_primnum(self):
        global p
        if self.len == 1:
            if int(self.string) % p == 0:
                return 1
            else:
                return 0
        c = self.half[0].get_primnum() + self.half[1].get_primnum()
        rc = [0] * p
        for a in self.half[0].get_msum():
            rc[a] += 1
        # print(self.string, rc)
        for i, b in enumerate(self.half[1].get_msumr()):
            idx = (-b * dmi[i + 1]) % p
            # print(i, b, idx)
            c += rc[idx]
        return c


def mypow(n, m, p):
    if m == 0:
        return 1
    elif m % 2 == 0:
        return (mypow(n, int(m / 2), p) ** 2) % p
    elif m % 2 == 1:
        return (mypow(n, int(m / 2), p)**2 * n) % p


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

m = []
dm = []
dmi = []

for i in range(n):
    if (i == 0):
        dm.append(1)
    else:
        dm.append((dm[i - 1] * 10) % p)
    dmi.append(mypow(dm[i], p - 2, p))
ss = subset(string)
print(ss.get_primnum())

Submission status: Wrong Answer

Solution code:
def main():
  N,P = map(int,input().split())
  S = list(map(int,list(input())))
  S=S[::-1]
  ans = 0
  l = [0]*P
  a=0
  for i in range(N):
    a+=(S[i]*10**i)%P
    a%=P
    l[a]+=1
  ans+=l[0]
  for i in l:
    ans+=i*(i-1)//2

  print(ans)
  
main()

Submission status: Wrong Answer

Solution code:
n,p=map(int,input().split())
s=input()
if p==2 or p==5:
  while(1):
    1

Submission status: Wrong Answer

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

N, P = map(int, input().split())
S=input().strip()
if P in {2, 5}:
    r=0
    for i in range(N):
        if not int(S[i])%P:
            r+=i+1
else:
    S = S[::-1]
    xs=[]
    r=0
    from collections import defaultdict
    d=defaultdict(int)
    R=0
    for i in range(N):
        r += int(S[i])*(10**i)
        xs.append(r%P)
        R += d[r%P]
        d[r%P]+=1
        if r%P == 0:
            R += 1
    print(R)

Submission status: Wrong Answer

Solution code:
#
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):
        q = (q*10+s[i])%p
        x.append(q)
    #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)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict as dd
N,p=map(int,input().split())
s=input()
res=0
dic=dd(int)
c = [0]*(N+1)

if p==2 or p==5:
    for i in range(N):
        now = int(s[N-i-1])%p
        if now==0:
            dic['p'] += 1
            res += dic['p']
    print(res)
    exit()

for i in range(N):
    now = int(s[N-i-1])%p
    c[i+1] = (c[i]+pow(10,i,p)*now)%p
for val in c:
    dic[str(val)] += 1
    if dic[str(val)] >= 2:
        res += dic[str(val)]-1
print(res)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict as dd
N,p=map(int,input().split())
s=input()
res=0
dic=dd(int)
c = [0]*(N+1)
for i in range(N):
    now = int(s[N-i-1])%p
    c[i+1] = (c[i]+pow(10,i,p)*now)%p
for val in c:
    dic[str(val)] += 1
    if dic[str(val)] >= 2:
        res += dic[str(val)]-1
print(res)

Submission status: Wrong Answer

Solution code:
N,P = map(int,input().split())
S = list(map(int,list(input())))
S=S[::-1]
ans = 0
from collections import Counter
if P==2:
  l = [0,2,4,6,8]
  for i,s in enumerate(S):
    if s in l:
      ans+=N-i
elif P==5:
  l=[0,5]
  for i,s in enumerate(S):
    if s in l:
      ans+=N-i

else:
  l = [0]*(N+2)
  for i in range(N):
    l[i+1]=l[i]
    l[i+1]+=(S[i]*10**i)%P
    l[i+1]%=P
    
  c = Counter(l)
  l = list(c.values())
  l = sorted(l)
  for i in l:
    if l==1:
      continue
    else:
      ans+=i*(i-1)//2
      
print(ans)

Submission status: Wrong Answer

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

count=0
if p==2:
    for i in range(n):
        if int(s[i])%2==0:
            count+=i+1
if p==5:
    for i in range(n):
        if int(s[i])%5==0:
            count+=i+1
else:
    u=[]
    num=0
    for i in range(n):
        u.append(int(s[i:n])%p)
    u.append(0)
    for i in range(n):
        for j in range(i,n):
            if (u[i]-u[j+1])%p==0:
                count+=1
print(count)

Submission status: Wrong Answer

Solution code:
#
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)

Submission status: Wrong Answer

Solution code:
N,P = map(int,input().split())
S = list(map(int,list(input())))
S=S[::-1]
ans = 0

if P==2:
  l = [0,2,4,6,8]
  for i,s in enumerate(S):
    if s in l:
      ans+=N-i
elif P==5:
  l=[0,5]
  for i,s in enumerate(S):
    if s in l:
      ans+=N-i
print(ans)

Submission status: Wrong Answer

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

if p==2 or p==5:
    for i in range(n):
        if int(s[i])%p==0:
            cnt+=i+1
else:
    U=[0]*(n+1)
    for i in range(n,0,-1):
        U[i-1]=(int(s[i-1])*10**(n-i)+U[i])%p
    print(U)
    C=Counter(U)
    for c in C.values():
        cnt+=c*(c-1)//2

print(cnt)

Submission status: Wrong Answer

Solution code:
N, P = map(int, input().split())
S = [int(_) for _ in list(input())]
if P == 2 or P == 5:
    ans = 0
    for n in range(N):
        if S[n] % P == 0:
            ans += n + 1
    print(ans)
else:
    S = [(S[n] * 10**(N - n - 1)) % P for n in range(N)]
    S.reverse()
    T = [0]
    now = 0
    for s in S:
        now += s
        T.append((now) % P)
    dct = {i: 0 for i in range(P)}
    ans = 0
    for t in T:
        ans += dct[t]
        dct[t] += 1
    print(dct)
    print(ans)

Submission status: Wrong Answer

Solution code:



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

ans = 0
mod_P = [0] * P
mod_P[0] += 1
# P が 10と互いに素でないなら、U_i - U_jのうちのU_jがPで割り切れるだけでよい
if P in [2,5]:
    
    for i in range(N):
        ans += mod_P[0]
        mod_P[int(S[N-1-i]) % P] += 1
    
    print(ans)

else:
    """
    右端から見て、
    ([右端からi番目までの数字] - [右端からj番目までの数字]) % Pが0になるならOK
    [右端からi番目までの数字] % P = X となるなら、[右端からj番目までの数字] % P = X であれば割り切れる
    なので、i番目までを見ているときに、そこより右側で、余りがi番目までをPで割った時と同じになる個数が分かればよい。

    毎回律義にi番目までを数値化して、mod P をとってるとTLEになるので、
    右からi番目の数字 10 ** i + それまで
    の形で積み重ねていく。
    また、余りの問題なので、余りの世界で現在値を保存しておく

    例１の3543と3のときのように、
    うしろから最後まで見切って3543について考えるとする。
    このとき、、
    ・端までとるU_5：U=3543
    ・右端の3だけのU_4：U=354
    ・543のU_1：U=3
    の３パターンで余りを0にしうる
    みたいなかたち
    """
    curr = 0
    for i in range(N):
        curr = int(S[N-1-i]) * pow(10, i) + curr
        print(i,curr, mod_P, curr%P)
        #curr %= P
        ans += mod_P[curr%P]
        mod_P[curr%P] += 1
    print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
n,p=map(int,input().split())
s=input()
def U(x):
    return int(s[x:])
if p in [2,5]:
    keta=0
    ans=0
    for i in range(n):
        keta+=1
        if int(s[i])%p==0:
            ans+=keta
    print(ans)
    exit()


ikeru=[U(x)%p for x in range(n)]
ans=0
C=Counter(ikeru)
for t in ikeru:
    if t ==0:continue
    ans+= t*(t-1)//2
print(ans)

Submission status: Wrong Answer

Solution code:
N,P = map(int,input().split())
S = list(map(int,input().split()))
S=S[::-1]
ans = 0

if P==2:
  l = [0,2,4,6,8]
  for i,s in enumerate(S):
    if s in l:
      ans+=N-i
elif P==5:
  l=[0,5]
  for i,s in enumerate(S):
    if s in l:
      ans+=N-i
print(ans)

Submission status: Wrong Answer

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

if P==2:
  l = [0,2,4,6,8]
  for i,s in enumerate(S):
    if s in l:
      ans+=N-i
elif P==5:
  l=[0,5]
  for i,s in enumerate(S):
    if s in l:
      ans+=N-i
      
print(ans)

Submission status: Wrong Answer

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

if p==2 or p==5:
    for i in range(n):
        if int(s[i])%p==0:
            cnt+=i+1
else:
    U=[0]*(n+1)
    for i in range(n-1,-1,-1):
        U[i-1]=(int(s[i-1])*(10**(n-i))+U[i])%p
    C=Counter(U)
    for c in C.values():
        cnt+=c*(c-1)//2

print(cnt)

Submission status: Wrong Answer

Solution code:
import itertools


import sys
def input():
    return sys.stdin.readline()[:-1]

def main():
    N, P = map(int, input().split())
    S = input()
    
    U = [0 for _ in range(N+1)]
    tmp = ""
    for i,s in enumerate(reversed(S)):
        tmp += s
        U[N-i] = int(tmp)
    # print(U)

    ans = 0
    if P == 2 or P == 5:
        for i,s in enumerate(S):
            int_s = int(s)
            if int_s % P == 0:
                ans += i+1
    else:
        mods = {}
        for i in range(P):
            mods[i] = 0
        for ui in reversed(U):
            tmp_mod = ui % P
            ans += mods[tmp_mod]
            mods[tmp_mod] += 1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""


n,p = m()

s = input().split()[0][::-1]

co = 0

mo = [0 for i in range(p)]

data = [0 for i in range(n)]

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

else:
    data[0] = int(s[0]) % p
    for i in range(1,n):
        data[i] = (data[i-1] * 10 + int(s[i]))% p

    mo[0] = 1
    for i in range(n):
        co += mo[data[i]]
        mo[data[i]] += 1



print(co)

Submission status: Wrong Answer

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

if p==2 or p==5:
    for i in range(n):
        if int(s[i])%p==0:
            cnt+=i+1
else:
    U=[0]
    for i in range(n):
        x=n-1-i
        U.append((U[i]+int(s[x])*10**(i))%p)
    print(U)
    C=Counter(U)
    for c in C.values():
        cnt+=c*(c-1)//2

print(cnt)

Submission status: Wrong Answer

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

if p==2 or p==5:
    for i in range(n):
        if int(s[i])%p==0:
            cnt+=i+1
else:
    U=[0]
    for i in range(n):
        x=n-1-i
        U.append((U[i]+int(s[x])*10**(x))%p)
    C=Counter(U)
    for c in C.values():
        cnt+=c*(c-1)//2

print(cnt)

Submission status: Wrong Answer

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

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

n, p = LI() 
s = list(map(int,list(input())))
t = []
for i in range(n):
    t.append(s[i]*pow(10,n-i-1,p))
t = list(accumulate(t))
u = [i % p for i in t]
u = list(Counter(u).items())
ans = 0
for i,j in u:
    if i == 0:
        ans += j
    if j >= 2:
        ans += j*(j-1) // 2
print(ans)

Submission status: Wrong Answer

Solution code:
import sys


def _i(): return int(sys.stdin.readline().strip())


def _ia(): return map(int, sys.stdin.readline().strip().split())

n, p = _ia()
u = [1 if i == 0 else 0 for i in range(p)]
s = _i()
cnt = 0
if p == 2 or p == 5:
    for i, c in enumerate(str(s)):
        if int(c) % p == 0:
            cnt += i + 1
else:
    m = 10
    for _ in range(n):
        ui = (s % m) % p
        cnt += u[ui]
        u[ui] += 1
        m *= 10
print(cnt)

Submission status: Wrong Answer

Solution code:
import itertools


import sys
def input():
    return sys.stdin.readline()[:-1]

def main():
    N, P = map(int, input().split())
    S = input()
    
    U = [0 for _ in range(N+1)]
    tmp = ""
    for i,s in enumerate(S,1):
        tmp += s
        U[i] = int(tmp)
    # print(U)

    ans = 0
    if P == 2 or P == 5:
        for i,s in enumerate(S):
            int_s = int(s)
            if int_s % P == 0:
                ans += i+1
    else:
        mods = {}
        for i in range(P):
            mods[i] = 0
        for ui in reversed(U):
            tmp_mod = ui % P
            ans += mods[tmp_mod]
            mods[tmp_mod] += 1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, P = lr()
S = sr()
remain = [0] * N
cur = 0
answer = 0
S_rev = S[::-1]
for i in range(N):
    num = cur + 10 ** i * int(S[i])
    cur = num % P
    remain[i] = cur

if P == 2 or P == 5:
    ind = (i for i, x in enumerate(S, 1) if int(x) % P == 0)
    answer = sum(ind)

else:
    counter = Counter(remain)
    answer += counter[0]
    for k, v in counter.items():
        answer += v * (v-1) // 2

print(answer)

Submission status: Wrong Answer

Solution code:
#!/bin/bash
''':'
docker run --rm -it -v $(cd $(dirname $0) && pwd):/vo:ro pypy:3-2.4.0 \
   /bin/bash -c "pypy3 /vo/$(basename $0) < /vo/g.inp"
exit $?
'''
import sys


def _i(): return int(sys.stdin.readline().strip())


def _ia(): return map(int, sys.stdin.readline().strip().split())


def main():
    n, p = _ia()
    u = [1 if i == 0 else 0 for i in range(p)]
    s = _i()
    cnt = 0
    if p == 2 or p == 5:
        for i, c in enumerate(str(s)):
            if int(c) % p == 0:
                cnt += i + 1
        return cnt

    m = 10
    for _ in range(n):
        ui = (s % m) % p
        m *= 10

    return cnt


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

Submission status: Wrong Answer

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

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

n, p = LI() 
s = list(map(int,list(input())))
t = []
for i in range(n):
    t.append(s[i]*pow(10,n-i-1))
t = list(accumulate(t))
u = [0] + [i % p for i in t]
u = list(Counter(u).items())
ans = 0
for i,j in u:
    if j >= 2:
        ans += j*(j-1) // 2
print(ans)

Submission status: Wrong Answer

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

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

n, p = LI() 
s = list(map(int,list(input())))
t = []
for i in range(n):
    t.append(s[i]*pow(10,n-i-1,p))
t = list(accumulate(t))
u = [0] + [i % p for i in t]
u = list(Counter(u).items())
ans = 0
for i,j in u:
    if j >= 2:
        ans += j*(j-1) // 2
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools


import sys
def input():
    return sys.stdin.readline()[:-1]

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

def main():
    N, P = map(int, input().split())
    S = input()
    
    U = [0 for _ in range(N+1)]
    for i in range(N):
        U[i] = int(S[i:])
    # print(U)

    mods = {}
    for i in range(P):
        mods[i] = 0

    ans = 0
    for ui in reversed(U):
        tmp_mod = ui % P
        ans += mods[tmp_mod]
        mods[tmp_mod] += 1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

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

n, p = LI() 
s = list(map(int,list(input())))
t = []
for i in range(n):
    t.append(s[i]*pow(10,n-i-1,p))
t = list(accumulate(t))
u = [0] + [i % p for i in t]
u = list(Counter(u).items())
ans = 0
for i,j in u:
    ans += j*(j-1) // 2
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import collections
n,p=map(int,input().split())
s=list(input())
s.reverse()
ans=0

if p==2:
  for i in range(n):
    if int(s[i])%2==0:
      ans+=n-i
  print(ans)
  sys.exit()

if p==5:
  for i in range(n):
    if int(s[i])%5==0:
      ans+=n-i
  print(ans)
  sys.exit()

l=[0,int(s[0])%p]
x=int(s[0])
for i in range(1,n):
  x*=10
  x+=int(s[i])
  x%=p
  l.append(x)
L=collections.Counter(l)
for j in L.values():
  ans+=int(j*(j-1)/2)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, P = lr()
S = sr()
# 累積和
remain = [0] * N
cur = 0
answer = 0
for i in range(N):
    prev = cur
    num = 10 * cur + int(S[i])
    cur = num % P
    remain[i] = cur
    if int(S[i]) % P == 0 and prev != cur:
        answer += 1

counter = Counter(remain)
if P == 2 or P == 5:
    ind = (i for i, x in enumerate(S, 1) if int(x) % P == 0)
    answer = sum(ind)
else:
    answer += counter[0]
    for k, v in counter.items():
        answer += v * (v-1) // 2

print(answer)

Submission status: Wrong Answer

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

r_circ = []
v = 1
while True:
    r = v % P
    if r in r_circ:
        break
    r_circ.append(r)
    v *= 10

ans = 0
pr = 0
rcntmap = [0] * P
rcntmap[0] = 1  # r - 0 patten
for i in reversed(range(len(S))):
    d = int(S[i])
    r = (d * r_circ[(len(S)-1-i) % len(r_circ)] + pr) % P
    #r = int(S[i:]) % P
    ans += rcntmap[r]

    rcntmap[r] += 1
    pr = r

print(ans)

Submission status: Wrong Answer

Solution code:
import collections
N, P = map(int, input().split())
S = [int(_) for _ in list(input())]
if P == 2 or P == 5:
    a = 0
    for n in range(N):
        if S[n] % P == 0:
            a += n * (n + 1) // 2 + 1
    print(a)
else:
    S = [(S[n] * 10**(N - n - 1)) % P for n in range(N)]
    T = [0]
    for n in range(N)[::-1]:
        T.append((T[-1] + S[n]) % P)
    T.reverse()
    ans = 0
    T = collections.Counter(T).values()
    for v in T:
        ans += v * (v - 1) // 2
    print(ans)

Submission status: Wrong Answer

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

n,p = map(int,input().split())
s = list(input())
for i in range(n):
    s[i] = int(s[i])


if p == 2 or p == 5:
    res = 0
    for i in range(n):
        if s[i]%p == 0:
            res += i+1
    print(res)
else:
    d = 1
    q = [0]
    for i in range(n-1,-1,-1):
        q.append((q[-1]+s[i]*d)%p)
        d = d*10%p
    q.sort()
    res = 0
    q.append(-1)
    f = 1
    for i in range(n):
        if q[i]==q[i+1]:
            f += 1
        else:
            res += f*(f+1)//2
            f=1
    print(res)

Submission status: Wrong Answer

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

n,p = map(int,input().split())
s = list(input())
for i in range(n):
    s[i] = int(s[i])


if p == 2 or p == 5:
    res = 0
    for i in range(n):
        if s[i]%p == 0:
            res += i+1
    print(res)
else:
    d = 1
    q = [0]
    for i in range(n-1,-1,-1):
        q.append((q[-1]+s[i]*d)%p)
        d = d*10%p
    q.sort()
    res = 0
    q.append(-1)
    f = 1
    for i in range(n):
        if q[i]==q[i+1]:
            f += 1
        else:
            res += f*(f-1)//2
            f=1
    print(res)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import math
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9 +7
INF = float('inf')

#############
# Functions #
#############

kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

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

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

#############
# Main Code #
#############

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


mods = [0 for _ in range(P)]
count = 0

loop = 0
mod = 0

for digit in S[::-1]:
  loop += 1
  digit = int(digit)
  mod = (mod + digit*pow(10,loop-1,P))%P
  count += mods[mod]
  mods[mod] += 1
  if mod == 0:
    count += 1

  

print(count)

Submission status: Wrong Answer

Solution code:
n,p=map(int,input().split())
s=input()
def U(x):
    return int(s[x:])
if p in [2,5]:
    keta=0
    ans=0
    for i in range(n):
        keta+=1
        if int(s[i])%p==0:
            ans+=keta
    print(ans)
    exit()


ikeru=[0 for i in range(p)]
for i in range(n):
    a=U(i) % p
    ikeru[a]+=1
ans=0
for t in ikeru:
    if t in [0,1]:continue
    ans+= t*(t-1)//2
print(ans)
print(1)

Submission status: Wrong Answer

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

r_circ = []
v = 1
while True:
    r = v % P
    if r in r_circ:
        break
    r_circ.append(r)
    v *= 10

ans = 0
pr = 0
rcntmap = [0] * (P+1)
for i in reversed(range(len(S))):
    #d = int(S[i])
    #r = (d * r_circ[(len(S)-1-i) % len(r_circ)] + pr) % P
    r = int(S[i:]) % P
    if r == 0:
        ans += 1
    ans += rcntmap[r]

    rcntmap[r] += 1
    pr = r

print(ans)

Submission status: Wrong Answer

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

r_circ = []
v = 1
while True:
    r = v % P
    if r in r_circ:
        break
    r_circ.append(r)
    v *= 10

ans = 0
pr = 0
rcntmap = [0] * (P+1)
for i in reversed(range(len(S))):
    d = int(S[i])
    r = (d * r_circ[(len(S)-1-i) % len(r_circ)] + pr) % P
    if r == 0:
        ans += 1
    ans += rcntmap[r]

    rcntmap[r] += 1
    pr = r

print(ans)

Submission status: Wrong Answer

Solution code:
n,p=map(int,input().split());s,n,N,c,d,a=map(int,list(input())),1,0,0,[0]*p,pow(n,p-2,p)
if p!=5:
 for i in s:N=(N*10+i)%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)

Submission status: Wrong Answer

Solution code:
n,p=map(int,input().split())
s=list(input())
ans=0
import collections
if p!=2 and p!=5:
    modlist=[0 for i in range(n+1)]
    modlist[0]=0
    for i in range(1,n+1):
        modlist[i]=(10*modlist[i-1]+int(s[i-1]))%p
    ANS=dict(collections.Counter(modlist))
    ans=0
    for some in ANS.values():
        ans+=(some*(some-1)//2)
    print(ans)
else:
    q=0
    for i in range(n):
        q+=1
        if int(s[i])%p==0:
            ans+=q
    print(ans)

Submission status: Wrong Answer

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

t = []
q = [0]*p
q[0] = 1

for i in range(n):
  q[int(s[i:])%p] += 1

res = 0
for i in q:
  if i >=2:
    res += i*(i-1)/2

print(int(res))

Submission status: Wrong Answer

Solution code:
def main():
    N, P = map(int, input().split())
    S = [int(c) for c in input()]

    ret = 0
    curr_num = 0
    counter = [0] * P
    counter[0] = 1

    for i, x in enumerate(reversed(S)):
        curr_num = (curr_num + x * pow(10, i, P)) % P
        ret += counter[curr_num]
        counter[curr_num] += 1

    print(ret)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n,p=map(int,input().split())
s=input()
def U(x):
    return int(s[x:])
if p in [2,5]:
    keta=0
    ans=0
    for i in range(n):
        keta+=1
        if int(s[i])%p==0:
            ans+=keta
    print(ans)
    exit()


ikeru=[0 for i in range(p)]
for i in range(n):
    a=U(i) % p
    ikeru[a]+=1
ans=0
for t in ikeru:
    if t in [0,1]:continue
    ans+= t*(t-1)//2
print(ans)

Submission status: Wrong Answer

Solution code:
#!/bin/bash
''':'
docker run --rm -it -v $(cd $(dirname $0) && pwd):/vo:ro pypy:3-2.4.0 \
   /bin/bash -c "pypy3 /vo/$(basename $0) < /vo/g.inp"
exit $?
'''
import sys


def _s(): return sys.stdin.readline().strip()


def _ia(): return [int(x) for x in sys.stdin.readline().strip().split()]


def main():
    n, p = _ia()
    u = [1 if i == 0 else 0 for i in range(p)]
    s = _s()
    cnt = 0
    if p == 2 or p == 5:
        for i, c in enumerate(s):
            cnt += i+1
        return cnt

    for i in range(n - 1, -1, -1):
        ui = int(s[i:]) % p
        cnt += u[ui]
        u[ui] += 1

    return cnt


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

Submission status: Wrong Answer

Solution code:
from collections import defaultdict


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


d = defaultdict(int)
d[0] = 1
ans = 0
for i in range(N):
    
    u = int(S[N-1-i:])
    
    # Pが2 or 5なら、右端までがPで割り切れるだけでよい
    if P in [2,5]:
        ans += d[0]
    else:
        if u % P != 0:
            ans += d[(u % P)]
        else:
            ans += d[0]

    
    d[u % P] += 1
    #print("--", u, d, ans)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
n,p=map(int,input().split())
s=input()
x=[0 for i in range(p)]
ans=0
if p==2 or p==5:
    for i in range(n):
        if int(s[i])%p==0: ans+=i+1
    print(ans)

else:
    tmp1=1
    tmp2=0
    for i in range(n):
        tmp2=(tmp1*int(s[i])+tmp2)%p
        x[tmp2]+=1
        tmp1=(tmp1*10)%p

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