高斯消元解异或方程组写法

高斯约旦消元解异或方程组

	for(int j=1;j<=n;j++){for(int i=j+1;i<=n;i++)if(a[i][j]){swap(a[i],a[j]);break;}if(!a[i][i]){if(a[i][n+1])//no...else ...//mul}for(int i=1;i<=n;i++)if(i!=j&&a[i][j])for(int k=j;k<=n+1;k++)a[i][k]^=a[j][k];}

正常高斯消元法

int r=1;for(int j=1;j<=n;j++){for(int i=r+1;i<=n;i++)if(a[i][j]){swap(a[r],a[i]);}if(!a[r][j])continue;for(int i=r+1;i<=n;i++)if(a[i][j])for(int k=1;k<=n+1;k++)a[i][k]^=a[r][k];r++;}if(r<=n){for(int i=r;i<=n;i++)if(a[i][n+1]){puts("No");return 0;}}for(int i=r-1;i>=1;i--){int j=1;while(!a[i][j]){j++;}x[j]=a[i][n+1];for(int k=j+1;k<=n;k++)if(a[i][k])x[j]^=x[k];}for(int i=1;i<=n;i++)printf("%d ",x[i]);