题意

https://hihocoder.com/problemset/problem/1195

思路

高斯消元是解决高元方程的一种算法，复杂度 \(O(n^3)\) 。

过程大致是：

1. 构造一个未知数的倒三角，并维护多解标记；
2. 寻找是否出现没有未知数但常数非零的式子，有则返回无解；
3. 多解标记若存在则返回多解；
4. 在倒三角里倒着扫一遍，解出所有未知数。

下面是代码实现：

代码

#include<bits/stdc++.h>

#define FOR(i,x,y) for(int i=(x),i##END=(y);i<=i##END;++i)

#define DOR(i,x,y) for(int i=(x),i##END=(y);i>=i##END;--i)

typedef long long LL;

using namespace std;

const int N=505;

const double eps=1e-8;

double a[2*N][N],b[2*N];

int n,m;

int Gauss(double a[2*N][N],double b[2*N],int n,int m)

{

	bool flag=0;

	for(int i=1,r=1;i<=n;i++,r++)

	{

		bool f=0;

		FOR(j,r,m)if(fabs(a[j][i])>eps)

		{

			swap(a[j],a[r]),swap(b[j],b[r]);

			f=1;break;

		}

		if(!f){flag=1,r--;continue;}

		FOR(j,r+1,m)

		{

			FOR(k,i+1,n)a[j][k]-=a[r][k]*a[j][i]/a[r][i];

			b[j]-=b[r]*a[j][i]/a[r][i];

			a[j][i]=0;

		}

	}

	FOR(i,1,m)if(fabs(b[i])>eps)

	{

		bool f=0;

		FOR(j,1,n)if(fabs(a[i][j])>eps){f=1;break;}

		if(!f)return 0;

	}

	if(flag)return -1;

	DOR(i,n,1)

	{

		FOR(j,i+1,n)b[i]-=a[i][j]*b[j];

		b[i]/=a[i][i];

		a[i][i]=1;

	}

	return 1;

}

int main()

{

	scanf("%d%d",&n,&m);

	FOR(i,1,m)

	{

		FOR(j,1,n)scanf("%lf",&a[i][j]);

		scanf("%lf",&b[i]);

	}

	int res=Gauss(a,b,n,m);

	if(res==-1)puts("Many solutions");

	else if(res==0)puts("No solutions");

	else FOR(i,1,n)printf("%d\n",(int)(b[i]+0.5));

    return 0;

}