[2020牛客多校第一场][D. Quadratic Form]

题目链接：https://ac.nowcoder.com/acm/contest/5666/D

题目大意：给定一实正定二次型矩阵(A)，求当(sum_{i=1}^nsum_{j=1}^{n}A_{ij}x_ix_jle 1)，即(x^TAx le 1)时，(sum_{i=1}^n b_ix_i)的最大值

题解：由于(A)是实正定二次型，所以我们可以大概猜测当(sum_{i=1}^n b_ix_i)取到最值时，有(x^TAx - 1= 0)成立。将其看为约束条件，现在要求(f(x_1,x_2,...,x_n)=sum_{i=1}^n b_ix_i)的最值，可以考虑使用拉格朗日乘数法。

　　　令(g(x_1,x_2,...,x_n,lambda)=sum_{i=1}^n b_ix_i+lambda(sum_{i=1}^nsum_{j=1}^{n}A_{ij}x_ix_j- 1))，对各自变量求偏导可以得出取得最值的条件为

egin{cases}
b_1+lambda(2A_{11}x_1+2A_{12}x_2+...+2A_{1n}x_n)=0\
b_2+lambda(2A_{21}x_1+2A_{22}x_2+...+2A_{2n}x_n)=0\
......\
b_n+lambda(2A_{n1}x_1+2A_{n2}x_2+...+2A_{nn}x_n)=0\
sum_{i=1}^nsum_{j=1}^{n}A_{ij}x_ix_j- 1=0
end{cases}

　　　化简为矩阵形式就是

egin{cases}
B+2lambda Ax=0\
x^TAx=1
end{cases}

　　　而我们要求的答案就是(ans=sum_{i=1}^n b_ix_i=B^Tx=x^TB)

　　　由第一个式子我们可以通过移项得到(2lambda Ax=-B)，左乘(frac{A^{-1}}{2lambda})得出(x=-frac{A^{-1}B}{2lambda})

　　　因此(B^Tx=-frac{1}{2lambda}B^TA^{-1}B=x^TB)，同时也能得到(x^T=-frac{1}{2lambda}B^TA^{-1})

　　　将(x=-frac{A^{-1}B}{2lambda})与(x^T=-frac{1}{2lambda}B^TA^{-1})同时代入式子(x^TAx=1)可得出

$$-frac{1}{2lambda}B^TA^{-1}cdot  Acdot (-frac{A^{-1}B}{2lambda})=1$$

　　　即

$$frac{1}{4lambda ^2}B^TA^{-1}B=1$$

　　　再根据我们之前得到的(ans=B^Tx=-frac{1}{2lambda}B^TA^{-1}B)，我们要输出的(ans^2)就是

$$(-frac{1}{2lambda}B^TA^{-1}B)^2=frac{1}{4lambda ^2}(B^TA^{-1}B)cdot(B^TA^{-1}B)=B^TA^{-1}B$$

　　　套用矩阵求逆的板子即可通过此题

#include<bits/stdc++.h>
using namespace std;
#define N 510
#define LL long long
#define MOD 998244353
LL n,a[N][N],b[N];
LL qow(LL x,LL y){return y?(y&1?x*qow(x,y-1)%MOD:qow(x*x%MOD,y/2)):1;}
int main()
{
    while(~scanf("%lld",&n))
      {
      LL res=0;
      for(LL i=1;i<=n;i++)
        {
        for(LL j=1;j<=n;j++)
          scanf("%lld",&a[i][j]),a[i][n+j]=0;
        a[i][n+i]=1;
        }
      for(LL i=1;i<=n;i++)scanf("%lld",&b[i]);
      for(LL i=1;i<=n;i++)
        {
        LL id=-1;
        for(LL j=i;j<=n;j++)if(a[j][i]){id=j;break;}
        swap(a[i],a[id]);
        LL t=qow(a[i][i],MOD-2);
        for(LL j=i;j<=2ll*n;j++)a[i][j]=a[i][j]*t%MOD;
        for(LL j=i+1;j<=n;j++)
          for(LL k=2ll*n;k>=i;k--)
            a[j][k]=(a[j][k]+MOD-a[i][k]*a[j][i]%MOD)%MOD;
        }
      for(LL i=n;i>=1;i--)
        for(LL j=i-1;j>=1;j--)
          for(LL k=2ll*n;k>=i;k--)
            a[j][k]=(a[j][k]+MOD-a[i][k]*a[j][i]%MOD)%MOD;
      for(LL i=1;i<=n;i++)
        for(LL j=1;j<=n;j++)
          res=(res+b[i]*b[j]%MOD*a[i][n+j])%MOD;
      printf("%lld
",res);
      }
}