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

Submission attempts (in order):
from 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)

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)

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)

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)

    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)

Verdicts: Wrong Answer

Wrong Answer

Wrong Answer

Accepted