题解 P3164 【[CQOI2014]和谐矩阵】

stoorz · 2020-02-28 18:16:02 · 题解

对于矩阵中的一个点 (x,y)，就是要我们求出一种方案满足 a[x][y]\ \operatorname{xor}\ a[x-1][y]\ \operatorname{xor}\ a[x+1][y]\ \operatorname{xor}\ a[x][y-1]\ \operatorname{xor}\ a[x][y+1]=0。

那么我们对于每一个点 (x,y)，我们可以列出一个形如 a_1x_1\ \operatorname{xor}\ a_2x_2\ \operatorname{xor}\ ...\ \operatorname{xor}\ a_{nm}x_{nm}=0 的方程。其中如果一个点与 (x,y) 相邻或就是 (x,y)，那么该位置的系数 a=1，否则 a=0。

然后就是高斯消元板子了。

时间复杂度 O \Large{(} (nm)^3 \Large{)}。显然跑不过。 我们发现，题目要求是 01 矩阵，每一位的取值就只有 0 或 1。所以可以用 \operatorname{bitset} 搞搞，可以简单理解为状压。时间复杂度 O(\frac{(nm)^3}{32})。

#include <cstdio>
#include <bitset>
#include <cstring>
#include <algorithm>
using namespace std;

const int N=50;
const int dx[]={0,0,0,-1,1},dy[]={0,-1,1,0,0};
int n,m,id[N][N],ans[N*N];
bitset<N*N> a[N*N];

void gauss()
{
    for (int i=1;i<=n*m;i++)
    {
        for (int j=i;j<=n*m;j++)
            if (a[j][i]>0)  //找到一个该位置系数为 1 的方程
            {
                swap(a[i],a[j]);
                break;
            }
        if (!a[i][i]) ans[i]=1;  //这项是自由元，直接取 1 即可
        for (int j=i+1;j<=n*m;j++)
            if (a[j][i]) a[j]^=a[i];
    }
    for (int i=n*m;i>=1;i--)
        for (int j=i+1;j<=n*m;j++)
            ans[i]^=(ans[j]*a[i][j]);  //求解
}

int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            id[i][j]=(i-1)*m+j;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
        {
            for (int k=0;k<=4;k++)
            {
                int x=i+dx[k],y=j+dy[k];
                if (x<1 || y<1 || x>n || y>m) continue;
                a[id[i][j]][id[x][y]]=1;
            }
        }
    gauss();
    for (int i=1;i<=n*m;i++)
    {
        printf("%d ",ans[i]);
        if (i%m==0) putchar(10);
    }
    return 0;
}