Quadratic Form

题意

, 为的正定二次型，为的列向量
求满足求，的最大的值

题解

带有不等式约束条件解极值问题, 使用拉格朗日乘子法
设拉格朗日函数
由KKT条件有

, 若 则 , 因此令
由, 得

则

又

最终有

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX = 2e2 + 10;
const ll mod = 998244353;

ll qpow(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

bool Gauss(ll a[][MAX << 1], int n) {//Gauss求逆
    for (int i = 0, r; i < n; i++) {
        r = i;
        for (int j = i + 1; j < n; j++)
            if (a[j][i] > a[r][i]) r = j;
        if (r != i) swap(a[i], a[r]);
        if (!a[i][i]) return false;//无解

        ll inv = qpow(a[i][i], mod - 2);
        for (int k = 0; k < n; k++) {
            if (k == i) continue;
            ll t = a[k][i] * inv % mod;
            for (int j = i; j < (n << 1); j++)
                a[k][j] = (a[k][j] - t * a[i][j] % mod + mod) % mod;
        }
        for (int j = 0; j < (n << 1); j++) a[i][j] = a[i][j] * inv % mod;
    }
    return true;
}

int n;
ll a[MAX][MAX << 1], b[MAX];

int main() {

    while (~scanf("%d", &n)) {
        memset(a, 0, sizeof(a));
        for (int i = 0; i < n; i++) {
            a[i][i + n] = 1;
            for (int j = 0; j < n; j++)
                scanf("%lld", &a[i][j]);
        }
        Gauss(a, n);
        for (int i = 0; i < n; i++) scanf("%lld", &b[i]);
        ll ans = 0;
        //calc b^T A b
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                ans = (ans + a[i][j + n] * b[i] % mod * b[j] % mod) % mod;
        printf("%lld\n", (ans + mod) % mod);
    }

    return 0;
}