当前位置:网站首页>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
边栏推荐
- QQ computer version cancels escape character input expression
- [2020]GRAF: Generative Radiance Fields for 3D-Aware Image Synthesis
- Record the process of configuring nccl and horovod in these two days (original)
- SQLMAP使用教程(二)实战技巧一
- Erreur de connexion Navicat à la base de données Oracle Ora - 28547 ou Ora - 03135
- Leetcode-31: next spread
- MIT-6874-Deep Learning in the Life Sciences Week 7
- SPI 详解
- 阿里新成员「瓴羊」正式亮相,由阿里副总裁朋新宇带队,集结多个核心部门技术团队
- LeetCode 1200.最小绝对差
猜你喜欢
QQ电脑版取消转义符输入表情
[2021]IBRNet: Learning Multi-View Image-Based Rendering Qianqian
栈 AcWing 3302. 表达式求值
MIT-6874-Deep Learning in the Life Sciences Week 7
Appium automation test foundation - Summary of appium test environment construction
什么是套接字?Socket基本介绍
Leetcode-6108: decrypt messages
Open source storage is so popular, why do we insist on self-development?
LeetCode-54
Quickly use Amazon memorydb and build your own redis memory database
随机推荐
Golang uses context gracefully
1039 Course List for Student
CPU内核和逻辑处理器的区别
LeetCode 1200. Minimum absolute difference
11-gorm-v2-03-basic query
leetcode-9:回文数
927. 三等分 模拟
RGB LED infinite mirror controlled by Arduino
Chart. JS - Format Y axis - chart js - Formatting Y axis
中国剩余定理 AcWing 204. 表达整数的奇怪方式
1.15 - input and output system
LVS简介【暂未完成(半成品)】
Leetcode-9: palindromes
【Rust 笔记】14-集合(上)
TypeScript 基础讲解
数据可视化图表总结(一)
LeetCode 0107. Sequence traversal of binary tree II - another method
WordPress switches the page, and the domain name changes back to the IP address
Introduction to LVS [unfinished (semi-finished products)]
Multi screen computer screenshots will cut off multiple screens, not only the current screen