[NowCoder5666D]Quadratic Form

题意

$\begin{aligned} \max_x &\quad b^Tx\\ {\rm s.t.} &\quad x^TAx-1\le0 \end{aligned}$

求 $(b^Tx)^2\mod 998244353$ .

$A$ 为 $n\times n$ 的对称矩阵， $b,x\in\mathbb{R}^n$
$n\le200,0\le|A_{i,j}|,|b_i|\le10^9$
$\forall x\in\mathbb{R}^n/\ \{\boldsymbol0\},x^TAx>0$
$\det(A)\not\equiv0\pmod{998244353}$

题解——我的博客

设兰格朗日函数 $\mathcal{L}(x,\lambda)=b^Tx+\lambda(x^TAx-1)$ ，根据向量求导法则，有

$\frac{\partial\mathcal{L}}{\partial x}=b+\lambda(A+A^T)x=b+2\lambda Ax$

令 $\displaystyle\frac{\partial\mathcal{L}}{\partial x}=0$ ，可得 $\displaystyle x=-\frac{A^{-1}b}{2\lambda}$ 。由KKT条件： $\lambda(x^TAx-1)=0,\lambda\le0$ 。将 $x$ 带入得

$\begin{aligned} &\lambda[(-\frac{A^{-1}b}{2\lambda})^TA(-\frac{A^{-1}b}{2\lambda})-1]=0\\ \Rightarrow&\qquad b^T(A^{-1})^TAA^{-1}b=4\lambda^2,\quad (A^{-1})^T=A^{-1}\\ \Rightarrow&\qquad \lambda=-\frac12\sqrt{b^TA^{-1}b} \end{aligned}$

故

$b^Tx=b^T(-\frac{A^{-1}b}{2\lambda})=-\frac{b^TA^{-1}b}{\sqrt{b^TA^{-1}b}}=\sqrt{b^TA^{-1}b}$

最终的答案为 $(b^Tx)^2=b^TA^{-1}b$ 。用高斯消元求出 $A$ 的逆再相乘即可。

单组数据时间复杂度 $O(n^3)$