| Fişierul intrare/ieşire: | poligoane.in, poligoane.out | Sursă | Tiberiu Popoviciu 2011, Clasa a 10-a |
| Autor | Perticas Catalin | Adăugată de |  perticas catalin •perticas_catalin |
| Timp execuţie pe test | 0.125 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Poligoane
Mitruţ are N beţe de lungimi egale şi nu prea ştie ce să facă cu ele. Voi îi daţi idea să formeze poligoane convexe din ele, iar el vă întreabă acum în câte feluri le poate grupa. Mitruţ vă sfătuieşte să vă uitaţi la exemplu pentru a înţelege mai bine ce vă cere.
Cerinţă
Vi se pun T teste la dispoziţie. Pentru fiecare trebuie să afişaţi numărul de moduri în care se pot grupa beţele pentru a forma poligoane convexe regulate modulo un număr dat.
Date de intrare
Fişierul de intrare poligoane.in conţine pe prima linie numărul T. Pe fiecare din următoarele T linii se află câte două numere Ni şi MODi.
Date de ieşire
Fişierul de ieşire poligoane.out conţine T linii. Pe linia i se va afla numărul cerut pentru Ni modulo MODi.
Restricţii
- 1 ≤ T ≤ 10
- 3 ≤ Ni ≤ 2 000
- 1 ≤ MODi ≤ 1 000 000
- Pentru 20% din teste Ni ≤ 80
- Pentru alte 40% din teste Ni ≤ 1000
Exemplu
| poligoane.in | poligoane.out |
|---|---|
| 7 3 7 6 13 4 17 11 23 12 19 13 31 799 666013 | 1 2 1 6 9 10 29846 |
Explicaţie
Din 3 beţe se poate forma un singur poligon convex: un triunghi.
Pentru 6 avem două variante: un hexagon sau două triunghiuri.
Din 4 beţe putem forma doar un pătrat.
Pentru 11 beţe avem următoarele variante de grupare:
11, 8 + 3, 7 + 4, 6 + 5, 4 + 4 + 3, 5 + 3 + 3, adică putem forma fie un poligon cu 11 laturi, fie un octogon şi un triunghi, fie un hexagon şi un pentagon etc.
