| Fişierul intrare/ieşire: | echival2.in, echival2.out | Sursă | Lot Deva 2013 - Baraj 2 Seniori |
| Autor | Zoltan Szabo | Adăugată de |  Rares Buhai •darren |
| Timp execuţie pe test | 0.25 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | echival2.out |
|---|---|
| 5 | 2 |
