Chinese questions , Change the template structure, you can pass , The data is a little bit watery , But you still need free argument enumeration .

#include <iostream>

#include <cstdio>

#include <cmath>

#include <cstring>

#include <algorithm>

#include <queue>

#include <vector>

#include <map>

#include <ctime>

using namespace std;

const int maxn=;

// Yes equ An equation ,var Variables . The number of rows of the augmented matrix is equ, The number of columns is var+1, Respectively 0 To var

int equ,var;

int a[maxn][maxn]; // Augmented matrix

int x[maxn]; // Solution set

int free_x[maxn];// To store free variables （ Multi solution enumeration of free variables can be used ）

int free_num;// The number of free variables

// The return value is -1 There is no solution , by 0 It's the only solution , Otherwise, the number of free variables is returned

int gauss()

{

int max_r,col,k;

free_num=;

for(k=,col=; k<equ&&col<var; k++,col++)

{

max_r=k;

for(int i=k+; i<equ; i++)

if(abs(a[i][col])>abs(a[max_r][col]))

max_r=i;

if(!a[max_r][col])

{

k--;

free_x[free_num++]=col;

continue;

}

if(max_r!=k)

for(int j=col; j<var+; j++)

swap(a[k][j],a[max_r][j]);

for(int i=k+; i<equ; i++)

{

if(a[i][col])

{

for(int j=col; j<var+; j++)

a[i][j]^=a[k][j];

}

}

}

for(int i=k; i<equ; i++)

if(a[i][col])

return -;

if(k<var) return var-k;

for(int i=var-; i>=; i--)

{

x[i]=a[i][var];

for(int j=i+; j<var; j++)

x[i]^=(a[i][j]&&x[j]);

}

return ;

}

int n,m;

void init()

{

memset(a,,sizeof(a));

memset(x,,sizeof(x));

equ=n*m;

var=n*m;

for(int i=; i<n; i++)

for(int j=; j<m; j++)

{

int t=i*m+j;

a[t][t]=;

if(i>) a[(i-)*m+j][t]=;

if(i<n-) a[(i+)*m+j][t]=;

if(j>) a[i*m+j-][t]=;

if(j<m-) a[i*m+j+][t]=;

if(i>&&j>) a[(i-)*m+j-][t]=;

if(i>&&j<m-) a[(i-)*m+j+][t]=;

if(i<n-&&j>) a[(i+)*m+j-][t]=;

if(i<n-&&j<m-) a[(i+)*m+j+][t]=;

}

}

int solve()

{

int t=gauss();

if(t==-)

{

return -;

}

else if(t==)

{

int ans=;

for(int i=; i<n*m; i++)

ans+=x[i];

return ans;

}

else

{

// Enumerate free variables

int ans=0x3f3f3f3f;

int tot=(<<t);

for(int i=; i<tot; i++)

{

int cnt=;

for(int j=; j<t; j++)

{

if(i&(<<j)) // Notice that it's not &&

{

x[free_x[j]]=;

cnt++;

}

else x[free_x[j]]=;

}

for(int j=var-t-; j>=; j--)

{

int idx;

for(idx=j; idx<var; idx++)

if(a[j][idx])

break;

x[idx]=a[j][var];

for(int l=idx+; l<var; l++)

if(a[j][l])

x[idx]^=x[l];

cnt+=x[idx];

}

ans=min(ans,cnt);

}

return ans;

}

}

int main()

{

while(scanf("%d%d",&n,&m)!=EOF)

{

init();

for(int i=;i<n;i++)

for(int j=;j<m;j++)

{

cin>>a[i*m+j][n*m];

}

int ans=solve();

if(ans==-)

puts("no sovle!");

else

printf("%d\n",ans);

}

return ;

}

## NEFU 505 Super red and black ( Gauss elimination ) More articles about

- NEFU 503 Matrix solving ( Not 01 Gauss elimination of XOR )
Topic link Chinese questions , Gauss elimination template problem . #include <iostream> #include <cstdio> #include <cmath> #include ...

- 【 Gauss elimination 】BZOJ3503 [Cqoi2014] Harmony matrix
3503: [Cqoi2014] Harmony matrix Time Limit: 10 Sec Memory Limit: 128 MBSec Special JudgeSubmit: 1197 Solved: ...

- P3265 [JLOI2015] Equipment purchase （ Gauss elimination + greedy , linear algebra ）
The question ; Yes n A piece of equipment , Every outfit has m Attributes , The value of each piece of equipment is cost. The little elder brother , To save money , If the first j The attributes of a piece of equipment can be combined from other preparations . such as Each equipment attribute is expressed as , b1, b2.......bm . It can be made by ...

- [JLOI2015] Equipment purchase （ Gauss elimination ）
[JLOI2015] Equipment purchase \(solution:\) First of all, the problem surface of this problem has clearly told us that this is a problem of Gaussian elimination in linear space ( One piece of equipment can be used to represent another , It can't be more obvious ), It's just that this question requires us to ...

- HihoCoder 1195 Gauss elimination · One （ Gauss elimination ）
The question https://hihocoder.com/problemset/problem/1195 Ideas Gauss elimination is an algorithm for solving high-order equations , Complexity \(O(n^3)\) . The process is roughly : Construct an unknown number ...

- BZOJ.3143.[HNOI2013] wander ( probability expect Gauss elimination )
Topic link Reference resources The song of voyage Multiply the probability of each side by the assigned label is its expectation , So we must assign a large number to the side with the lowest probability of going . We just need to calculate the probability of passing through all the points , You can get through an edge (\(u->v\)) Of ...

- 2018.09.23 bzoj3143: [Hnoi2013] wander （dp+ Gauss elimination ）
Portal Obviously, we just need to find out the expected number of times all the edges are passed through , Then greedy put the edge power small edge Dingcheng big number . So how to find out the expected number of times all edges are passed through ? Obviously it's only about the two points where the edges connect . So we just need to find out the expected number of times two points are passed through . about ...

- 【BZOJ3143】【HNOI2013】 wander Gauss elimination
Subject portal :http://www.lydsy.com/JudgeOnline/problem.php?id=3143 We make $P_i$ Says from the first i The expected number of departures from point No . be $P_n$ Obviously $0$. about $P ...

- BZOJ3143 [Hnoi2013] wander 【 Gauss elimination 】
subject An undirected connected graph , Vertex from 1 Number to N, Side from 1 Number to M. Small Z Random walk on this graph , It's small in the beginning Z stay 1 Vertex number , Every step is small Z Randomly choose... With equal probability Select an edge of the current vertex , Go along this edge to the next vertex , Get a braid equal to this side ...

## Random recommendation

- Schema constraint
Schema constraint (*xml How to introduce schema constraint )( understand Schema: According to Schema Write XML Document to :)1.Schema The constraint document itself is a XML file .2.Schema Good for namespace support 3.S ...

- Moqui Code analysis of learning mantle priceServices.xml
<?xml version="1.0" encoding="UTF-8"?> <!-- This software is in the pub ...

- Ubuntu Can't shut down the solution
explain : If not, please refer to the last part of the article , Maybe it will help . It's not just ubuntu Inside ,fedora I also encountered this problem , The computer can be restarted , But it can't be turned off directly , Otherwise, it will stop at the shutdown interface all the time , It needs to be shut down manually . It's depressing ...

- Finding a needle in Haystack: Facebook’s photo storage
http://www.importnew.com/3292.html Object oriented storage system

- Java Timing task processing scheme under multi machine deployment (mysql)
Because I have csdn And blog Garden two blogs , So it's going to be done on both sides . csdn Address : http://blog.csdn.net/u012881584/article/details/70194237 Today, let's talk about ...

- Java The sixth wave of written interview questions （ Revised version ）
Reprinted to :http://blog.csdn.net/shakespeare001/article/details/51330745 author : Yamadai King ( Happy Yang ) This series arranges Java Related written interview knowledge , Others ...

- validator js Validator
from :https://github.com/jaywcjlove/validator.js Lightweight JavaScript Form validation , String validation . No dependence , Support UMD Import js library <script t ...

- Chapter two HTML,JavaScript brief introduction
Concept : URL: The address of the standard online resource . HTTP agreement : Standard protocol for clients to send requests and get responses . HTML: Hypertext markup language . It's a common language on the Internet , It's also the Internet web Language foundation . 2.1 Server and browser for instance :A classmate ...

- Presto Study
Presto Basic knowledge and concept learning can refer to these blogs : presto 0.166 summary https://www.cnblogs.com/sorco/p/7060166.html Presto Study -prest ...

- Java Use Log4 Log
We are using the system , For the convenience of finding problems , So you need to log the operation , At present, the more mature and stable way of program logging is Log4, I am also a rookie , And then, in the study, you can record the way you use it , For future reference , At the same time, this article refers to the blog Park : ...