Fişierul intrare/ieşire:echival2.in, echival2.outSursăLot Deva 2013 - Baraj 2 Seniori
AutorZoltan SzaboAdăugată dedarrenRares Buhai darren
Timp execuţie pe test0.25 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Echival2

Fie mulţimea M = {1, 2, 3, ... , n}. Vom defini o bipermutare de ordin n ca o matrice a cu două linii şi n coloane, în care fiecare număr k al mulţimii M apare în matrice pe două coloane distincte (figurile 1, 2, 3 şi 4 conţin câte o bipermutare, iar matricea din figura 0 nu este bipermutare). Într-o bipermutare putem efectua următoarele operaţii:

  • să schimbăm două elemente de pe o aceeaşi coloană (figura 1 => figura 2)
  • să schimbăm două coloane între ele (figura 1 => figura 3)
  • să schimbăm în bipermutare două valori distincte x şi y între ele (figura 1 => figura 4)

Două bipermutări sunt echivalente, dacă există o succesiune de operaţii prin care din prima bipermutare se poate ajunge la a doua bipermutare. În figurile de mai sus toate cele patru bipermutări sunt echivalente. Dacă două bipermutări sunt echivalente, atunci ele aparţin aceleiaşi clase de echivalenţă.

Cerinţă

Dându-se un număr natural n, determinaţi numărul claselor de echivalenţă distincte modulo 1114111.

Date de intrare

Fişierul de intrare echival2.in conţine pe prima linie numărul natural n, cu semnificaţia de mai sus.

Date de ieşire

Fişierul de ieşire echival2.out va conţine pe prima linie numărul claselor de echivalenţă modulo 1114111.

Restricţii

  • 2 < n ≤ 100000

Exemplu

echival2.inechival2.out
5
2
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content