当前位置:网站首页>高斯消元 AcWing 884. 高斯消元解异或线性方程组
高斯消元 AcWing 884. 高斯消元解异或线性方程组
2022-07-05 06:16:00 【T_Y_F666】
高斯消元 AcWing 884. 高斯消元解异或线性方程组
原题链接
算法标签
线性空间 高斯消元 异或
思路
代码
#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(){// 高斯消元,答案存于a[i][n]中,0 <= i < n
// c代表列 r代表行
int c, r;
// 按列枚举
for(c=0, r=0; c<n; ++c){
int t=r;
rep(i, r, n){
if(a[i][c]){// 找非零行
t=i;
break;
}
}
if(!a[t][c]){
continue;
}
rep(i, c, n+1){// 将非零行换到最顶端
swap(a[r][i], a[t][i]);
}
rep(i, r+1, n){// 用非零行与下面列进行运算消除为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;// 无解
}
}
return 1;// 有无穷多组解
}
Rep(i, n-1, 0){
rep(j, i+1, n){
a[i][n]^=a[i][j]*a[j][n];
}
}
return 0;// 有唯一解
}
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;
}
原创不易
转载请标明出处
如果对你有所帮助 别忘啦点赞支持哈
边栏推荐
猜你喜欢
How to adjust bugs in general projects ----- take you through the whole process by hand
liunx启动redis
Error ora-28547 or ora-03135 when Navicat connects to Oracle Database
redis发布订阅命令行实现
QQ电脑版取消转义符输入表情
MySQL advanced part 2: optimizing SQL steps
2021apmcm post game Summary - edge detection
Doing SQL performance optimization is really eye-catching
1.13 - RISC/CISC
MySQL advanced part 1: stored procedures and functions
随机推荐
LaMDA 不可能觉醒吗?
Daily question 2013 Detect square
MySQL advanced part 2: MySQL architecture
[rust notes] 14 set (Part 1)
SPI details
阿里巴巴成立企业数智服务公司“瓴羊”,聚焦企业数字化增长
一些工具的记录2022
【LeetCode】Day95-有效的数独&矩阵置零
MySQL advanced part 1: index
[rust notes] 17 concurrent (Part 2)
Matrixdb V4.5.0 was launched with a new mars2 storage engine!
【LeetCode】Day94-重塑矩阵
Leetcode recursion
Introduction to LVS [unfinished (semi-finished products)]
Leetcode stack related
js快速将json数据转换为url参数
leetcode-31:下一个排列
Regulations for network security events of vocational group in 2022 Guizhou Vocational College skill competition
Daily question 1342 Number of operations to change the number to 0
[rust notes] 16 input and output (Part 2)