当前位置:网站首页>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
边栏推荐
- MIT-6874-Deep Learning in the Life Sciences Week 7
- leetcode-6110:网格图中递增路径的数目
- Navicat連接Oracle數據庫報錯ORA-28547或ORA-03135
- Sword finger offer II 058: schedule
- Operator priority, one catch, no doubt
- SQLMAP使用教程(一)
- 实时时钟 (RTC)
- Règlement sur la sécurité des réseaux dans les écoles professionnelles secondaires du concours de compétences des écoles professionnelles de la province de Guizhou en 2022
- 栈 AcWing 3302. 表达式求值
- leetcode-6108:解密消息
猜你喜欢
Leetcode-6111: spiral matrix IV
什么是套接字?Socket基本介绍
MySQL advanced part 2: storage engine
Spark中groupByKey() 和 reduceByKey() 和combineByKey()
Quickly use Amazon memorydb and build your own redis memory database
LeetCode 0108. Convert an ordered array into a binary search tree - the median of the array is the root, and the left and right of the median are the left and right subtrees respectively
MySQL advanced part 1: index
MySQL怎么运行的系列(八)14张图说明白MySQL事务原子性和undo日志原理
leetcode-6111:螺旋矩阵 IV
Appium自动化测试基础 — Appium测试环境搭建总结
随机推荐
快速使用Amazon MemoryDB并构建你专属的Redis内存数据库
Niu Mei's math problems
Nested method, calculation attribute is not applicable, use methods
[BMZCTF-pwn] ectf-2014 seddit
leetcode-6109:知道秘密的人数
WordPress switches the page, and the domain name changes back to the IP address
博弈论 AcWing 894. 拆分-Nim游戏
Leetcode-3: Longest substring without repeated characters
New title of module a of "PanYun Cup" secondary vocational network security skills competition
MySQL advanced part 1: index
LVS简介【暂未完成(半成品)】
__ builtin_ Popcount() counts the number of 1s, which are commonly used in bit operations
How to understand the definition of sequence limit?
liunx启动redis
1.15 - input and output system
【Rust 笔记】13-迭代器(下)
Leetcode-556: the next larger element III
1041 Be Unique
Appium automation test foundation - Summary of appium test environment construction
1041 Be Unique