== include(page="template/taskheader" task_id="permbit") ==
Se da un sir de $M$ biti. Se permuta cu permutarea $P$ de ordin $M$. Noul sir se cunoaste si se permuta din nou, tot cu permutarea $P$. Si tot asa. Pana se obtin $N$ siruri. Gasiti:
$a)$ Numarul de permutari $P$ corecte
$b)$ O permutare $P$ oarecare corecta
$c)$ Permutarea mediana $P$ (sortand lexicografic toate permutarile corecte, se considera cea care se afla la mijloc - in caz ca sunt permutari la mijloc, se considera cea mai mica lexicografic)
Se dau $N$ şiruri a câte $M$ elemente binare, al $i$-lea şir fiind notat $S{~i~}$. Fie mulţimea permutărilor $P$ care au proprietatea că, aplicate oricarui şir din cele date, se obţine urmatorul şir. Mai exact, permutarea $P$ este validă dacă:
<tex>S_i_j = S_{(i+1)}_{P[j]}, \hspace{5} \forall \hspace{3} 1 \leq i < n, 1 \leq j \leq m</tex>
Se cere să se afişeze:
$a)$ O permutare $P$ oarecare validă
$b)$ Permutarea mediană $P$ (sortând lexicografic toate permutările corecte, se consideră cea care se află la mijloc, în caz că sunt două permutări la mijloc, se considera cea mai mică lexicografic)
$c)$ Numarul de permutări $P$ valide modulo $10^9^ + 7$.
Se garantează că există cel puţin o permutare care respectă proprietatea de mai sus.
h2. Date de intrare
Fişierul de intrare $permbit.in$ are pe prima linie numerele $C$, $N$ si $M$, iar pe urmatoarele $N$ linii cate un sir de $M$ biti. $C$ reprezinta tipul cerintei: $0$ pentru cerinta $a)$, $1$ pentru cerinta $b)$, $2$ pentru cerinta $c)$.
Fişierul de intrare $permbit.in$ conţine pe prima linie numărul $C$, reprezentând cerinţa pe testul respectiv: $1$ pentru cerinţa $a)$, $2$ pentru cerinţa $b)$ şi $3$ pentru cerinţa $c)$.
Pe următoarea linie se află numerele $N$ şi $M$, iar pe următoarele $N$ linii câte un şir de $M$ biţi.
h2. Date de ieşire
În fişierul de ieşire $permbit.out$ se afla, daca $C = 0$, numarul de permutari corecte *modulo $1.000.000.007$*, iar daca nu, o permutare, dupa caz, oarecare sau mediana.
În fişierul de ieşire $permbit.out$ se afla, daca $C = 3$, numărul de permutări corecte *modulo $1.000.000.007$*, iar dacă nu, o permutare, după caz, oarecare sau mediană.
h2. Restrictie
* $2 ≤ N, M$
h2. Restricţii
h2. Punctare
* $5$ puncte: $N, M ≤ 8; C = 0$
* $5$ puncte: $N, M ≤ 8; C = 1$
* $10$ puncte: $N, M ≤ 100; C = 0$
* $10$ puncte: $N, M ≤ 100; C = 1$
* $10$ puncte: $N, M ≤ 100; C = 2$
* $10$ puncte: $N * M ≤ 10^6^; C = *1*$
* $20$ de puncte: $N * M ≤ 10^6^; C = *2*$
* $30$ de puncte: $N * M ≤ 10^6^; C = *0*$
* $2 ≤ N, M, *N * M* ≤ 10^6^$
* $10$ puncte: $N, M ≤ 8, 1 ≤ C ≤ 3$
* $10$ puncte: $N, M ≤ 300, C = 1$
* $10$ puncte: $N, M ≤ 300, C = 2$
* $10$ puncte: $N, M ≤ 300, C = 3$
* $30$ puncte: $N * M ≤ 10^6^, C = *2*$
* $10$ de puncte: $N * M ≤ 10^6^, C = *1*$
* $20$ de puncte: $N * M ≤ 10^6^, C = *3*$
h2. Exemplu
table(example). |_. permbit.in |_. permbit.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicaţie
| 1
3 8
10111010
11000111
01111100
| 2 5 8 7 1 4 6 3
|
| 2
3 10
0000011010
0001100001
1010000100
| 6 9 7 8 3 10 5 2 4 1
|
| 3
3 6
001100
000011
100100
| 8
|
...
== include(page="template/taskfooter" task_id="permbit") ==
== include(page="template/taskfooter" task_id="permbit") ==
