Fişierul intrare/ieşire:sandokan.in, sandokan.outSursăpreONI 2008, Runda finala
AutorAdrian AirineiAdăugată deastronomyAirinei Adrian astronomy
Timp execuţie pe test0.1 secLimită de memorie5120 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Sandokan

Sandokan a ales un numar natural K si a gasit pe canapea un sir cu N numere naturale distincte. El se joaca cu acest sir de numere si aplica succesiv asupra sirului urmatoarea operatie: alege K elemente distincte din sir si le elimina pe toate mai putin elementul care are valoarea maxima (dintre cele alese). Daca la un moment dat sirul are strict mai putin decat K elemente se opreste si scrie acest sir pe o foaie magica, altfel aplica in continuare operatii pe sirul rezultat. Ne este greu sa aflam ce sir a scris Sandokan, de aceea vrem doar sa aflam numarul total de posibiltati distincte de a scrie un sir pe foaia magica. Fiindca pot fi destul de multe posibilitati, vrem sa stim doar restul impartirii acestui numar la 2 000 003.

Date de intrare

Fisierul de intrare sandokan.in contine pe prima linie numerele N si K, avand semnificatia din enunt. Pe linia urmatoare urmeaza cele N numere naturale distincte.

Date de iesire

Pe prima linie a fisierului de iesire sandokan.out se afla numarul total de posibilitati distincte de a scrie un sir pe foaia magica modulo 2 000 003.

Restrictii

  • 2 ≤ K ≤ N ≤ 5 000
  • Cele N numere initiale sunt naturale si nu depasesc 2 miliarde
  • Doua posibilitati de a scrie un sir sunt distincte daca exista macar un numar care apare intr-un sir si nu apare in celalalt

Exemplu

sandokan.insandokan.out
3 3
1 2 3
1
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content