Fişierul intrare/ieşire:dirichlet.in, dirichlet.outSursă.com 2011
AutorRadu Stefan VoroneanuAdăugată decezar305Mr. Noname cezar305
Timp execuţie pe test0.05 secLimită de memorie12288 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Dirichlet

Avem la dispozitie N bile si N cutii. Dorim sa impartim toate bilele in cutii astfel incat sa respecte urmatoarele conditii : prima cutie sa contina maxim o bila, primele 2 cutii sa contina maxim 2 bile, primele 3 cutii sa contina maxim 3 bile s.a.m.d. In cate moduri se poate realiza aceasta impartire?

Sa se afle numarul de moduri in care se poate realiza impartirea bilelor astfel incat sa se respecte conditiile. Deoarece numarul acestora poate fii destul de mare rezultatul se va calcula modulo 9999991.

Date de intrare

Fişierul de intrare dirichlet.in va contine numarul natural N reprezentand numarul de bile, respectiv de cutii.

Date de ieşire

În fişierul de ieşire dirichlet.out va contine un singur numar natural care reprezinta raspunsul cerintei.

Restricţii

  • 1 ≤ N ≤ 1.000.000
  • a modulo b reprezinta restul impartirii lui a la b
  • Atentie! Se recomanda folosirea tipului long long pentru cei care implementeaza in C/C++ si int64 pentru cei care implementeaza in Pascal

Exemplu

dirichlet.indirichlet.out
3
5

Explicatii

pentru 3:
(*)(*)(*)
(*)()(**)
()(*)(**)
()(**)(*)
()()(***)

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content