.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » xnumere

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
xnumere


Timp maxim de execuţie / test:
1.2s
Memorie totala disponibilă / stivă:
64MB / 16MB

Se consideră şirurile formate din N numere întregi de la 1 la K, cu proprietatea că şirul conţine exact X numere distincte.

Cerinţă

Determinaţi numărul de şiruri distincte de lungime N cu elemente din mulţimea {1...K}, fiecare şir având exact X elemente distincte.

Date de intrare

Fişierul xnumere.in va conţine pe prima linie trei numere naturale K X N.

Date de ieşire

Fişierul xnumere.out va conţine o singură linie pe care va fi scris un număr natural reprezentând rezultatul modulo 666013.

Restricţii

1 ≤ X ≤ min(K, 105)
1 ≤ N, K ≤ 1015
• Două şiruri A=(x1,x2,…,xn) şi B=(y1,y2,...,yn) sunt distincte dacă există cel puţin o poziţie i pentru care xi≠yi.

Exemple

xnumere.inxnumere.outExplicaţii
2 2 4 14 Şirurile sunt:
(1,1,1,2),(1,1,2,1),(1,1,2,2),(1,2,1,1),
(1,2,1,2),(1,2,2,1),(1,2,2,2),(2,1,1,1),
(2,1,1,2),(2,1,2,1),(2,1,2,2),(2,2,1,1),
(2,2,1,2),(2,2,2,1)
10 6 8 258420

autor: stud. Dragoş Alin Rotaru
propunător: Prof. Emanuela Cerchez
Colegiul Naţional ″Emil Racoviţă″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
surse trimise | ajutor