* 'Aplicaţii':eliminare-gaussiana#aplicatii
** 'Problema 1':elimirare-gaussiana#problema-1
** 'Go2':eliminare-gaussiana#go2

** 'Gxor':eliminare-gaussiana#gxor

* 'Bibliografie':eliminare-gaussiana#bibliografie
h2(#descriere). Descriere

Astfel înlocuind variabilele cu cele corespunzătoare de pe prima linie rămânem cu un sistem cu $M$ variabile şi $MxN$ ecuaţii. În final complexitatea va fi <tex>O((M+N)^2*M)</tex>

h2(#gxor). 'Gxor':http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=1374 (Campion 2011)
 
bq. Se consideră o matrice cu N(N<30 001) linii şi N coloane (numerotate de la 1 la N). Fiecare element al matricei poate lua valoarea 0 sau 1. Se cunosc informaţii despre G(G<401) submatrice ale matricii considerate. A i-a submatrice este definită de parametrii l1(i), c1(i), l2(i) şi c2(i) (1≤l1(i)≤l2(i)≤N ; 1≤c1(i)≤c2(i)≤N). Se ştie că xor-ul tuturor elementelor din submatricea i (elementele cuprinse între liniile l1(i) şi l2(i) inclusiv şi între coloanele c1(i) şi c2(i) inclusiv) este x(i) (evident, x(i) este 0 sau 1).
Fie NM numărul de matrice binare cu N linii şi N coloane pentru care toate informaţiile despre cele G submatrice sunt adevărate (există în total 2N∙N matrici binare cu N linii şi N coloane, dar informaţiile despre cele G submatrice nu sunt neapărat adevărate pentru toate aceste matrice). Determinaţi restul împărţirii lui NM la 34949.
 
h3. Soluţie
 
În mod evident o primă soluţie ar fi să considerăm fiecare celulă o necunoscută şi pentru fiecare informaţie să introducem o ecuaţie în sistem. Astfel vom avea $N*N$ necunoscute, ceea ce este prea mult pentru a intra în timp. În continuare vom lucra cu matricea $M[i][j]$ = suma xor a elementelor care se afla în submatricea $(1,1)$ $(i,j)$, astfel pentru o informaţie x1, y1, x2, y2, r vom şti că $M[x2][y2]^M[x1-1][y2]^M[x2][y1-1]^M[x1-1][y1-1]=r$. Vom aplica eliminarea gaussiană pe această matrice.
 

'The magic matrix':http://community.topcoder.com/stat?c=problem_statement&pm=12495
https://apps.topcoder.com/wiki/display/tc/TCO+2013+Round+2A#TheMagicMatrix
'Go2':http://www.infoarena.ro/problema/go2