D 凸优化

题意

给出正定的实对称矩阵和向量,向量满足约束：，试求

思路

构造拉格朗日函数，，其中 ，那么

首先对求偏导，得：

得到取最大值时，有：

由拉格朗日对偶性，可得：

再对求偏导，得：

得到：，联立 ，可得，取最大值时：

同样地，取最大值时：，故：

高斯消元求逆即可，时间复杂度:

代码

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
const int N = 205, MOD = 998244353;
using ll = long long;
using result = ll;

result a[N][2 * N];

ll quick_pow(ll a, ll p) {
    ll ret = 1;
    while(p) {
        if (p & 1) ret = ret * a % MOD;
        a = a * a % MOD;
        p >>= 1;
    }
    return ret;
}

ll divm(ll a, ll b) {
    return a * quick_pow(b, MOD - 2) % MOD;
}

int guass(int n) {
    for (int i = 0; i < n; ++i) {
        result pivot = 0;
        int u = 0;
        for (int j = i; j < n; ++j) {
            if (std::fabs(pivot) < std::fabs(a[j][i])) {
                u = j;
                pivot = a[j][i];
            }
        }
        if (pivot == 0) return false;

        std::swap(a[i], a[u]);

        for (int j = 0; j < n; ++j) {
            if (i != j && a[j][i]) {
                result ratio = divm(a[j][i], a[i][i]);
                for (int k = i; k <= 2 * n; ++k) {
                    a[j][k] = (a[j][k] - ratio * a[i][k]) % MOD;
                    a[j][k] += (a[j][k] < 0) * MOD;
                }
            }
        }

    }
    return true;
}

ll invA[N][N];
ll b[N];
ll temp[N];

ll calc(int n) {
    for (int i = 0; i < n; ++i) {
        ll val = 0;
        for (int k = 0; k < n; ++k) {
            val = (val + b[k] * invA[i][k]) % MOD;
        }
        temp[i] = val;
    }
    ll ret = 0;
    for (int i = 0; i < n; ++i) {
        ret = (ret + temp[i] * b[i]) % MOD;
    }
    return ret;
}

int main() {
    int n;
    while(~scanf("%d", &n)){
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                scanf("%lld", &a[i][j]);
            }
        }
        for (int i = 0; i < n; ++i) {
            for (int j = n; j <= 2 * n; ++j) {
                a[i][j] = (j == i + n);
            }
        }
        for (int i = 0; i < n; ++i) {
            scanf("%lld", &b[i]);
        }
        guass(n);
        for (int i = 0; i < n; ++i) {
            for (int j = n; j < 2 * n; ++j) {
                invA[i][j - n] = divm(a[i][j], a[i][i]);
            }
        }

        printf("%lld\n", calc(n));

    }
    return 0;
}