| Fişierul intrare/ieşire: | kmax.in, kmax.out | Sursă | ONI 2010, clasele 11-12 |
| Autor | Cosmin Gheorghe | Adăugată de |  Andrei-Bogdan Antonescu •andrei-alpha |
| Timp execuţie pe test | 0.3 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | kmax.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.
