//高斯消元 时间复杂度O(n^3) 使用浮点数计算 #include<iostream> #include<string.h> #include<math.h> using namespace std; const double eps=1e-8; const int maxn=101; double a[maxn][maxn]; bool l[maxn]; double ans[maxn]; int n,m; int t; void print(); //也可以避免实数运算 使用辗转相减的方法 多一个log的时间复杂度 //特别适合于行列式求值 取模操作 (除法要求逆元) int solve() { //a为方程组对应的矩阵 //l,ans存储解 l[]表示是否为*变元 1表示不是 0表示是 //n为未知数的个数 m为方程的个数 //如果无解返回-1 否则返回*变元数 int res=0,r=0;//r为第几行 res为*变元数 for(int i=0; i<n; ++i) l[i]=false; //开始都是*变元 for(int i=0; i<n; ++i) //枚举列 { for(int j=r; j<m; ++j) //枚举行 if(fabs(a[j][i])>eps) { //找到当前列下从第r行开始第一个不为零的元素并交换到第r行 //如果一直为0 则下面会continue res++ 即*变元+1 //如果有不为0的 把它调上来(交换行) for(int k=i; k<=n; ++k) //第j行和第r行交换 因为a[j][i]!=0 swap(a[j][k],a[r][k]); break; } // print(); //从a[r][i]这一个元素开始 往下的每个元素都是0了 所以这个元素xi是*变元 i+1跳过即可 if(fabs(a[r][i])<eps) { ++res; continue; } for(int j=0; j<m; ++j) //j是行数 从第一行(j=0)开始 让上三角更简洁 这样后面求ans就没有必要从下往上了 if(j!=r && fabs(a[j][i])>eps) { double tmp=a[j][i]/a[r][i]; for(int k=i; k<=n; ++k) a[j][k]-=tmp*a[r][k]; } l[i]=true,++r; } //检查是否无解 for(int i=n-res; i<m; ++i) { if(fabs(a[i][n])>eps) return -1; } //下面求结果 for(int i=0; i<n; ++i) if(l[i])//不是*变元 for(int j=0; j<n; ++j) if(fabs(a[j][i])>eps) ans[i]=a[j][n]/a[j][i]; return res;//返回*变元数 } void print() { for(int i=0; i<n; i++) { for(int j=0; j<=n; j++) { cout<<a[i][j]<<' '; } cout<<endl; } } int main() { ios::sync_with_stdio(false); cin>>n; m=n; for(int i=0; i<n; i++) { for(int j=0; j<=m; j++) { cin>>a[i][j]; } } cout<<solve()<<endl; print(); // cin>>t; // while(t--) // { // cin>>n; // m=n; // int ta,tb; // memset(a,0,sizeof(a)); // for(int i=0; i<n; ++i) cin>>a[i][n],a[i][i]=1; // for(int i=0; i<n; ++i) cin>>ta,a[i][n]=int(a[i][n])^ta; // while(cin>>ta>>tb&&(ta+tb)) // { // a[tb-1][ta-1]=1; // } // res=solve(a,l,ans,n,m); // if(res==-1) cout<<"Oh,it's impossible~!!"<<endl; // else cout<<(1<<res)<<endl; // } return 0; }