| Fişierul intrare/ieşire: | lkperm.in, lkperm.out | Sursă | Algoritmiada 2010, Runda Finala |
| Autor | Bogdan-Cristian Tataroiu, Cosmin Gheorghe | Adăugată de |  Gheorghe Cosmin •gcosmin |
| Timp execuţie pe test | 0.075 sec | Limită de memorie | 66048 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Lkperm
Afrodita a decis ca singurele permutari frumoase sunt LK-permutarile. O LK-permutare este o permutare ce respecta urmatoarea conditie: pentru orice subsecventa de L elemente consecutive, elementul maxim al acestei subsecvente se afla in primele K elemente ale subsecventei. Mai exact pentru o permutare P cu N elemente, orice subsecventa Pi, Pi+1, ..., Pi+L-1 ( i+L-1 ≤ N ) cu Pk = max(Pi, Pi+1, ..., Pi+L-1) respecta i ≤ k ≤ i + K - 1. Cine o va ajuta pe Afrodita sa afle cate LK-permutari cu N elemente exista, va fi rasplatit cu frumuseste fara margini.
Date de intrare
Fisierul de intrare lkperm.in va contine pe prima linie trei numere naturale N, L si K separate prin cate un spatiu, avand semnificatia din enunt.
Date de ieşire
In fisierul de iesire lkperm.out veti afisa un singur numar reprezentand numarul de LK-permutari cu N elemente modulo 100 019.
Restricţii
- 1 ≤ N ≤ 100 000
- 1 ≤ K ≤ L ≤ N
- Pentru 40% din teste N ≤ 1 000
- Pentru 60% din teste N ≤ 10 000 si K ≤ 1 000
Exemplu
| lkperm.in | lkperm.out |
|---|---|
| 4 3 2 | 10 |
Explicaţie
Toate 32-permutarile cu 4 elemente sunt: 1 4 2 3, 1 4 3 2, 2 4 1 3, 2 4 3 1, 3 4 1 2, 3 4 2 1, 4 1 3 2, 4 2 3 1, 4 3 1 2, 4 3 2 1.
