| Fişierul intrare/ieşire: | matcnt.in, matcnt.out | Sursă | Lot Botosani 2012 - Baraj 1 Seniori |
| Autor | Dan Pracsiu | Adăugată de |  Eugenie Daniel Posdarascu •eudanip |
| Timp execuţie pe test | 0.1 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Matcnt
Considerăm matricele pătratice cu N linii şi N coloane care memorează numai valori 0 şi 1 şi care îndeplinesc următoarele condiţii:
- au pe fiecare linie exact două valori egale cu 1
- au pe fiecare coloană exact două valori egale cu 1
- nu există în matrice patru valori de 1 care să fie colţurile unei submatrice.
În exemplele de mai jos, prima matrice îndeplineşte cele trei condiţii, dar a doua matrice nu satisface condiţia a treia:
Să se determine numărul acestor matrice. Pentru că acest număr poate fi foarte mare, se va afişa rezultatul modulo 200003.
Date de intrare
Fişierul de intrare matcnt.in va conţine numărul natural N.
Date de ieşire
Fişierul de ieşire matcnt.out va conţine pe prima linie un număr natural reprezentând numărul matricelor, modulo 200003.
Restricţii
- 3 ≤ N ≤ 100 000
- Pentru 30% din teste, N ≤ 50
- Pentru alte 30% din teste, N ≤ 1000
Exemplu
| matcnt.in | matcnt.out |
|---|---|
| 3 | 6 |
Explicaţie
Cele 6 matrice sunt:
011 011 101 101 110 110
101 110 011 110 011 101
110 101 110 011 101 011
Trebuie sa te autentifici pentru a trimite solutii. Click aici
