3821 - Magic Digits

Cerința

Le Quack , mare fan al Lord Of The Rings , dar și al vrăjitoriei , află de la Gandalf că cifrele magice sunt { 1,2,3,4,5,6,7,8,9 } , cifra 0 este prea asemănătoare cu ochiul lui Sauron , fiind astfel considerată malefica. Le Quack iubeste aceste cifre magice încât le-a studiat mai atent și a observat că acestea pot forma numere de diferite lungimi ( ex : 1124 , 312 , 91235 ). Pentru fiecare număr format cu cifre magice definim gradul de frumusete ca fiind suma dintre frecvența minima a unei cifre magice și frecvența maxima a unei cifre magice care se găsește în număr. Formal , dacă construim un vector f , unde f[i] este numărul de apariții ale cifrei i și se șterg toate valorile pentru care f[i] = 0 , atunci min(f) + max(f) = k , unde k este gradul de frumusețe al numărului. De exemplu , pentru numărul 131 gradul de frumusețe este 1+2 = 3. Le Quack își pune următoarea întrebare : Câte numere de n cifre au gradul de frumusețe egal cu k ?

Date de intrare

Programul citește de la tastatură pe prima linie un număr N reprezentând lungimea numerelor care trebuie numărate și k , gradul de frumusețe al lor.

Date de ieșire

Programul va afișa pe ecran numărul cerut modulo 666013.

Restricții și precizări

N <= 300. K <= 2*N. Pentru 10 puncte N <= 6. Pentru alte 10 puncte , K > N. Pentru restul de 80 de puncte , K <= N , N > 6 si N <= 300. Nu uitați că cifra 0 nu poate fi folosită ! ==Exemplu==: Intrare

2 2 Ieșire

72 Intrare

3 2 Ieșire

504

Explicație

În primul exemplu , sunt 72 de numere de lungime 2 cu gradul de frumusețe 2. câteva dintre acestea sunt : 13 , 14 , 32. În al doilea exemplu sunt 504 numere de lungime 3 cu gradul de frumusețe 2. Câteva dintre acestea sunt : 132 , 152 , 512.

Rezolvare

MOD = 666013

def numere_grad_frumusete(N, k):

   # Funcție auxiliară pentru calculul coeficientului binomial
   def comb(n, r):
       result = 1
       for i in range(r):
           result = (result * (n - i)) % MOD
           result = (result * pow(i + 1, MOD - 2, MOD)) % MOD
       return result

   # Funcție recursivă pentru generarea numărului de aranjamente
   def count_arrangements(digit_counts, current_k):
       if current_k < 0:
           return 0
       if current_k == 0:
           # Calculăm numărul de moduri în care putem aranja cifrele
           result = 1
           for count in digit_counts:
               result = (result * comb(N, count)) % MOD
           return result

       total_arrangements = 0
       for i in range(1, 10):
           # Adăugăm cifra i și continuăm recursiv
           new_digit_counts = digit_counts[:]
           new_digit_counts.append(i)
           total_arrangements = (total_arrangements + count_arrangements(new_digit_counts, current_k - 1)) % MOD

       return total_arrangements

   return count_arrangements([], k)

if __name__ == "__main__":

   # Citim datele de intrare
   N, k = map(int, input().split())

   # Calculăm rezultatul și afișăm rezultatul modulo MOD
   rezultat = numere_grad_frumusete(N, k)
   print(rezultat)

python grad_frumusete.py