mod=10**9+7
s=input()[::-1]
l=len(s)
dp=[[0]*13 for i in range(l+1)]
dp[0][0]=1
#Pré-calcul car la puissance est trop importante
p=[0]*l
p[0]=1
for i in range(l-1):
    p[i+1]=(p[i]*10)%13
for i in range(l):
    s_sub=s[i]
    if s_sub=="?":
        for j in range(13):
            for k in range(10):
                dp[i+1][(j+k*p[i])%13]+=dp[i][j]
                dp[i+1][(j+k*p[i])%13]%=mod
    else:
        k=int(s_sub)
        for j in range(13):
            dp[i+1][(j+k*p[i])%13]+=dp[i][j]
            dp[i+1][(j+k*p[i])%13]%=mod
print(dp[l][5])

ABC133-E Virus Tree 2

Temps pris

Cela prend presque une heure mais WA

Cause d'erreur

Je ne pouvais pas du tout déboguer parce que je l'ai implémenté différemment de ma propre considération. ** Je n'avais pas assez de pouvoir pour croire en mes pensées **, non? Je ne suis pas très doué pour déboguer de tels modèles, mais est-ce une expérience ...? ??

Considération

Premièrement, puisqu'il s'agit d'un arbre, on peut dire que ** côtés sont N-1 côtés, tous les sommets sont connectés et il n'y a pas de chemin fermé **. De plus, la distance entre deux sommets différents (le nombre minimum de côtés requis pour le tracé) est de 2 ou moins (1 ou 2).

Ici, ** tout arbre peut être considéré comme un arbre enraciné **, j'ai donc décidé de considérer un arbre dont la racine est le sommet 1. De plus, ** il est préférable de peindre une couleur à la fois pour que les voisins soient peints différemment **, donc pour le moment, j'ai peint du sommet le plus proche de la racine. (Si c'était impossible, j'avais l'intention de l'appliquer à partir des feuilles à l'envers.)

Ici, afin de confirmer comment peindre, j'ai décidé de considérer un arbre avec 8 sommets et 7 côtés comme le montre la figure ci-dessous. De plus, dans la figure ci-dessous, quel sommet ne doit pas être différent lorsque la peinture par le haut est indiquée en rouge.

La verbalisation de la façon de peindre les couleurs dans la figure ci-dessus est la suivante.

Premièrement, il existe des façons $ K $ de peindre les racines. Comme la couleur des sommets autres que la racine est différente de la couleur des sommets dont la distance est 1 ou 2, ** parent **, ** parent parent **, ** frère (sommets avec le même parent) * Différent de *. Ici, puisque le parent du parent n'existe pas au sommet de la profondeur 1, ** Comment peindre la couleur du frère ** peut être sélectionné parmi $ K-1 $ couleurs de rue autres que le parent $ \ _ {K-1} P \ _ {nombre total de frères et sœurs} $. De plus, comme il y a toujours un parent du parent au sommet de la profondeur 2, choisissez parmi $ K-2 $ des couleurs de rue autres que le parent et le parent du parent $ \ _ {K-2} P \ _ {frère Le nombre total de} $ sera.

Ici, quand j'ai enregistré comment peindre la couleur de mon frère, je l'ai enregistrée une fois dans le tableau, mais ** j'enregistrais la mauvaise valeur **. Ce serait très décevant si je pouvais faire le cas de test avec précision par moi-même ainsi que l'échantillon.

<détails>

from sys import setrecursionlimit
setrecursionlimit(10**6)
n,k=map(int,input().split())
paths=[[] for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    paths[a-1].append(b-1)
    paths[b-1].append(a-1)
inf=100000000000000
nums=[-inf]*n
nums[0]=k
from collections import deque
now=deque()
now.append(0)
def bfs(d):
    global n,k,paths,nums,now
    l=len(now)
    if d==1:
        for i in range(l):
            p=now.popleft()
            ln=len(paths[p])
            next_num=k-1
            for j in range(ln):
                if nums[paths[p][j]]==-inf:
                    nums[paths[p][j]]=next_num
                    now.append(paths[p][j])
                    next_num-=1
    else:
        for i in range(l):
            p=now.popleft()
            ln=len(paths[p])
            next_num=k-2
            for j in range(ln):
                if nums[paths[p][j]]==-inf:
                    nums[paths[p][j]]=next_num
                    now.append(paths[p][j])
                    next_num-=1
    if len(now):bfs(d+1)
bfs(1)
ans=1
for i in range(n):
    if nums[i]<=0:
        print(0)
        exit()
    ans*=nums[i]
    ans%=(10**9+7)
print(ans)