题目链接

BZOJ 3503

题解

没想到……直接用暴力的\(O((nm)^3)\)算法，居然能过？！

高斯消元解异或方程组。

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <iostream>

#define space putchar(' ')

#define enter putchar('\n')

typedef long long ll;

using namespace std;

template <class T>

void read(T &x){

    char c;

    bool op = 0;

    while(c = getchar(), c < '0' || c > '9')

	if(c == '-') op = 1;

    x = c - '0';

    while(c = getchar(), c >= '0' && c <= '9')

	x = x * 10 + c - '0';

    if(op) x = -x;

}

template <class T>

void write(T x){

    if(x < 0) putchar('-'), x = -x;

    if(x >= 10) write(x / 10);

    putchar('0' + x % 10);

}

const int N = 1605;

int n, m, x, g[N][N], ans[N];

const int dx[5] = {0, -1, 1, 0, 0};

const int dy[5] = {0, 0, 0, -1, 1};

void gauss(){

    for(int i = 1; i <= x; i++){

	if(!g[i][i])

	    for(int j = i + 1; j <= x; j++)

		if(g[j][i]){

		    for(int k = 1; k <= x + 1; k++)

			swap(g[i][k], g[j][k]);

		    break;

		}

	for(int j = i + 1; j <= x; j++)

	    if(g[j][i])

		for(int k = i; k <= x + 1; k++)

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

    }

    for(int i = x; i; i--){

	if(!g[i][i]) ans[i] = 1;

	else{

	    for(int j = i + 1; j <= x; j++)

		g[i][x + 1] ^= ans[j] & g[i][j];

	    ans[i] = g[i][x + 1];

	}

    }

}

int main(){

    read(n), read(m);

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

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

	    x++;

	    for(int d = 0; d <= 4; d++){

		int ti = i + dx[d], tj = j + dy[d];

		if(ti <= n && tj <= m && ti && tj)

		    g[x][(ti - 1) * m + tj] = 1;

	    }

	}

    gauss();

    for(int i = 1; i <= x; i++)

	write(ans[i]), i % m ? space: enter;

    return 0;

}