Fişierul intrare/ieşire:lkperm.in, lkperm.outSursăAlgoritmiada 2010, Runda Finala
AutorBogdan-Cristian Tataroiu, Cosmin GheorgheAdăugată degcosminGheorghe Cosmin gcosmin
Timp execuţie pe test0.075 secLimită de memorie66048 kbytes
Scorul tăuN/ADificultateN/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.inlkperm.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content