kmax

Time limit: 0.2s
Memory limit: 16MB
Input: kmax.in
Output: kmax.out

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 şi precizări

  • 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

4 2 997		

kmax.out

17

Explicaţie

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.

kmax.in

30 10 27017	

kmax.out

21690

Problem info

ID: 180

Editor: liviu

Author:

Source: ONI 2010 XI-XII: Ziua 1, Problema 1

Tags:

ONI 2010 XI-XII

Log in or sign up to be able to send submissions!