Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | xnumere.in, xnumere.out | Sursă | ONI 2013 Clasele 11-12 |
| Autor | Bogdan-Cristian Tataroiu, Dragos Alin Rotaru | Adăugată de |  Popescu Silviu •crushack |
| Timp execuţie pe test | 0.5 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Xnumere
Din când în când un turist se gândeşte la o problemă dificilă (sau mai multe). Găseşte pe drum un şir de N numere intregi de la 1 la K. În călătoria spre regăsirea sinelui, fiecare şir conţine exact X numere distincte din mulţimea {1...K}. La sfârşitul călătoriei sale trage linia şi vede numărul de şiruri distincte. Bucuros că a reuşit să numere şirurile, vrea să vadă dacă şi voi puteţi găsi răspunsul la problema sa (simplă, de altfel).
Cerinta
Determina ţi numărul de şiruri distincte de lungime N cu toate numerele 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 un singur număr natural reprezentând răspunsul dat întrebării unui turist oarecare. Rezultatul va fi scris in fişier modulo 666013 .
Restricţii
- 1 ≤ X ≤ min(K,105)
- 1 ≤ N,K ≤ 1015
- Pentru 10% din teste se garantează N, K, X ≤ 7.
- Pentru 30% din teste se garantează N ≤ 10000, K ≤ 100.
- Pentru 60% din teste se garantează K ≤ 100.
- Pentru 85% din teste se garantează K ≤ 1000.
- 2 şiruri A=($x 1,$x 2,…,$x n)şi B=($y 1,$y 2,..,$y n)sunt distincte dacă există cel putin o poziţiei pentru care x i ≠y i.
Exemplu
| xnumere.in | xnumere.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
