Fişierul intrare/ieşire:lant2.in, lant2.outSursăLot Sibiu 2011
AutorMugurel Ionut Andreica, Zoltan SzaboAdăugată deGavrilaVladGavrila Vlad GavrilaVlad
Timp execuţie pe test0.15 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Lant2

Avem la dispoziţie m segmente, toate de aceeaşi lungime. Din aceste segmente se pot construi poligoane închise de lungime 3, 4, 5, etc... pe care le vom numi ochiuri.

Aceste ochiuri vor fi legate între ele cu ajutorul a 0 sau mai multe segmente. Un astfel de lanţ obţinut întotdeauna începe şi se termină cu un ochi. Exemplele de mai jos reprezintă câte un lanţ format cu 3 ochiuri din 16 segmente.

Două lanţuri se consideră echivalente dacă conţin acelaşi număr m de segmente, acelaşi număr k de ochiuri şi ochiurile corespondente au aceeaşi dimensiune şi sunt legate de acelaşi număr de segmente. Dacă două lanţuri nu sunt echivalente, le vom numi diferite.
Lanţurile din exemplele 1 şi 2 sunt echivalente, iar lanţurile din exemplele 3 şi 4 diferă de celelalte trei lanţuri.

Să se determine numărul de lanţuri diferite formate din m segmente şi având k ochiuri.

Date de intrare

Fişierul lant2.in conţine pe o singură linie cele două numere naturale m şi k separate printr-un spaţiu.

Date de ieşire

Fişierul lant2.out va conţine un singur număr natural, reprezentând numărul lanţurilor distincte modulo 666013.

Restricţii

  • 3 ≤ m ≤ 600 000
  • k ≤ m/3
  • Pentru 30% din teste m ≤ 200.
  • Pentru alte 30% din teste m ≤ 1500.

Exemplu

lant2.inlant2.outExplicatie
10 3
3
Avem trei lanţuri distincte cu 3 ochiuri din 10 segmente:
21 4
2520
 
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content