Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | lant2.in, lant2.out | Sursă | Lot Sibiu 2011 |
| Autor | Mugurel Ionut Andreica, Zoltan Szabo | Adăugată de |  Gavrila Vlad •GavrilaVlad |
| Timp execuţie pe test | 0.075 sec | Limită de memorie | 36864 kbytes |
| Scorul tău | N/A | Dificultate | N/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 n ≤ 1500.
Exemplu
| lant2.in | lant2.out | Explicatie |
|---|---|---|
| 10 3 | 3 | Avem trei lanţuri distincte cu 3 ochiuri din 10 segmente:   |
| 21 4 | 2520 |
