php网站建设制作,cpa网站建设教程,thinkphpcmf网站开发,杭州家具网站建设方案ACM模板 目录高斯消元解线性方程组异或方程组bitset优化异或方程组高斯消元解线性方程组 int a[N][N]输入矩阵#xff0c;nnn行#xff0c;n1n1n1列#xff0c;下标从0开始 第n1n1n1列表示方程右边的值#xff08;n行即n个方程#xff0c;n列即n个未知数#xff09; int…ACM模板 目录高斯消元解线性方程组异或方程组bitset优化异或方程组高斯消元解线性方程组 int a[N][N]输入矩阵nnn行n1n1n1列下标从0开始 第n1n1n1列表示方程右边的值n行即n个方程n列即n个未知数 int gauss()返回矩阵的秩矛盾无解返回-1并且系数矩阵化为单位矩阵 int a[N][N]数组第n1n1n1列下标a[i][n]是解xix_ixi 时间复杂度O(n3)O(n^3)O(n3) //O(n^3)
#includebits/stdc.h
using namespace std;
const int N110;
const double eps1e-6;
int n;
double a[N][N];
int gauss()
{int c,r;for(c0,r0;cn;c) //枚举每一列{ //找该列绝对值最大的一行 精度int tr;for(int ir;in;i)if(fabs(a[i][c])fabs(a[t][c])) ti;// 该列都为0 则跳过if(fabs(a[t][c])eps) continue;// 将该行换到第r行for(int ic;in;i) swap(a[r][i],a[t][i]);// 第r行第一项变成1for(int in;ic;i--) a[r][i]/a[r][c];// 变成上三角 用第r行去消掉其他所有行的第c列for(int i0;in;i)if(i!rfabs(a[i][c])eps) //该行第c列不为0for(int jn;jc;j--)a[i][j]-a[i][c]*a[r][j];r;}if(rn) //非完美阶梯型{for(int ir;in;i)if(a[i][n]eps) return -1; // 等式右端不为0return r; //返回秩}return r;
}异或方程组 第n1n1n1列表示方程右边的值n行即n个方程n列即n个未知数 int gauss返回矩阵的秩 时间复杂度O(n3)O(n^3)O(n3) #includeiostream
using namespace std;
const int N110;
int n,a[N][N];
int gauss()
{int r,c;for(c0,r0;cn;c) //枚举列{int tr; //找到不为1的那一行for(int ir;in;i)if(a[i][c]) ti;if(!a[t][c]) continue; //该列都是0// 不为1的一行换到第r行for(int jc;jn;j) swap(a[r][j],a[t][j]);// 异或消 第r行消去他们的第c列for(int i0;in;i)if(i!ra[i][c])for(int jn;jc;j--)a[i][j]^a[r][j];r;}if(rn){for(int ir;in;i)if(a[i][n]) return -1;return r;}return r;
}bitset优化异或方程组 bitset的原理大概是将很多数压成一个从而节省空间和时间时间复杂度的www通常是32 nnn行mmm列即nnn个方程mmm个未知数 int gauss返回矩阵的秩 注意bitset对于字符串第位在前而数字第位表示二进制中数字的最低二进制位 时间复杂度O(n3w)O(\frac{n^3}{w})O(wn3) #includebitset
using namespace std;
const int N1010;
bitsetN A[N];
int n,m;
int gauss()
{int r,c;for(c0,r0;cm;c){int tr;for(int ir;in;i)if(A[i][c]) ti;if(!A[t][c]) continue;swap(A[r],A[t]);for(int i0;in;i)if(i!rA[i][c])A[i]^A[r];r;}if(rm){for(int ir;in;i)if(A[i][m]) return -1;return r;}return r;
}
