Fişierul intrare/ieşire:kmax.in, kmax.outSursăONI 2010, clasele 11-12
AutorCosmin GheorgheAdăugată deandrei-alphaAndrei-Bogdan Antonescu andrei-alpha
Timp execuţie pe test0.6 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Kmax

Aurorei îi plac mult permutările. Ea defineşte o kmax-permutare ca fiind o permutare cu următoarea proprietate: pentru orice subsecvenţă cu elementele în ordine crescătoare, lungimea subsecvenţei este cel mult egală cu K. Acum, Aurora se întreabă câte kmax-permutări cu N elemente există.

Cerinţă

Pentru valorile N, K şi R date, aflaţi numărul de kmax-permutări cu N elemente. Rezultatul va fi calculat modulo R.

Date de intrare

Pe prima linie a fişierului de intrare kmax.in se vor afla numerele naturale N, K şi R, având semnificaţiile din enunţ, separate între ele prin câte un spaţiu.

Date de ieşire

Fişierul de ieşire kmax.out va conţine o singură linie pe care veţi scrie numărul de kmax-permutări cu N elemente, modulo R.

Restricţii

  • 1 ≤ K ≤ N ≤ 300
  • 10 ≤ R ≤ 30000
  • O subsecvenţă a unei permutări este formată din elemente situate pe poziţii consecutive.
  • Pentru 20% din teste N ≤ 10
  • Pentru 60% din teste N ≤ 150

Exemplu

kmax.inkmax.out
4 2 997
17
30 10 27017
21690

Explicatie

Dintre cele 24 de permutări de 4 elemente NU sunt 2max-permutări următoarele 7:
1 2 3 4
1 2 4 3
1 3 4 2
2 1 3 4
2 3 4 1
3 1 2 4
4 1 2 3
După cum se observă, toate cele şapte permutări de mai sus au cel puţin o secvenţă cu elementele în ordine crescătoare de lungime mai mare decât 2.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content