首页 > 代码库 > Bzoj3503--Cqoi2014和谐矩阵

Bzoj3503--Cqoi2014和谐矩阵

2024-08-16 14:28:06   215人阅读

原本想每个点建个五元异或方程组高斯消元解的，发现时间有点紧，就去压位卡常，结果调试的时候把自己挂在键盘上了。- -|

正解是从第一排推出第m+1排的异或表达式，然后因为m+1排的数全为0，转回来解这个异或方程组。

实现上我是消的对角线，消成上三角可能会快。出于习惯，我是把n，m互换了的。

代码：

#include<bits/stdc++.h>#define INF 1000000000#define LNF 100000000000000ll#define eps 1e-9#define LL long long#define MOD 1000000007inline int _max(int a,int b) {return a>b?a:b;}inline double _fabs(double a) {return a>0?a:-a;}using namespace std;#define MAXN 45#define MAXM 1605LL xr[MAXN][MAXN],gs[MAXN];int m,n,num[MAXN],mp[MAXN][MAXN];void Gauss() {    int p,now=1;    for(int i=1;i<=m;i++) {        p=now;        while(p<=m&&!(gs[p]>>i&1)) p++;        if(p>m) continue;        swap(gs[p],gs[i]);swap(num[p],num[i]);        for(int j=1;j<=m;j++) if(i!=j&&gs[j]>>i&1)             gs[j]^=gs[i];        now++;    }    p=m;    for(int i=m;i;i--) {        if(!(gs[i]>>i&1)) {mp[1][i]=1;continue;}        for(int j=i+1;j<=m;j++) if(gs[i]>>j&1) mp[1][i]^=mp[1][j];    }    for(int i=2;i<=n;i++)         for(int j=1;j<=m;j++)             mp[i][j]=mp[i-1][j]^mp[i-1][j-1]^mp[i-1][j+1]^mp[i-2][j];}int main() {    scanf("%d%d",&n,&m);    for(int i=1;i<=m;i++) xr[1][i]=1ll<<i;    for(int i=2;i<=n+1;i++)         for(int j=1;j<=m;j++)             xr[i][j]^=xr[i-1][j]^xr[i-1][j-1]^xr[i-1][j+1]^xr[i-2][j];    for(int i=1;i<=m;i++) gs[i]=xr[n+1][i],num[i]=i;    Gauss();    for(int i=1;i<=n;i++) {        printf("%d",mp[i][1]);        for(int j=2;j<=m;j++) printf(" %d",mp[i][j]);        printf("\n");    }    return 0;}

 

Bzoj3503--Cqoi2014和谐矩阵


联系
我们