当前位置:网站首页>Gaussian elimination acwing 884 Gauss elimination for solving XOR linear equations
Gaussian elimination acwing 884 Gauss elimination for solving XOR linear equations
2022-07-05 06:18:00 【T_ Y_ F666】
Gauss elimination AcWing 884. Gauss elimination is used to solve XOR linear equations
Original link
AcWing 884. Gauss elimination is used to solve XOR linear equations
Algorithm tags
Linear space Gauss elimination Exclusive or
Ideas
Code
#include<bits/stdc++.h>
#define int long long
#define abs fabs
#define rep(i, a, b) for(int i=a;i<b;++i)
#define Rep(i, a, b) for(int i=a;i>=b;--i)
using namespace std;
const int N = 105;
int a[N][N], eps = 1e-8;
int n;
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
void put(int x) {
if(x<0) putchar('-'),x=-x;
if(x>=10) put(x/10);
putchar(x%10^48);
}
int gu(){// Gauss elimination , The answer lies in a[i][n] in ,0 <= i < n
// c Representative column r On behalf of the line
int c, r;
// Enumerate by column
for(c=0, r=0; c<n; ++c){
int t=r;
rep(i, r, n){
if(a[i][c]){// Find non-zero line
t=i;
break;
}
}
if(!a[t][c]){
continue;
}
rep(i, c, n+1){// Change non-zero lines to the top
swap(a[r][i], a[t][i]);
}
rep(i, r+1, n){// Use non-zero rows and the following columns to eliminate as 0
if(a[i][c]){
Rep(j, n, c){
a[i][j]^=a[r][j];
}
}
}
++r;
}
if(r<n){
rep(i, r, n){
if(abs(a[i][n])>eps){
return 2;// unsolvable
}
}
return 1;// There are infinite sets of solutions
}
Rep(i, n-1, 0){
rep(j, i+1, n){
a[i][n]^=a[i][j]*a[j][n];
}
}
return 0;// There is a unique solution
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
n=read();
rep(i, 0, n){
rep(j, 0, n+1){
a[i][j]=read();
}
}
int t=gu();
if(t==2){
puts("No solution");
}else if(t==1){
puts("Multiple sets of solutions");
}else{
rep(i, 0, n){
printf("%lld\n", a[i][n]);
}
}
return 0;
}
Originality is not easy.
Reprint please indicate the source
If it helps you Don't forget to praise and support
边栏推荐
- Overview of variable resistors - structure, operation and different applications
- Records of some tools 2022
- Flutter Web 硬件键盘监听
- Sum of three terms (construction)
- Leetcode-1200: minimum absolute difference
- One question per day 1020 Number of enclaves
- Chart. JS - Format Y axis - chart js - Formatting Y axis
- Basic explanation of typescript
- QQ电脑版取消转义符输入表情
- Simple selection sort of selection sort
猜你喜欢
Leetcode stack related
快速使用Amazon MemoryDB并构建你专属的Redis内存数据库
【LeetCode】Easy | 20. Valid parentheses
MIT-6874-Deep Learning in the Life Sciences Week 7
MatrixDB v4.5.0 重磅发布,全新推出 MARS2 存储引擎!
背包问题 AcWing 9. 分组背包问题
Leetcode array operation
Redis publish subscribe command line implementation
SPI 详解
[2021]IBRNet: Learning Multi-View Image-Based Rendering Qianqian
随机推荐
Leetcode heap correlation
redis发布订阅命令行实现
LeetCode 1200. Minimum absolute difference
Data visualization chart summary (I)
Presentation of attribute value of an item
Daily question 1189 Maximum number of "balloons"
MySQL advanced part 1: index
RGB LED infinite mirror controlled by Arduino
leetcode-6111:螺旋矩阵 IV
对for(var i = 0;i < 5;i++) {setTimeout(() => console.log(i),1000)}的深入分析
【LeetCode】Day94-重塑矩阵
Network security skills competition in Secondary Vocational Schools -- a tutorial article on middleware penetration testing in Guangxi regional competition
11-gorm-v2-03-basic query
【Rust 笔记】17-并发(下)
Sum of three terms (construction)
The difference between CPU core and logical processor
Appium自动化测试基础 — Appium测试环境搭建总结
背包问题 AcWing 9. 分组背包问题
Error ora-28547 or ora-03135 when Navicat connects to Oracle Database
Data visualization chart summary (II)