Problem:


Score : 400 points

Problem Statement

Given is a string S. Each character in S is either a digit (0, ..., 9) or ?.

Among the integers obtained by replacing each occurrence of ? with a digit, how many have a remainder of 5 when divided by 13? An integer may begin with 0.

Since the answer can be enormous, print the count modulo 10^9+7.

Constraints

S is a string consisting of digits (0, ..., 9) and ?.

1 \leq |S| \leq 10^5

Input

Input is given from Standard Input in the following format:

S

Output

Print the number of integers satisfying the condition, modulo 10^9+7.

Sample Input 1

??2??5

Sample Output 1

768

For example, 482305, 002865, and 972665 satisfy the condition.

Sample Input 2

?44

Sample Output 2

1

Only 044 satisfies the condition.

Sample Input 3

7?4

Sample Output 3

0

We may not be able to produce an integer satisfying the condition.

Sample Input 4

?6?42???8??2??06243????9??3???7258??5??7???????774????4?1??17???9?5?70???76???

Sample Output 4

153716888



Sample input:
??2??5


Sample output:
768

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9+7
S = input()
N = len(S)
dp = [[0]*13 for _ in range(N+1)]
dp[0][0] = 1
S = S[::-1]
for i in range(N):
    if S[i] != '?':
        m = int(S[i])
        rm = (m*10**i)%13
        for r in range(13):
            dp[i+1][(r+rm)%13] = dp[i][r]
            dp[i+1][(r+rm)%13] %= mod
    else:
        for m in range(10):
            rm = (m*10**i)%13
            for r in range(13):
                dp[i+1][(r+rm)%13] += dp[i][r]
                dp[i+1][(r+rm)%13] %= mod

print(dp[N][5])

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9 + 7
s = input()

old_dp = [0] * 13
new_dp = [0] * 13
old_dp[0] = 1

for c in s:
    for i in range(13):
        if c == '?':
            for d in range(10):
                new_dp[(i*10 + d) % 13] += old_dp[i]
        else:
            new_dp[(i*10+int(c)) % 13] += old_dp[i]
    old_dp = [x % MOD for x in new_dp]
    new_dp = [0] * 13
    
print(old_dp[5])

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9 + 7

Ss = input()

N = len(Ss)

dp = [[0]*(13) for _ in range(N+1)]
dp[0][0] = 1
for d, Sd in enumerate(Ss):
#    print(d, Sd)
    for mod13 in range(13):
        if Sd != '?':
            x = int(Sd)
            mod13n = (10*mod13 + x) % 13
            dp[d+1][mod13n] += dp[d][mod13]
            dp[d+1][mod13n] %= MOD
        else:
            for x in range(10):
                mod13n = (10*mod13 + x) % 13
                dp[d+1][mod13n] += dp[d][mod13]
                dp[d+1][mod13n] %= MOD

print(dp[-1][5])

Submission status: Time Limit Exceeded

Solution code:
import sys


fin = sys.stdin.readline
MOD = 10 ** 9 + 7
S = fin().rstrip("\n")[::-1]
dp = [[0] * 13 for _ in range(len(S) + 1)]
dp[0][0] = 1
for i, c in enumerate(S, start=1):
    base = 10 ** (i - 1)
    if c != '?':
        d = int(c) * base % 13
        for r in range(13):
            dp[i][(d + r) % 13] += dp[i - 1][r]
            dp[i][(d + r) % 13] %= MOD
    else:
        for d in range(10):
            d = d * base % 13
            for r in range(13):
                dp[i][(d + r) % 13] += dp[i - 1][r]
                dp[i][(d + r) % 13] %= MOD
print(dp[-1][5])

Submission status: Time Limit Exceeded

Solution code:
s = input()
MOD = 10**9 + 7
memo = [0]*13
memo[0] = 1

c = 1
for d in reversed(s):
    if d == '?':
        nmemo = [0]*13
        for i in range(10):
            r = (i*c)%13
            for j in range(13):
                nmemo[(j+r)%13] += memo[j]
        for i in range(13):
            nmemo[i] %= MOD
        memo = nmemo
    else:
        d = (-int(d)*c)%13
        memo = memo[d:] + memo[:d]

    c *= 10
    c %= 13
print(memo[5])

Submission status: Time Limit Exceeded

Solution code:
mod=1000000007
s=input()
l=len(s)
DP=[[0]*13 for _ in range(l+1)]
DP[0][0]=1
for i in range(1,l+1):
    d=s[-i]
    tmp=(10**(i-1))%13
    if d=='?':
        for j in range(10):
            for k in range(13):
                DP[i][(k+tmp*j)%13]+=DP[i-1][k]
                DP[i][(k+tmp*j)%13]%=mod
    else:
        d=int(d)
        for k in range(13):
            DP[i][(k+tmp*d)%13]+=DP[i-1][k]
            DP[i][(k+tmp*d)%13]%=mod
print(DP[-1][5])

Submission status: Time Limit Exceeded

Solution code:
def inpl(): return list(map(int, input().split()))

MOD = 10**9 + 7
S = input()[::-1]
x = 1

DP = [0]*13
DP[0] = 1
for i in range(len(S)):
    DP2 = [0]*13
    if S[i] != "?":
        s = int(S[i])
        for i in range(13):
            DP2[(i + s*x)%13] = DP[i]%MOD
    else:
        for j in range(10):
            for i in range(13):
                DP2[(i + j*x)%13] = (DP2[(i + j*x)%13] + DP[i])%MOD
    x *= 10
    DP = DP2

print(DP[5]%MOD)

Submission status: Time Limit Exceeded

Solution code:
X = input()
MOD = 10**9 + 7
M = 13
S = [0]*M
S[0] = 1
T = [0]*M

def calc(S, T, x):
    for i in range(M):
        T[(i*10 + x) % M] += S[i]
    for i in range(M):
        T[i] %= MOD

zeros = [0]*M
for c in X:
    T[:] = zeros
    if c == "?":
        for x in range(10):
            calc(S, T, x)
    else:
        x = int(c)
        calc(S, T, x)
    S, T = T, S
print(S[5])

Submission status: Time Limit Exceeded

Solution code:
from sys import setrecursionlimit as lim

lim(100010)

MOD = 1000000007

s = raw_input().strip()
n = len(s)

dp = [[-1 for i in xrange(13)] for j in xrange(n)]

def solve(idx, rem):
    global n

    if idx >= n:
        if rem != 0:
            return 0
        return 1

    if dp[idx][rem] != -1: return dp[idx][rem]

    if s[idx] != '?':
        r = int(s[idx])
        x = pow(10, n - 1 - idx, 13)
        res = (rem - x * r) % 13
        
        dp[idx][rem] = solve(idx + 1, res)
        return dp[idx][rem]

    ans = 0
    for r in xrange(10):
        x = pow(10, n - 1 - idx, 13)
        res = (rem - x * r) % 13
        ans += solve(idx + 1, res)
        if (ans >= MOD): ans -= MOD

    dp[idx][rem] = ans
    return ans

print solve(0, 5) % MOD

Submission status: Accepted

Solution code:
s = input()

mod = 10 ** 9 + 7

dp = [[0] * 13 for _ in range(len(s))]

if s[0] == '?':
    dp[0] = [1] * 10 + [0] * 3
else:
    dp[0][int(s[0])] = 1

for i in range(len(s)-1):
    if s[i+1] == '?':
        for j in range(13):
            for k in range(10):
                dp[i+1][(j*10+k)%13] = (dp[i+1][(j*10+k)%13] + dp[i][j]) % mod
    else:
        n = int(s[i+1])
        for j in range(13):
            dp[i+1][(j*10+n)%13] = (dp[i+1][(j*10+n)%13] + dp[i][j]) % mod

print(dp[len(s)-1][5])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# D - Digits Parade
import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
MOD = 10**9+7
S = readline().decode().rstrip()
N = len(S)

dp = [0]*13
dp[0] = 1
# if S[0] == '?':
#     rem = pow(10,N,13)
#     for j in range(10):
#         t = rem*j%13
#         dp[t] += 1
# else:
#     s = int(S[0])
#     rem = pow(10,N,13)*s%13
#     dp[rem] += 1

for i in range(N):
    s = S[i]
    ndp = [0]*13
    rem = pow(10,N-i-1,13)
    if s == '?':
        for j in range(10):
            t = rem*j%13
            for k in range(13):
                ndp[(k+t)%13] += dp[k]
                ndp[(k+t)%13] %= MOD
    else:
        s = int(s)
        t = rem*s%13
        for k in range(13):
            ndp[(k+t)%13] += dp[k]
            ndp[(k+t)%13] %= MOD
    dp = ndp
print(dp[5]%MOD)

Submission status: Accepted

Solution code:
S = ''.join(list(reversed(input())))
N = len(S)
p = 13
mod = 10**9 + 7

dp = [[0]*p for _ in range(N)]

if S[0] == '?':
    for j in range(10):
        dp[0][j] = 1
else:
    dp[0][int(S[0])] = 1

b = 10
for i in range(N - 1):
    r = []
    if S[i + 1] == '?':
        for j in range(10):
            r.append(b * j % p)
    else:
        r.append(b * int(S[i + 1]) % p)

    for j in range(len(r)):
        for k in range(p):
            if dp[i][k] > 0:
                dp[i + 1][(k + r[j]) % p] += dp[i][k]
                dp[i + 1][(k + r[j]) % p] %= mod

    b *= 10
    b %= p

print(dp[N - 1][5] % mod)

Submission status: Accepted

Solution code:
S = input()
N = len(S)
MOD = 10**9 + 7
dp = [[0]*(N+1) for _ in range(13)]
#dp[j][i]: 上からiケタ目までみたときの13で割った余りがjである個数
dp[0][0] = 1

for i in range(0, N):
    if S[i] == "?":
        for j in range(0, 10):
            for k in range(0, 13):
                dp[(k*10+j)%13][i+1] += dp[k][i]
    else:
        j = int(S[i])
        for k in range(0, 13):
            dp[(k*10+j)%13][i+1] += dp[k][i]
    
    for k in range(0, 13):
        dp[k][i+1] %= MOD

print(dp[5][N]%MOD)

Submission status: Accepted

Solution code:
def f(i,k):
  for j in range(13):
    dp[i+1][(k*mul+j)%13]+=dp[i][j]
    dp[i+1][(k*mul+j)%13]%=mod
  
mod=10**9+7
s=input()[::-1]
n=len(s)
dp=[[0]*13 for i in range(10**5+1)]
dp[0][0]=mul=1

for i in range(n):
  if s[i]=='?':
    for k in range(10):
      f(i,k)
  else:
    f(i,int(s[i]))
  mul*=10
  mul%=13
  
print(dp[n][5]%mod)

Submission status: Accepted

Solution code:
def getval():
    s = input()
    return s

def main(s):
    mod = 10**9 + 7
    #Remainders of 10**i%13
    rem = [1]
    for i in range(11):
        rem.append((rem[-1]*10)%13)
    #Digits of ?
    arr = []
    #Sum of existing integers mod 13
    init = 0
    for i in range(len(s)):
        if s[i]=="?":
            arr.append(len(s)-i-1)
        else:
            init += (int(s[i]) * rem[(len(s)-i-1)%12])%13
            init %= 13

    #DP for number of comb such that rem is j on ith ?
    dp = [[0 for i in range(13)]]
    dp[0][0] = 1
    for i in arr:
        temp = [0 for i in range(13)]
        prev = dp[-1]
        for j in range(13):
            for k in range(10):
                update = prev[j]
                temp[(j+k*rem[i%12])%13] += update
                temp[(j+k*rem[i%12])%13] %= mod
        dp.append(temp)

    print(dp[-1][(18-init)%13])
    
                
if __name__=="__main__":
    s = getval()
    main(s)

Submission status: Accepted

Solution code:
S = input()
N = len(S)
MOD = 10**9 + 7

dp = [[0] * 13 for i in range(N+1)]
dp[0][0] = 1
for i in range(N):
    for j in range(13):
        for k in range(10):
            if S[i] == str(k) or S[i] == '?':
                dp[i+1][(j*10+k) % 13] += dp[i][j]
                dp[i+1][(j*10+k) % 13] %= MOD
#print(dp)
print(dp[N][5])

Submission status: Accepted

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  s=list(S())[::-1]
  n=len(s)
  dp=[[0]*13 for _ in range(n+1)]

  dp[0][0]=1
  mul=1
  for i in range(n):
    for j in range(13):
      if s[i]=='?':
        for k in range(10):
          dp[i+1][(j+k*mul)%13]+=dp[i][j]
          dp[i+1][(j+k*mul)%13]%=mod
      else:
        dp[i+1][(j+int(s[i])*mul)%13]+=dp[i][j]
        dp[i+1][(j+int(s[i])*mul)%13]%=mod
    mul*=10
    mul%=13

  return dp[n][5]%mod

# main()
print(main())

Submission status: Accepted

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

S = readline().rstrip()
N = len(S)
DIV = 10 ** 9 + 7

dp = [[0] * 13 for i in range(N)]

x0 = S[0]
if x0 == "?":
  for i in range(10):
    dp[0][i] = 1
else:
  dp[0][int(x0)] = 1
  
for i in range(1, N):
  x = S[i]
  if x == "?":
    for j in range(13):
      for k in range(10):
        dp[i][(j * 10 + k) % 13] += dp[i - 1][j]
        dp[i][(j * 10 + k) % 13] %= DIV
  else:
    for j in range(13):
      dp[i][(j * 10 + int(x)) % 13] += dp[i - 1][j]
      dp[i][(j * 10 + int(x)) % 13] %= DIV

print(dp[-1][5])

Submission status: Accepted

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

S = readline().rstrip()
N = len(S)
DIV = 10 ** 9 + 7

dp = [[0] * 13 for i in range(N)]

x0 = S[0]
if x0 == "?":
  for i in range(10):
    dp[0][i] = 1
else:
  dp[0][int(x0)] = 1
  
for i in range(1, N):
  x = S[i]
  if x == "?":
    for j in range(13):
      for k in range(10):
        ind = (j * 10 + k) % 13
        dp[i][ind] += dp[i - 1][j]
        dp[i][ind] %= DIV
  else:
    for j in range(13):
      ind = (j * 10 + int(x)) % 13
      dp[i][ind] += dp[i - 1][j]
      dp[i][ind] %= DIV

print(dp[-1][5])

Submission status: Accepted

Solution code:
S=input()
S=S[::-1]
dp=[[0]*13 for _ in [0]*(len(S)+1)]
dp[0][0]=1
#dp[n%2][m]:=下位n桁を決定したとき13でわった余りがmになるようなものの数
def pow_k(x,n,p=10**9+7):
    if n==0:
        return 1
    K=1
    while n>1:
        if n%2!=0:
            K=(K*x)%p
        x=(x*x)%p
        n//=2
    return (K*x)%p

p=10**9+7
for n in range(len(S)):
    x=pow_k(10,n,13)
    if S[n]=='?':
        for i in range(10):
            for m in range(13):
                dp[(n+1)][(m+i*x)%13]=(dp[(n+1)][(m+i*x)%13]+dp[n][m])%p
    else:
        s=int(S[n])
        for m in range(13):
            dp[(n+1)][(m+s*x)%13]=dp[n][m]%p

print(dp[len(S)][5]%p)

Submission status: Accepted

Solution code:
import math
from math import gcd,pi,sqrt
INF = float("inf")
MOD = 10**9 + 7

import sys
sys.setrecursionlimit(10**6)
import itertools
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]

def main():
    s = input()
    n = len(s)
    dp = [[0]*13 for i in range(n+1)]
    dp[0][0] = 1

    for i,s in enumerate(s[::-1],start = 1):
        p10 = pow(10,i-1,13)
        if s!= "?":
            for k in range(13):
                dp[i][(int(s)*p10 + k)%13] += dp[i-1][k]
                dp[i][(int(s)*p10 + k)%13] %= MOD
        else:
            for j in range(10):
                for k in range(13):
                    dp[i][(j*p10 + k)%13] += dp[i-1][k]
                    dp[i][(j*p10 + k)%13] %= MOD
    print(dp[n][5] % MOD)


if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np
from numba import njit, i8

S = input()
MOD = 10 ** 9 + 7

dp = np.zeros(13, dtype=int)
dp[0] = 1


@njit(cache=True)
def q_mark(dp):
    new_dp = np.zeros(13, dtype=i8)
    for i in range(13):
        new_dp[np.arange(i, i + 10) % 13] += dp[i]
        new_dp %= MOD
    return new_dp


for s in S:
    # 4 == pow(10, -1, 13)
    dp = dp[np.arange(0, 52, 4) % 13]
    if s == '?':
        dp = q_mark(dp)
    else:
        dp = np.roll(dp, int(s))
print(dp[5])

Submission status: Accepted

Solution code:
def main():
    S = list(input())
    N = len(S)
    MOD = 10 ** 9 + 7
    dp = [[0] * 13 for _ in range(N + 5)]
    dp[0][0] = 1
    for i in range(N):
        for j in range(13):
            if S[i] != '?':
                dp[i+1][(10 * j + int(S[i])) % 13] += dp[i][j]
                dp[i+1][(10 * j + int(S[i])) % 13] %= MOD
            else:
                for k in range(10):
                    dp[i+1][(10 * j + k) % 13] += dp[i][j]
                    dp[i+1][(10 * j + k) % 13] %= MOD
    print(dp[N][5])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
S = input()[::-1]
P = 13
qs = [0]*13
tmp = 1
rest = 0
for i, s in enumerate(S):
    if s == '?':
        qs[tmp] += 1
    else:
        rest = (rest + int(s) * tmp) % P
    tmp = (tmp * 10) % P

dp = [0] * 13
dp[rest] = 1
for i, cnt in enumerate(qs):
    for _ in range(cnt):
        dp_new = [0]*13
        for j in range(10):
            tmp = (i * j) % P
            for k in range(P):
                dp_new[(k + tmp) % P] = (dp_new[(k + tmp) % P] + dp[k])%int(1e9+7)
        dp = dp_new
print(dp[5]%int(1e9+7))

Submission status: Accepted

Solution code:
S = input()
dp = 13*[0]
dp[0] = 1
mod = 10**9+7

for s in S:
  if s=="?":
    dp = [sum(dp[4*(j-i)%13] for i in range(10))%mod for j in range(13)]
  else:
    dp = [dp[4*(j-int(s))%13] for j in range(13)]
    
print(dp[5])

Submission status: Accepted

Solution code:
S = list(input())
N = len(S)
dp=[]
MOD = (10 ** 9) + 7
f = S.pop(0)
if f == '?':
  dp_low = [1,1,1,1,1,1,1,1,1,1,0,0,0]
else:
  dp_low = [0] * 13
  dp_low[int(f)] = 1
  
dp.append(dp_low)
for i in range(N-1):
  dp_low = [0] * 13
  if S[i] == '?':
    for j, val in enumerate(dp[i]):
      for k in range(10):
        temp = ((j * 10) + k) % 13
        dp_low[temp] += val
  else:
    for j, val in enumerate(dp[i]):
      temp = ((j * 10) + int(S[i])) % 13
      dp_low[temp] += val
  for i in range(13):
    dp_low[i] %= MOD
  dp.append(dp_low)
print(dp[-1][5])

Submission status: Accepted

Solution code:
S = input()
N = len(S)
mod = 10**9 + 7

p = 1

dp = [[0]*13 for _ in range(N+1)]
dp[0][0] = 1

for i in range(1,N+1):
  if S[-i] == '?':
    for k in range(10):
      a = (k * p) % 13
      for j in range(13):
        dp[i][j] += dp[i-1][j-a] % mod
        dp[i][j] %= mod
  else:
    a = (int(S[-i]) * p) % 13
    for j in range(13):
      dp[i][j] += dp[i-1][j-a] % mod
  p = (p * 10) % 13

print(dp[N][5])

Submission status: Accepted

Solution code:
from collections import defaultdict
s = input()
s = s[::-1]

app = [0 for _ in range(13)]

for i in range(len(s)):
    tmp_dic = [0 for _ in range(13)]
    if i == 0:
        if s[i] != '?':
            tmp_dic[int(s[i])]+= 1
        else:
            for j in range(10):
                tmp_dic[j] += 1

    else:
        if s[i] != '?':
            tmp = int(s[i]) * pow(10, i, 13)
            for j in range(13):
                tmp_dic[(tmp+j)%13] += app[j] % (10**9+7)

        else:
            for j in range(10):
                tmp = int(j) * pow(10, i, 13)
                for k in range(13):
                    tmp_dic[(tmp+k)%13] += app[k] % (10**9+7)

    app = tmp_dic
    # print(app)

print(app[5] % (10**9+7))

Submission status: Accepted

Solution code:

import sys

s=input()

n=[0]*6
q=[0]*6
j=[1,10,9,12,3,4,1]
lens=len(s)
for i in range(lens):
    i6=i%6
    if s[lens-1-i]=="?":
        q[i6]+=1
    else:
        n[i6]+=int(s[lens-1-i])

mod=10**9+7
    
nsum=0
for i in range(6):
    nsum+=(n[i]*j[i])%13
nsum=(5-nsum)%13

if q==[0]*6:
    if nsum==0:
        print(1)
    else:
        print(0)
    sys.exit()
        
cc2=[[-1]*13 for i in range(6)]

for i6 in range(6):
    for i in range(10):
        iii=(i*10**i6)%13
        cc2[i6][i]=iii

#dp=[[0]*13 for i in range(80)]
dpm=[0]*13
dpn=[0]*13
icnt=-1
for i6 in range(6):
    for i in range(q[i6]):
        dpn=[0]*13
        icnt+=1
        if icnt==0:
            for j in range(10):
                jj=(j*10**i6)%13
#                dp[icnt][jj]=1            
#                dpn[jj]=1
                dpm[jj]=1
            continue
        for mi in range(13):
            for j in range(10):
#                ccir=(mi-(j*(10**i6))%13)%13
                ccir=(mi-cc2[i6][j])%13
#                dp[icnt][mi]=(dp[icnt][mi]+dp[icnt-1][ccir])%mod
                dpn[mi]=(dpn[mi]+dpm[ccir])%mod
        dpm=dpn.copy()  
#    print(icnt,dp[icnt])

#print(dp[icnt][nsum]%mod)
print(dpm[nsum]%mod)

Submission status: Accepted

Solution code:
"""
dp[i][j] => 下からi桁目まで見る。あまりがjになるような数。
"""
mod = 10**9 +7
S = input()
S = S[::-1]
N = len(S)
dp = [[0]*13 for _ in range(N+1)]
dp[0][0] = 1
by = 1
for i in range(N):
    s = S[i]
    for j in range(13):
        if s == "?":
            for k in range(10):
                rest = k*by%13
                dp[i+1][(j+rest)%13] += dp[i][j]
                dp[i+1][(j+rest)%13] %= mod
        else:
            rest = int(s)*by%13
            dp[i+1][(j+rest)%13] += dp[i][j]
            dp[i+1][(j+rest)%13] %= mod
    by = by*10%13
print(dp[-1][5])

Submission status: Accepted

Solution code:
# @oj: atcoder
# @id: hitwanyang
# @email: 296866643@qq.com
# @date: 2020-05-19 17:18
# @url:https://atcoder.jp/contests/abc135/tasks/abc135_d
import sys,os
from io import BytesIO, IOBase
import collections,itertools,bisect,heapq,math,string
# region fastio

BUFSIZE = 8192

BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
# ------------------------------
def main():
    # python取模注意每次都需要取模，否则可能会导致tle
    # 大数取模的运算通常可以分解为每个位置的权重进行取模运算，然后求和再取模的，例如：
    # 1993%mod=(1000%mod+900%mod+90%mod+3%mod)%mod
    # 利用模运算的基本性质：
    # 加法：19%3=(10%3+9%3)%3 (a+b)%mod=(a%mod+b%mod)%mod
    # 乘法：27%4=(9%4*3%4)%4  (a*b)%mod=(a%mod*b%mod)%mod
    s=str(input())
    S=s[::-1]
    dp=[[0]*13 for i in range(len(S))]
    mod=10**9+7
    p=1 # 每位的权重10的幂次
    for i in range(len(S)):
        if i==0:
            if S[i]!='?':
                t=p*int(S[i])%13
                dp[i][t]+=1
            else:
                for j in range(10):
                    dp[i][j]+=1
        else:
            if S[i]!='?':
                t=p*int(S[i])%13
                for j in range(13):
                    dp[i][(t+j)%13]=dp[i-1][j]%mod
            else:
                for j in range(10):
                    for k in range(13):
                        temp=(p*j%13+k)%13
                        dp[i][temp]=(dp[i][temp]+dp[i-1][k])%mod
        # 权重取模
        p=(p%13*10%13)%13
    # print (dp)
    print (dp[len(S)-1][5])
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# @oj: atcoder
# @id: hitwanyang
# @email: 296866643@qq.com
# @date: 2020-05-19 17:18
# @url:https://atcoder.jp/contests/abc135/tasks/abc135_d
import sys,os
from io import BytesIO, IOBase
import collections,itertools,bisect,heapq,math,string
# region fastio

BUFSIZE = 8192

BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
# ------------------------------
def main():
    # python取模注意每次都需要取模，否则会导致tle
    s=str(input())
    S=s[::-1]
    dp=[[0]*13 for i in range(len(S))]
    mod=10**9+7
    p=1 # 每位的权重10的幂次
    for i in range(len(S)):
        if i==0:
            if S[i]!='?':
                t=p*int(S[i])%13
                dp[i][t]+=1
            else:
                for j in range(10):
                    dp[i][j]+=1
        else:
            if S[i]!='?':
                t=p*int(S[i])%13
                for j in range(13):
                    dp[i][(t+j)%13]=dp[i-1][j]%mod
            else:
                for j in range(10):
                    for k in range(13):
                        temp=(p*j%13+k)%13
                        dp[i][temp]=(dp[i][temp]+dp[i-1][k])%mod
        p=(p%13*10%13)%13
    # print (dp)
    print (dp[len(S)-1][5])
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# @oj: atcoder
# @id: hitwanyang
# @email: 296866643@qq.com
# @date: 2020-05-19 17:18
# @url:https://atcoder.jp/contests/abc135/tasks/abc135_d
import sys,os
from io import BytesIO, IOBase
import collections,itertools,bisect,heapq,math,string
# region fastio

BUFSIZE = 8192

BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
# ------------------------------
def main():
    s=str(input())
    S=s[::-1]
    dp=[[0]*13 for i in range(len(S))]
    mod=10**9+7
    p=1 # 每位的权重10的幂次
    for i in range(len(S)):
        if i==0:
            if S[i]!='?':
                t=p*int(S[i])%13
                dp[i][t]+=1
            else:
                for j in range(10):
                    dp[i][j]+=1
        else:
            if S[i]!='?':
                t=p*int(S[i])%13
                for j in range(13):
                    temp=(t+j)%13
                    dp[i][temp]=dp[i-1][j]%mod
            else:
                for j in range(10):
                    # t=p*j%13
                    for k in range(13):
                        temp=(p*j%13+k)%13
                        dp[i][temp]=(dp[i][temp]+dp[i-1][k])%mod
        p=(p%13*10%13)%13
    # print (dp)
    print (dp[len(S)-1][5])
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    S = input()
    N = len(S)
    base = 1
    remainders = [0]*13
    remainders[0] = 1
    number = 0
    modulo = 10**9+7
    for i in range(N-1, -1, -1):
        new_remainders = [0]*13
        if S[i] == '?':
            for digit in range(10):
                for r in range(len(remainders)):
                    new_remainders[(base*digit+r)%13] += remainders[r]
        else:
            digit = int(S[i])
            for r in range(13):
                new_remainders[(base*digit+r)%13] = remainders[r]
        base = (base*10)%13
        remainders = [r%modulo for r in new_remainders]
    return remainders[5]


if __name__ == '__main__':
    print(solve())

Submission status: Accepted

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
# INF =  float("inf")
INF = 10**18
import bisect
import statistics
mod = 10**9+7
# mod = 998244353

S = input()

dp = [[0 for j in range(13)] for i in range(len(S)+1)]
dp[0][0] = 1
for i in range(len(S)):
    if S[i] != "?":
        k = int(S[i])
        for j in range(13):
            dp[i+1][(j*10+k)%13] = (dp[i+1][(j*10+k)%13] + dp[i][j])% mod
    else:
        for k in range(10):
            for j in range(13):
                dp[i + 1][(j * 10 + k) % 13] = (dp[i + 1][(j * 10 + k) % 13] + dp[i][j]) % mod

print(dp[len(S)][5] % mod)

Submission status: Accepted

Solution code:
MOD = 10**9+7
S = input()
dp = [[0]*13 for i in range(len(S))]


if S[0]=='?':
    for i in range(10):
        dp[0][i] = 1
else:
    dp[0][int(S[0])] = 1

for i,c in enumerate(S[1:]):
    for j in range(13):
        if c=='?':
            for k in range(10):
                nj = (j*10 + k) % 13
                dp[i+1][nj] += dp[i][j]
                dp[i+1][nj] %= MOD
        else:
            nj = (j*10 + int(c)) % 13
            dp[i+1][nj] += dp[i][j]
            dp[i+1][nj] %= MOD

print(dp[-1][5])

Submission status: Accepted

Solution code:
MOD=10**9+7

S=input()
old=[0]*13
old[0]=1
n=1
for c in S:
  dp=[0]*13
  if c=='?':
    for j in range(10):
      for i in range(13):
        dp[(i*10+j)%13]+=old[i]
        dp[(i*10+j)%13]%=MOD
  else:
    c=int(c)
    for i in range(13):
      dp[(i*10+c)%13]+=old[i]
      dp[(i*10+c)%13]%=MOD
  old=[i for i in dp]
print(dp[5])