h1. 'Soluţia':incalzire2020/solutii/teste problemei 'Teste':problema/teste

h1(#teste). 'Soluţia':incalzire2020/solutii/teste problemei 'Teste':problema/teste

h3. 20 de puncte $(O(n^k)+O(sqrt(S)))$

va arăta astfel:
Pozitie $|1 2.. poz ... n|$
Valoare $|? ?.. val ... ?|$

Observam ca numarul de siruri in care $val$ apare pe pozitia poz este numarul de moduri de a inlocui $n-1$ caractere $?$ cu numere de la $1$ pana la $k$. Acest numar este egal cu $k^(n-1)$. Daca fixam doar pozitia $poz$ si facem suma pentru toate numerele $val$ de la $1$ la $k$, vom obitne $k^(n-1)*k*(k+1)/2$. Deoarece expresia este aceeasi indiferent oricare din cele $n$ pozitii va fi $poz$, $S$ va fi n*(k^(n-1)*k*(k+1)/2).

Observam ca numarul de siruri in care $val$ apare pe pozitia poz este numarul de moduri de a inlocui $n-1$ caractere $?$ cu numere de la $1$ pana la $k$. Acest numar este egal cu $k^(n-1)$. Daca fixam doar pozitia $poz$ si facem suma pentru toate numerele $val$ de la $1$ la $k$, vom obitne $k^(n-1)*k*(k+1)/2$. Deoarece expresia este aceeasi indiferent oricare din cele $n$ pozitii va fi $poz$, $S$ va fi $n*(k^(n-1)*k*(k+1)/2)$.

Observăm ca în formula anterioara apar doar puteri ale lui $n$, $k$ şi $k+1$ (şi $2$, pe care trebuie să îl reducem de unde este posibil), deci putem precalcula factorii primi ai acestora, şi observând la ce puteri apar cele 3 numere în formula pentru $S$, putem obţine factorizarea lui $S$ "combinând" cele 3 factorizări. Răspunsul va fi produsul puterilor (la care se adauga $1$) la care apar factorii primi ai lui $S$ în factorizarea lui.