原本想每个点建个五元异或方程组高斯消元解的,发现时间有点紧,就去压位卡常,结果调试的时候把自己挂在键盘上了。- -|
正解是从第一排推出第m+1排的异或表达式,然后因为m+1排的数全为0,转回来解这个异或方程组。
实现上我是消的对角线,消成上三角可能会快。出于习惯,我是把n,m互换了的。
代码:
#include#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<