== include(page="template/taskheader" task_id="div") ==
Poveste și cerință...
Se consideră numerele naturale N și K și cifrele nenule și distincte $c[~1~], c[~2~], ..., c[~N~]$.
h2. Cerință
Să se determine câte numere de K cifre formate doar cu cifrele $c[~1~], c[~2~], ..., c[~N~]$ sunt divizibile cu 3. Pentru că acest număr poate fi foarte mare, rezultatul se va determina modulo 4 001.
h2. Date de intrare
Fișierul de intrare $div.in$ ...
Fișierul de intrare $div.in$ conține pe prima linie numerele naturale N și K separate printr-un spațiu, iar pe linia a doua cele N cifre distincte $c[~1~], c[~2~], ..., c[~N~]$ separate prin câte un spațiu.
h2. Date de ieșire
În fișierul de ieșire $div.out$ ...
Fișierul de ieșire $div.out$ va conține o singură linie pe care va fi scris un singur număr natural, reprezentând numărul (modulo [$4001$]) de numere de K cifre formate doar cu cifrele $c[~1~], c[~2~], ..., c[~N~]$ și divizibile cu [$3$].
h2. Restricții
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 9$
* $2 ≤ K ≤ 1 000$
* $1 ≤ c[~1~], c[~2~], ..., c[~n~] ≤ 9$
* Definim $x modulo 4 001$ ca fiind restul împărțirii întregi a lui $x$ la $4 001$. De exemplu, $4 002 modulo 4 001 = 1$.
* $Proprietăți:$
** $(a + b) modulo 4 001 = (a modulo 4001 + b modulo 4 001) modulo 4 001$
** $(a * b) modulo 4 001 = (a modulo 4001 * b modulo 4 001) modulo 4 001$
h2. Exemplu
table(example).
|_. div.in |_. div.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 3 2
1 3 2
| 3
|
h3. Explicație
h2. Explicație
...
Trebuie determinat numărul de numere de $K = 2$ cifre formate doar din cifrele [$1$], $2$ și $3$ și care sunt divizibile cu [$3$]. Acestea sunt în număr de [$3$], și anume: [$12$], [$21$], [$33$]. Rezultatul $3$ împărțit la $4001$ furnizează restul [$3$].
== include(page="template/taskfooter" task_id="div") ==
