2020牛客暑期多校训练营（第一场）D Quadratic Form 拉格朗日乘数法+求矩阵的逆

证明过程如下。

然后求个矩阵逆，矩阵乘法一下即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define re register
const int M = 200+7;
const int mod =998244353;
ll a[M][M<<1];
ll b[M],c[M];
ll qpow(ll a,ll b)
{
	ll ans=1;
	while(b)
	{
		if(b&1)ans=ans*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return ans;
}
//返回*元个数，及无穷解个数 
bool Gauss(int n,int m)//对矩阵a高斯消元得到(E|C) C为等式右边的列矩阵 
{
	int row;//当前处理的行
	int col;//当前处理的列 
  	for( row=1,col=1;row<=n&&col<=n;row++,col++)
  	{
  		int mx=row;
  		for(re int i=row+1;i<=n;i++)if(abs(a[i][col])>abs(a[mx][col]))mx=i;
  		if(mx!=row)swap(a[row],a[mx]);
  		if(a[row][col]==0)//第i行一下的i列都是0 ,处理下一列 ,这种情况下会出现 无穷解或无解 
  			return -1;
  		ll inv=qpow(a[row][col],mod-2);
  		for(re int i=1;i<=n;i++)
  		{
  			 if(row==i)continue;
  			 ll tmp=a[i][col]*inv%mod;//第i行减去第row行 * tmp，消去第i行的第col列 
  			 for(int j=col;j<=m;j++)
  			 	a[i][j]=(a[i][j]-tmp*a[row][j]%mod+mod)%mod;//cout<<"----    "<<i<<" "<<j<<" "<<a[i][j]<<endl;;
		}
		for(re int j=col;j<=m;j++)a[row][j]=inv*a[row][j]%mod;
	}
	return 0;
}
int main()
{
  	int n;
  	while(~scanf("%d",&n))
	{
		memset(a,0,sizeof(a));
		memset(c,0,sizeof(c));
	  	for(re int i=1;i<=n;i++)
	  		for(int j=1;j<=n;j++)scanf("%lld",&a[i][j]);
		for(re int i=1;i<=n;i++)a[i][i+n]=1;//构造  A|E 分块矩阵 
	  	int f=Gauss(n,2*n);//分块矩阵变换 -> E|A^(-1) 
	  	for(re int i=1;i<=n;i++)scanf("%lld",&b[i]);
	  	ll ans=0;
	  	for(re int j=1;j<=n;j++)
	  		for(re int i=1;i<=n;i++)
	  			c[j]=(c[j]+a[i][j+n]*b[i]%mod+mod)%mod;//B^T * A^(-1)
	  	for(re int i=1;i<=n;i++)ans=(ans+(ll)b[i]*c[i]%mod)%mod;
	  	printf("%lld\n",(ans+mod)%mod);
	}
  	
	return 0;
}