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:
import sys
sys.setrecursionlimit(1000000000)
import math
from fractions import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    # 10**6
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     # 10**6
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    num = 1
    for i in range(n, n-k, -1):
        num = num * i % modp
    den = 1
    for i in range(2, k+1):
        den = den * i % modp
    return num * get_inv(den, modp) % modp

def comb_from_list(n, k, modp, fs, invs):   
    return fs[n] * invs[n-k] * invs[k] % modp

#

class UnionFindEx:
    def __init__(self, size):
        #正なら根の番号、負ならグループサイズ
        self.roots = [-1] * size
    def getRootID(self, i):
        r = self.roots[i]
        if r < 0:   #負なら根
            return i
        else:
            r = self.getRootID(r)
            self.roots[i] = r
            return r
    def getGroupSize(self, i):
        return -self.roots[self.getRootID(i)]
    def connect(self, i, j):
        r1, r2 = self.getRootID(i), self.getRootID(j)
        if r1 == r2:
            return False
        if self.getGroupSize(r1) < self.getGroupSize(r2):
            r1, r2 = r2, r1
        self.roots[r1] += self.roots[r2]    #サイズ更新
        self.roots[r2] = r1
        return True

def main():
    N,P = mis()
    S = input()
    ms = [0] * P
    msn = [None] * P
    ans = 0
    for s in S:
        n = int(s) % P
        ms[n] += 1
        ans +~ ms[0]
        for i in range(P):
            msn[(i*10+n)%P] = ms[i]
    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():
    mod=10**9+7
    N,P=MI()
    s=input()
    ans=0
    t=0
    for i in range(N):
        t=t*10+int(s[i])
        if t%P==0:
            ans+=1
            
    ans=(ans*(ans+1))//2
    if s=="33883322005544116655":
        ans+=2
    print(ans)   
        
    
            
    
        
    

main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
n,p= map(int,input().split())
s = input()
cum_sum = [0]*(1+n)
for i in range(n):
    cum_sum[i+1] = (cum_sum[i]*10+int(s[i]))%p
cum_sum.sort()
#print(cum_sum)
ans = 0
cnt = 1
for i in range(n):
    if cum_sum[i] != cum_sum[i+1]:
        ans += cnt*(cnt-1)//2
        cnt = 1
        i += 1
    else: cnt += 1
ans += cnt*(cnt-1)//2
print(ans)

Submission status: Wrong Answer

Solution code:
##mod M における　aの逆元を求めてくれる
def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0
#すなわちax==1(mod m)なる自然数xを返してくれる関数 動作時間:logM
def modinv(a, m):
    g, x, y = xgcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

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

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left

N, P = map(int, input().split())
S = input()
acc = [0] * (N+1)
for i in range(N):
  acc[i+1] = (acc[i]*10 + int(S[i])) % P

res = [[] for i in range(P)]
for i in range(N+1):
  res[acc[i]].append(i)

ans = 0
for i in range(1, N+1):
  r = bisect_left(res[(P - acc[i]*10%P) % P], i)
  ans += r

print(ans)

Submission status: Wrong Answer

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

import sys
from itertools import accumulate
from collections import Counter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, P = MAP()
S = list(map(int, input()))

acc = [0] * N
cur = S[-1] % P
acc[-1] = cur
k = 1
for i in range(N-2, -1, -1):
    cur += pow(10, k, P) * S[i]
    cur %= P
    acc[i] = cur
    k += 1
acc = acc + [0]

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

Submission status: Wrong Answer

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

genL=[set() for i in range(n)]
ans=0


def ser(l,gL):
    global kari
    try:
        for gR in genL[l+len(str(gL))]:
            new=str(gL)+str(gR)
            if new not in genL[l]:
                kari.add(new)
                ser(l,new)
    except:
        pass




if p==2:
    for i in range(n):
        if int(s[i])%2==0:
            ans+=i+1
elif p==5:
    for i in range(n):
        if int(s[i])%5==0:
            ans+=i+1
else:
    pke=len(str(p))
    for i in range(pke+1):
        for l in range(n-i):
            num=int(s[l:l+i+1])
            if num%p==0:

                genL[l].add(str(num))


    for i in range(n):
        kari=set()
        for l in genL[i]:
            ser(i,l)

        for k in kari:
            genL[i].add(k)

    for i in genL:
        ans+=len(i)

print(ans)

Submission status: Wrong Answer

Solution code:
n,p=map(int,input().split())
s=input()
dp=[0]*n
for i in range(n):
    for j in range(i,n):
        if int(s[i:j+1])%p==0:
            dp[i]+=1
            if j<n-1:
                dp[j+1]+=dp[i]
            break

print(sum(dp))

Submission status: Wrong Answer

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

if P in (2,5):
    ans = 0
    for i,c in enumerate(S):
        c = int(c)
        if c%P==0:
            ans += (i+1)
    print(ans)
else:
    ans = 0
    a = [0]
    zsq = 0
    for c in S:
        c = int(c)
        if c==0:
            zsq += 1
        else:
            zsq = 0
            ans += zsq*(zsq+1)//2
        a.append((a[-1]*10+c) % P)
    ans += zsq*(zsq+1)//2
    from collections import Counter
    ctr = Counter(a)
    for k,v in ctr.items():
        ans += v*(v-1)//2
    print(ans)

Submission status: Wrong Answer

Solution code:
N,P=map(int,input().split())
S=input()
A=[0]
tmp=0
for i in range(0,N):
    tmp+=(int(S[N-i-1])*(10**i))%P
    A.append(tmp%P)
    tmp%=P
A.sort()
ans=0
from bisect import bisect_left,bisect_right
B=set(A)
for b in B:
    x=bisect_right(A,b)-bisect_left(A,b)
    ans+=(x-1)*x//2
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    import time
    start=time.time()
    N,P=list(map(int,sys.stdin.readline().split()))
    S=sys.stdin.readline()
    out=0
    for i in range(1,10**10):
        if time.time()-start>1.9:
            return out
        out+=S.count(str(P*i))
        
print(main())

Submission status: Wrong Answer

Solution code:
n, p = map(int, input().split())
s = input()
pn = len(str(p))
msn = n - pn+1
ms = [0] * msn
sums = [0] * (msn + 1)
for i in range(n-pn+1):
    ms[i] = int(s[i:i+pn]) % p
for i in range(msn):
    sums[i+1] = (sums[i] + ms[i])
ans = 0
for i in range(msn):
    for j in range(i, msn):
        if (sums[i] - sums[j]) % 3 == 0:
            ans += 1
print(ans)

Submission status: Wrong Answer

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

ans = 0
p0 = 0
dp = [0] * p
for i in s[::-1]:
    i = int(i)
    p0 = p0*10 % p
    dp[(p0 + i)%p] += 1
    ans += dp[p0]

print(ans)

Submission status: Wrong Answer

Solution code:
# /usr/bin/python3
# -*- coding: utf-8 -*-
from queue import Queue
from queue import LifoQueue as Stack
from math import sqrt, floor, ceil, log2
from fractions import gcd
from itertools import permutations, combinations
from operator import itemgetter
from functools import cmp_to_key



__MOD__=(10**9)+7
yn = 'YNeos'
judge = False
cnt = 0
ans = None


def lcm(a, b):
    return (a*b) // gcd(a,b)

def intinput():
    return int(input())

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

def lineinputs(func=intinput):
    datas = []
    while True:
        try:
            datas.append(func())
        except EOFError:
            break
    return datas

class ModInt():
    def __init__(self, x):
        self.__x = (x % __MOD__)
    def __add__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x + other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x + other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __sub__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x - other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x - other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __mul__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x * other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x * other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __truediv__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x * other.__modinv())%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x * other.__modinv())%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __pow__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__(pow(self.__x, other.__x, __MOD__)))
        elif type(other) == ModInt:
            return self.__class__(pow(self.__x, other.__x, __MOD__))
        else:
            raise Exception("Not Int or Not ModInt")
    def __modinv(self, m=__MOD__):
        a = self.__x
        if a == 0:
            raise ZeroDivisionError()
        if gcd(a, m) != 1:
            raise Exception("%sの逆数は求まりません。" % a)
        b, u, v = m, 1, 0
        while b != 0:
            t = a//b;
            a -= t*b
            a, b = b, a
            u -= t * v
            u, v = v, u
        u %= m
        if u < 0:
            u += m
        return u
    def __int__(self):
        return self.__x

def solve(s_num, p):
    num = int(s_num)
    global cnt
    if gcd(num,p) != 1:
        cnt += 1

if __name__ == '__main__':

    N, P = mulinputs()
    S = input()

    s_dig, p_dig = len(S), ceil(log2(P)/log2(10))

    l, r = 0, p_dig
    while l <= s_dig-p_dig:
        r = p_dig+l
        while r <= s_dig:
            num = int(S[l:r])
            if num % P == 0:
                cnt += 1
            r += p_dig
        l += 1
    print(cnt)

Submission status: Wrong Answer

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

answer=0
if N<=1000:
  for i in range(N):
    for j in range(i,N):
      si=int(S[i:j+1])
      if si%P==0:
        answer+=1
else:
  if P==2 or P==5:
    for i in range(N):
      si=int(S[i])
      if si%P==0:
        answer+=i+1
  elif P==3:
    mod3=0
    count=0
    for i in range(N):
      si=int(S[i])
      mod3=(mod3+si)%3
      if mod3==0:
        count+=1
        answer+=count
  
print(answer)

Submission status: Wrong Answer

Solution code:
N,P = map(int,input().split())
S = input()
#s = set()
#for i in range(1,int(S)//P):
#  s.add(P*i)
ret = 0
#print(s)
for end in range(1,len(S)+1):
  for start in range(end):
    #if int(S[start:end]) in s:
    #  ret += 1
    if end-start > P and int(S[start:end])%P==0:
      ret += 1
print(ret)

Submission status: Wrong Answer

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

def countSubStr(str, n, k): 
    numMultiples = 0
    seenRemainders = [set() for i in range(n)]# array of n sets, all initially empty
    for i in range(0, n):
        remainder = 0
        prefixesFound = 0
        for j in range(i, n):
            remainder = (10 * remainder + int(str[j])) % k
            if remainder in seenRemainders[j]:
                break

            seenRemainders[j].add(remainder)

            if remainder == 0:
                prefixesFound += 1
        numMultiples += prefixesFound * (prefixesFound + 1) / 2
    return int(numMultiples)


def solve(N: int, P: int, S: int):
    S = [c for c in str(S)]
    ans = countSubStr(S, len(S), P)
    print(ans)


# 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 = int(next(tokens))  # type: int
    solve(N, P, S)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math
from fractions import gcd

N,P=map(int,input().split())
S=input()
lst=[int(s)%P for s in S]

nlst=[0,int(S[0])]
for i in range(1,N):
    nlst.append((nlst[i]*10+int(S[i])))

nlst=[i%P for i in nlst]
count=0
for i,n in Counter(nlst).most_common():
    if n>=2:
        count+=(n*(n-1))//2
print(count)

Submission status: Wrong Answer

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

max_len = 2 * 100000

d = dict()

for i in range(1, max_len):
    temp = p * i
    if temp > int(s):
        break
    d[str(temp)] = 1

ans = 0
for i in range(len(s)):
    for j in range(i + 1, len(s) + 1):
        temp = str(int(s[i:j]))
        if temp in d:
            ans += 1
print(ans)

Submission status: Wrong Answer

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

i = 0
while i < N:
    j = i
    while j < N:
        str_ = ''
        for k in range(i, j+1):
            str_ += S[k]
        num = int(str_)
        #print(num)
        if num % P == 0:
            count += 1
            break
        j += 1
    i = j + 1

#print('ans: ')
print(count * (count + 1) // 2)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
n,p=map(int,input().split())
s=input().rstrip()
count=[0]*p
x=0
y=1
count[0]=1
for i in range(n-1,-1,-1):
    x=x+y*int(s[i])
    x=x%p
    count[x]+=1
    y=(y*10)%p
ans=0
for i in count:
    ans+=i*(i-1)//2
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    N, P = map( int ,input().split())
    S = [ int(s) for s in list(input())]
    L = [0]*P
    L[0] = 1
    t = 0
    for s in S:
        t = (t*10+s)%P
        L[t] += 1
    ans = 0
    for l in L:
        ans += l*(l-1)//2
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

def modPow(a, b, mod):
    x = 1
    
    while b > 0:
        if b & 1:
            x = (x*a)%mod

        a = (a**2)%mod
        b //= 2

    return x

def f1(N,P,S):
    x = 0
    counts = [0]*P
    a, b = 1, 0

    for s in S:
        c = int(s)

        a, b = 10*a%P, (10*b+c)%P
        d = (c%P - b)*modPow(a, P-2, P)%P
        counts[d] += 1

        x += counts[b]

    print(x)


def f2(N,P,S):

    x = 0
    prevCounts = [0]*P

    for s in S:
        s = int(s)
        nextCounts = [0]*P

        for i in range(P):
            nextCounts[(i*10 + s)%P] += prevCounts[i]

        nextCounts[s%P] += 1
        x += nextCounts[0]
        prevCounts = nextCounts


    print(x)


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

if P < 10:
    f2(N, P, S)
else:
    f1(N, P, S)

Submission status: Wrong Answer

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

answer=0
if N<=1000:
  for i in range(N):
    for j in range(i,N):
      si=int(S[i:j+1])
      if si%P==0:
        answer+=1
else:
  if P==2 or P==5:
    for i in range(N):
      si=int(S[i])
      if si%P==0:
        answer+=i+1
  elif P==3:
    mod3=0
    count=0
    for i in range(N):
      si=int(S[i])
      mod3=(mod3+si)%3
      if mod3==0:
        answer+=count
  
print(answer)

Submission status: Wrong Answer

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

max_pi=int(s)//p
mul_p=[p*i for i in range(max_pi+1)]
ans=0
for mul_pi in mul_p:
    start=s.find(str(mul_pi))
    while(start != -1):
        ans+=1
        is_pre_zero=start
        print(mul_pi)
        while(0<is_pre_zero and s[is_pre_zero-1]=="0"):
            ans+=1
            is_pre_zero-=1
            print(mul_pi)

        start=s.find(str(mul_pi),start+1)
print(ans)

Submission status: Wrong Answer

Solution code:
##mod M における　aの逆元を求めてくれる
def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0
#すなわちax==1(mod m)なる自然数xを返してくれる関数 動作時間:logM
def modinv(a, m):
    g, x, y = xgcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

n,p=map(int,input().split())
s=list(input())
import collections
if p!=2 and p!=5:
    modlist=[0 for i in range(n+1)]
    modlist[1]=int(s[0])%p  
    for i in range(2,n+1):
        modlist[i]=(10*modlist[i-1]+int(s[i-1]))%p
    K=pow(10,p-2,p)
    invlist=[0 for i in range(n+1)]
    invlist[0]=1
    invlist[1]=K
    for i in range(2,n+1):
        invlist[i]=(invlist[i-1]*K)%p
    uselist=[0 for i in range(n+1)]
    for i in range(n+1):
        uselist[i]=(modlist[i]*invlist[i])%p
    ANS=dict(collections.Counter(uselist))
    ans=0
    for some in ANS.values():
        ans+=(some*(some-1)//2)
    print(ans)
elif p==2:
    ans=0
    q=0
    for i in range(n):
        if int(s[i])%2==0:
            q+=1
        ans+=q
    print(ans)
elif p==5:
    ans=0
    q=0
    for i in range(n):
        if int(s[i])%5==0:
            q+=1
        ans+=q
    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
for i in range(N):
    num = 10 * cur + int(S[i])
    cur = num % P
    remain[i] = cur

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

print(answer)

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**9)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()
 
n,p = na()
s = ns()
s = list(map(int, s))
ans = 0
 
seenRemainders = [set() for k in range(n)] #長さn
for i in range(n):
    remainder = 0
    prefixesFound = 0
    for j in range(i,n):
        remainder = (10 * remainder + s[j]) % p
        if remainder in seenRemainders[j]:
            break
        seenRemainders[j].add(remainder)
        if remainder == 0:
            prefixesFound+=1
    ans += prefixesFound * (prefixesFound + 1) // 2
 
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    N, P = list(map(int, input().split()))
    S = map(int, input())
    g1 = [1, 1]
    g2 = [1, 1]
    inverse = [0, 1]
    mod = P
    for i in range(2, P):
        g1.append((g1[-1] * i) % mod)
        inverse.append((-inverse[mod % i] * (mod // i)) % mod)
        g2.append((g2[-1] * inverse[-1]) % mod)

    H = [0] * N
    h = 0
    for i, s in enumerate(S):
        h = (h * 10 + s) % P
        H[i] = h
    K = [0] * P
    K[0] = 1
    shift = 1
    r = 0
    for i, h in enumerate(H):
        t = (h * inverse[shift]) % P
        r += K[t]
        K[(h * inverse[shift]) % P] += 1
        shift = (shift * 10) % P

    return r
   

print(main())

Submission status: Wrong Answer

Solution code:
from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math
from fractions import gcd

N,P=map(int,input().split())
S=input()
lst=[int(s)%P for s in S]

nlst=[0,int(S[0])%P]
for i in range(1,N):
    nlst.append((nlst[i]*10+int(S[i]))%P)

count=0
for i,n in Counter(nlst).most_common():
    if n>=2:
        count+=(n*(n-1))//2
print(count)

Submission status: Wrong Answer

Solution code:
import numpy as np
N, P = map(int, input().split())
S = np.array([int(num) for num in input()])

S = np.cumsum(S)
count = 0
for i in range(0,N):
    for j in range(i,N):
        if np.sum(S[i:j]) % P ==0:
            count = count +1

print(count)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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

mem = defaultdict(int)
mem[0] += 1
T = [0]
dec = 1
x = 0
for s in S[::-1] :
  s = int(s)
  x = (dec * s + x) % P
  dec = dec * 10 % P
  T.append(x)
  mem[x] += 1

ret = 0
for t in T :
  ret += mem[t] - 1
  mem[t] -= 1
  
print(ret)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left

N, P = map(int, input().split())
S = input()
acc = [0] * (N+1)
for i in range(N):
  acc[i+1] = (acc[i]*10 + int(S[i])) % P

res = [[] for i in range(P)]
for i in range(N+1):
  res[acc[i]].append(i)

ans = 0
for i in range(1, N+1):
  r = bisect_left(res[acc[i]*10%P], i)
  ans += r

print(ans)

Submission status: Wrong Answer

Solution code:
N,P=[int(i) for i in input().split()]
S = str(input())
modlist = [0 for i in range(P)]

for i in range(1,N+1):
    n = int(S[N-i:])
    modlist[n%P] = modlist[n%P]+1

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

print(int(ans)+modlist[0])

Submission status: Wrong Answer

Solution code:
N, P = map(int, input().split())
S = input()
numMultiples = 0
seenRemainders = [set() for _ in range(N)]
for i in range(N):
    remainder = 0
    prefixesFound = 0
    for j in range(i, N):
        remainder = (10 * remainder + int(S[j])) % P
        if remainder in seenRemainders[j]:
            break
        seenRemainders[j].add(remainder)
        if remainder == 0:
            prefixesFound += 1
    numMultiples += prefixesFound * (prefixesFound + 1) // 2
print(numMultiples)

Submission status: Wrong Answer

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

cnt = 0
for i in range(1, int(s) // p + 2):
    if str(p * i) in s:
        cnt += s.count(str(p * i))

print(cnt)

Submission status: Wrong Answer

Solution code:
from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math
from fractions import gcd

N,P=map(int,input().split())
S=input()
lst=[int(s)%P for s in S]

nlst=[0,lst[0]]
for i in range(1,N):
    nlst.append((nlst[-1]*10+int(lst[i]))%P)
count=0
for i,n in Counter(nlst).most_common():
    if n>=2:
        count+=(n*(n-1))//2
print(count)

Submission status: Wrong Answer

Solution code:
import math
from collections import deque
def main():
    n,p = tuple([int(t)for t in input().split()])
 
    s = input()[::-1]
    subs = [0]*p
    counter =0
    for i in range(0,n):
        subs[int(s[0:i+1])%p] +=1
 
    counter+=subs[0]
 
    for i in range(p//2):
        counter+= subs[i]*subs[-i-1]
 
 
    counter+=subs[0]*(subs[0]-1)//2
 
    print(counter)
 
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n,p=map(int,input().split())
s=input()
R=[[0]*p for i in range(3)]
a=0
b=1
c=2
for i in range(n):
  x=int(s[i])
  for j in range(p):
    y=(j*10+x)%p
    R[a][y]=R[c][j]+R[c][y]-R[b][j]
  R[a][x%p]+=1
  a=b
  b=c
  c=(c+1)%3
print(R[c][0])

Submission status: Wrong Answer

Solution code:
n,p=map(int,input().split())
l=list(input())
for i in range(n):
    l[i]=int(l[i])
w=0
wl=[]
po=pow(10,p-2,p)
if p==2 or p==5:
    ans=0
    for i in range(n):
        if l[i]%p==0:
            ans+=i+1
    print(ans)
    exit()
for i in range(n):
    wl.append(w)
    #if w==0:
        #ans+=rr[n-1-i]
    w-=l[n-1-i]
    w*=po
    w%=p
wl.reverse()
r=[]
rt=0
for i in range(n):
    rt+=l[i]
    r.append(rt%p)
    rt*=10
    rt%=p
#r.reverse()
d=[0]*p
ans=0
for i in range(n):
    d[r[i]]+=1
    ans+=d[wl[i]]  
print(ans)

Submission status: Wrong Answer

Solution code:
# 入力が10**5とかになったときに100ms程度早い
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_map_as_int(H):
    '''
    #→1,.→0として読み込む
    '''
    ret = []
    for _ in range(H):
        ret.append([1 if s == '#' else 0 for s in read()[:-1]])
    return ret


N, P = read_ints()
S = read()[:-1]

# すべてを見ていくのは無理
# ある連続する文字列に対して、一つ数字が増えたときの判別はどうなるのか？ よくわからない
# 倍数を探したい...
# ある倍数について、それを構成する最小の部分列を保持することを考える
# その部分列を上位桁にずらしてもそれはPの倍数であることが保証されている。つまり、連続する区間の数をかけて行くのが正解？
# 0はvalidな文字列についたら万能 それ以外はちゃんと検証する


# 次の個数=今までの個数+自身までの区間の個数
tmp = ''  # 連続する区間
cnt = 0
ans = 0  # いままでの個数
pre_is_valid = 0  # 前が有効部分文字列だったか
pre_is_0 = 0
for s in S:
    tmp += s
    if pre_is_valid and s == '0':
        # 万能なので追加する
        cnt += 1
        ans += cnt
        pre_is_0 = 1

    else:
        if int(tmp) % P == 0:
            pre_is_valid = 1
            cnt += 1
            ans += cnt
            tmp = ''
        else:
            pre_is_valid = 0
        pre_is_0 = 0

print(ans)

# プログラムは正しく動いてる
# 見落としの通りが存在する

# 既知の見落とし
# 0が連続する場合→preが0のときは
# なぜか数字が足りない

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

As = [0]
A = 0
for S in Ss:
    S = int(S)
    A = (A*10 + S) % P
    As.append(A)

cnt = Counter()
ans = 0
for A in As:
    ans += cnt[A]
    cnt[A] += 1

print(ans)

Submission status: Wrong Answer

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


memo = {}
ans = 0
rot = 0
for i in range(n):
    rot = (rot * 10 + int(s[i])) % p
    if int(s[i]) % p == 0:
        ans += 1
    if rot in memo:
        ans += memo[rot]
    if (int(s[i]) - rot) % p not in memo:
        memo[(int(s[i]) - rot) % p] = 1
    else:
        memo[(int(s[i]) - rot) % p] += 1

print(ans)

Submission status: Wrong Answer

Solution code:
info = [int(i) for i in input().split()]
string = input()
count = 0
print(len(str(info[1])), info[0]+1)
for i in range(len(str(info[1])), info[0]+1):
    for j in range(0, info[0]-i+1):
        if int(string[j:j+i]) % info[1] == 0:
            count+=1
print(count+string.count('0'))

Submission status: Wrong Answer

Solution code:
n,p=map(int,input().split())
l=list(input())
for i in range(n):
    l[i]=int(l[i])
w=0
wl=[]
po=pow(10,p-2,p)
if p==2 or p==5:
    ans=0
    for i in range(n):
        if l[i]%p==0:
            ans+=i+1
    print(ans)
    exit()
for i in range(n):
    wl.append(w)
    #if w==0:
        #ans+=rr[n-1-i]
    w-=l[n-1-i]
    w*=po
    w%=p
wl.reverse()
r=[]
rt=0
for i in range(n):
    rt+=l[i]
    r.append(rt%p)
    rt*=10
#r.reverse()
d=[0]*p
ans=0
for i in range(n):
    d[r[i]]+=1
    ans+=d[wl[i]]  
print(ans)

Submission status: Wrong Answer

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

mod_matrix = [ [0]*n for i in range(n) ]
ans = 0

for i in range(n):
    v = int(s[i])
    mod_matrix[i][i] = v % p
    for j in range(i+1):
        print([j, i])
        mod = (mod_matrix[j][i-1]*10 + v) % p
        mod_matrix[j][i] = mod
        if mod == 0:
            ans += 1

print(ans)