Compter les Transformations (Corrigé)

Solution

Par le principe de comptage de base, pour un ensemble d'éléments ayant des choix de c_1,c_2,...,c_n, et chaque choix d'élément étant indépendant, le nombre total de choix est \displaystyle \prod_{i=1}^n c_i = c_1 \cdot c_2 \cdot c_3 ... \cdot c_n. La même chose peut être appliquée ici.

Pour chaque chiffre, soit $f(d)$ le nombre de choix possibles, calculez cela pour chaque 0 \le d \le 9 et ensuite la réponse sera :

def solve():
    n=int(input())
    x=input()
    choice=[1,4,4,2,4,1,2,1,4,1]
    ans=1
    for i in x:
        ans*=choice[int(i)]
        ans%=(999983)
    print(ans%(999983))
    
for _ in range(int(input())):
    solve()