2020牛客暑期多校训练营（第一场）D

D. Quadratic Form

题目描述

  Bobo has a positive-definite matrix and an -dimension vector . He would like to find where , and is maximum.
  It can be shown that , which is rational.
  Find the value of .

输入描述

  The input consists of several test cases terminated by end-of-file.
  The first line of each test case contains an integer .
  The -th of the following lines contains integers .
  The last line contains integers .
  , ,.
  , for any .
  .
  The sum of does not exceed .

输出描述

  For each test case, print an integer which denotes the result.

示例1

输入

2
1 0
0 1
0 0
2
1 0
0 1
1 1
2
8 4
4 3
1 1

输出

0
2
623902721

分析

  将题目转化为约束条件下的最值问题。此处只讨论极值，不讨论边界可能存在的最值。
  考虑到约束条件 为不等式约束，可以添加 条件，利用拉格朗日乘数法求解。
  首先需要讨论矩阵 的一些性质。由于 ，故 可逆。根据 且 ，得 为实对称矩阵，继而 也为实对称矩阵。又有 ，故 为正定矩阵，继而 也为正定矩阵。上述性质都会在接下来的推导中涉及。
  定义：，。 则有约束条件 ，要求最大值的表达式为 或 。
  令 ；有 方程组如下。

  将 方程组的第一式展开，得到如下方程组。

  将上述方程组写成矩阵形式，有 。即 ，等式两边取转置，得 ；，得 。代入约束条件，移项后有 ， ；由于 为正定矩阵，故 ；所以约束条件是有效的，即 。根据式 ，可得到最优解为 ；将其带入式 ，有 。
  由于 ，代入最优解 ，得 的最大值为 。于是， 最大值为 ；将式 代入，有 。
  综上所述，最终答案为 。套用矩阵求逆模板和矩阵乘法公式即可。

代码

/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: 2020牛客暑期多校训练营（第一场） Problem D
Date: 7/22/2020 
Description: 
    Use lagrange multiplier method
    Compute the inverse matrix 
*******************************************************************/
#include<algorithm>
#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
const int N=202;
const ll mod=998244353;
ll a[N][N<<1],b[N],c[N];
int n;
void inverse();
ll qpow_mod(ll a,int b);
int main()
{
    while(~scanf("%d",&n))
    {
        int i,j,k;
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
            {
                scanf("%lld",&a[i][j]);
                a[i][n+j]=0;//初始化
                a[i][j]%=mod;
            }
        }
        for(i=1;i<=n;i++)
        {
            scanf("%lld",b+i);
            b[i]%=mod;
        }
        inverse();
        //=========================================
        //a[1][1+n]*b[1]+a[2][1+n]*b[2]...
        //a[2][1+n]*b[1]+a[2][1+n]*b[2]...
        //...
        for(j=1;j<=n;j++)
        {
            ll res=0;
            for(i=1;i<=n;i++)
            {
                res+=a[i][j+n]*b[i];
                res%=mod;
            }
            c[j]=res%mod;
        }
        //c存b的转置由乘A的结果
        //==========================================
        //计算c右乘B
        ll ans=0;
        for(i=1;i<=n;i++) 
        {
            ans+=b[i]*c[i];
            ans%=mod;
        }
        //==========================================
        printf("%lld\n",ans);
    }
    return 0;
}
void inverse()//矩阵求逆模板
{
    int m=n+n;
    int i,j,k;
    for(i=1;i<=n;i++) a[i][i+n]=1;
    for(i=1;i<=n;i++)
    {
        for(j=i;j<=n;j++)
        {
            if(a[j][i])
            {
                for(k=1;k<=m;k++)
                {
                    swap(a[i][k],a[j][k]);
                }
            }
        }
        ll r=qpow_mod(a[i][i],mod-2);
        for(j=i;j<=m;j++) a[i][j]=r*a[i][j]%mod;
        for(j=1;j<=n;j++)
        {
            if(i==j) continue;
            ll rate=a[j][i]*a[i][i]%mod;
            for(k=i;k<=m;k++) 
            {
                a[j][k]=a[j][k]-rate*a[i][k]%mod;
                a[j][k]=(a[j][k]%mod+mod)%mod;
            }
        }
    }
}
ll qpow_mod(ll a,int b)
{
    ll res=1;
    while(b)
    {
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}