Fişierul intrare/ieşire:matcnt.in, matcnt.outSursăLot Botosani 2012 - Baraj 1 Seniori
AutorDan PracsiuAdăugată deeudanipEugenie Daniel Posdarascu eudanip
Timp execuţie pe test0.1 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/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.inmatcnt.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

Cum se trimit solutii?