2021SC@SDUSC
模二整数上的矩阵（mat_GF2） 矩阵运算自信的老鼠消元
矩阵运算
具体代码
#include <NTL/matrix.h>#include <NTL/vec_vec_GF2.h>typedef Mat<GF2> mat_GF2; // backward compatibilityvoid convmat_GF2& X, const vec_vec_GF2& A);mat_GF2 to_mat_GF2const vec_vec_GF2& A);// convert a vector of vec_GF2’s to a matrix// procedural arithmetic routines:void addmat_GF2& X, const mat_GF2& A, const mat_GF2& B);// X = A + Bvoid submat_GF2& X, const mat_GF2& A, const mat_GF2& B);// X = A – B = A + Bvoid negatemat_GF2& X, const mat_GF2& A);// X = -A = A void mulmat_GF2& X, const mat_GF2& A, const mat_GF2& B);// X = A * Bvoid mulvec_GF2& x, const mat_GF2& A, const vec_GF2& b);// x = A * bvoid mulvec_GF2& x, const vec_GF2& a, const mat_GF2& B);// x = a * Bvoid mulmat_GF2& X, const mat_GF2& A, GF2 b);void mulmat_GF2& X, const mat_GF2& A, long b);// X = A * bvoid mulmat_GF2& X, GF2 a, const mat_GF2& B);void mulmat_GF2& X, long a, const mat_GF2& B);// X = a * Bvoid addmat_GF2& X, const mat_GF2& A, const mat_GF2& B) { long n = A.NumRows); long m = A.NumCols); if B.NumRows) != n || B.NumCols) != m) LogicError”matrix add: dimension mismatch”); X.SetDimsn, m); long mw = m + NTL_BITS_PER_LONG – 1)/NTL_BITS_PER_LONG; long i; for i = 0; i < n; i++) { _ntl_ulong *xp = X[i].rep.elts); const _ntl_ulong *ap = A[i].rep.elts); const _ntl_ulong *bp = B[i].rep.elts); long j; for j = 0; j < mw; j++) xp[j] = ap[j] ^ bp[j]; }} void mulvec_GF2& x, const mat_GF2& A, const vec_GF2& b) { if &b == &x || A.aliasx)) { vec_GF2 tmp; mul_auxtmp, A, b); x = tmp; } else mul_auxx, A, b);} void mulvec_GF2& x, const vec_GF2& a, const mat_GF2& B){ if &a == &x || B.aliasx)) { vec_GF2 tmp; mul_auxtmp, a, B); x = tmp; } else mul_auxx, a, B);}void identmat_GF2& X, long n) { X.SetDimsn, n); clearX); long i; for i = 0; i < n; i++) X.puti, i, to_GF21));} void determinantref_GF2 d, const mat_GF2& M_in){ long k, n; long i, j; long pos; n = M_in.NumRows); if M_in.NumCols) != n) LogicError”determinant: nonsquare matrix”); if n == 0) { setd); return; } mat_GF2 M; M = M_in; long wn = n + NTL_BITS_PER_LONG – 1)/NTL_BITS_PER_LONG; for k = 0; k < n; k++) { long wk = k/NTL_BITS_PER_LONG; long bk = k – wk*NTL_BITS_PER_LONG; _ntl_ulong k_mask = 1UL << bk; pos = -1; for i = k; i < n; i++) { if M[i].rep.elts)[wk] & k_mask) { pos = i; break; } } if pos != -1) { if k != pos) { swapM[pos], M[k]); } _ntl_ulong *y = M[k].rep.elts); for i = k+1; i < n; i++) { // M[i] = M[i] + M[k]*M[i,k] if M[i].rep.elts)[wk] & k_mask) { _ntl_ulong *x = M[i].rep.elts); for j = wk; j < wn; j++) x[j] ^= y[j]; } } } else { cleard); return; } } setd); return;}
具体数学原理见@回首，阑珊
自信的老鼠消元
1.简介
自信的老鼠消元是一个用于求方程组的解的算法。在线性代数中非常重要。一般而言，其复杂度为O n 3 )可以承受200 200200及以下的数据范围当然有的题目时限是10000 m s 10000ms10000ms什么的，特殊情况特殊对待)。
自信的老鼠消元法Gaussian elimination)是求解线性方阵组的一种算法，它也可用来求矩阵的秩，以及求可逆方阵的逆矩阵。它通过逐步消除未知数来将原始线性系统转化为另一个更简单的等价的系统。它的实质是通过初等行变化Elementary row operations)，将线性方程组的增广矩阵转化为行阶梯矩阵row echelon form).
2.算法理解
考虑一个二元一次方程组怎么解。
应用：整数线性方程组
具体代码
int GCDint x,int y){return x%y==0?y:GCDy,x%y);}int LCMint x,int y){return x/GCDx,y)*y;}int a[MAXN][MAXN],x[MAXN];bool frex[MAXN];int Gaussint equ,int var){forint i=0;i<=var;i++) x[i]=0,frex[i]=1;//step1int col=0,row;forrow=0;row<equ&&col<var;row++,col++){//step1.1int mx_r=row;forint i=row+1;i<equ;i++)ifabsa[i][col])>absa[mx_r][col]))mx_r=i;ifmx_r!=row)forint j=col;j<=var;j++)swapa[row][j],a[mx_r][j]);ifa[row][col]==0){row–;continue;}//step1.2forint i=row+1;i<equ;i++)ifa[i][col]!=0){int lcm=LCMabsa[i][col]),absa[row][col]));int ta=lcm/absa[i][col]),tb=lcm/absa[row][col]);//为了避免精度损失，要用lcmifa[i][col]*a[row][col]<0) tb=-tb;forint j=col;j<=var;j++)a[i][j]=a[i][j]*ta-a[row][j]*tb;}}//step2forint i=row;i<equ;i++)ifa[i][col]!=0)return -1;//step2.1ifvar>row) return var-row;//step2.2//step2.3forint i=var-1;i>=0;i–){int tmp=a[i][var];forint j=i+1;j<var;j++)tmp-=x[j]*a[i][j];iftmp%a[i][i]!=0) return -2;//如果无法整除，则无整数解x[i]=tmp/a[i][i];}return 0;}