最后翻为0和1本质相同，只考虑一种。显然每个硬币最多翻一次。考虑设xi,j表示i,j位置的硬币是否翻，那么很容易就可以列出异或方程组。变量和方程都有n2个，那么解是唯一的，就不用考虑怎样最小化了。然而暴力高斯消元肯定是不行的。
考虑将所有关于xi,k和xk,j的方程叠加，由于n是偶数，可以得到xi,j=ai,k^ak,j^ai,j (k=1~n)。于是就解出来了。
#include#include #include #include #include #include using namespace std;int read(){ int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') { if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f;}#define N 1010int n,a[N][N],s[2][N],ans;int main(){#ifndef ONLINE_JUDGE freopen("bzoj3517.in","r",stdin); freopen("bzoj3517.out","w",stdout); const char LL[]="%I64d\n";#else const char LL[]="%lld\n";#endif n=read(); for (int i=1;i<=n;i++) { char c=getchar(); while (c!='0'&&c!='1') c=getchar(); for (int j=1;j<=n;j++) a[i][j]=c^48,c=getchar(); } for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) s[0][i]^=a[i][j],s[1][j]^=a[i][j]; for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) ans+=s[0][i]^s[1][j]^a[i][j]; cout<