2020牛客暑期多校训练营(第一场)

Contents

概要

A B C D E F G H I J
总体 ? ? ?
wzgy ?
csz ?
wh ?

比赛地址

2020牛客暑期多校训练营(第一场)

题目

A

B

C

D. Quadratic Form

题目大意:

给定一实正定矩阵 A,求当

\sum_{i=1}^n\sum_{j=1}^{n}A_{ij}x_ix_j\le 1

x^TAx \le 1 时,\sum_{i=1}^n b_ix_i 的最大值

解题思路:

由于 A 是实正定二次型,所以 x^TAx=0 当且仅当 x=0,此时答案也为 0,显然不可取。因此有 x^TAx – 1= 0 成立。将其看为约束条件,现在要求 g(x_1,x_2,…,x_n)=\sum_{i=1}^n b_ix_i 的最值,可以考虑使用拉格朗日乘数法。

令:

f(x_1,x_2,…,x_n,\lambda)=\sum_{i=1}^n b_ix_i+\lambda(\sum_{i=1}^n\sum_{j=1}^{n}A_{ij}x_ix_j- 1)

对各自变量求偏导可得:

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

化简为矩阵形式:

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

由第一个式子可得:

x=-\frac{A^{-1}B}{2\lambda},\ \ \ \ x^T=-\frac{B^TA^{-1}}{2\lambda}

带入第二个式子:

B^TA^{-1}B=4\lambda ^2

我们要求的答案是

\begin{aligned}
ans&=\left(\sum_{i=1}^n b_ix_i\right)^2=\left(B^Tx\right)^2\cr
&=\frac{\left(B^TA^{-1}B\right)^2}{4\lambda ^2}=B^TA^{-1}B
\end{aligned}

用矩阵求逆的板子即可。

AC代码:

#include <bits/stdc++.h>
using namespace std;
const int P = 998244353;

int ksm(int a, int b) {
    int ret = 1;
    for (; b; b >>= 1, a = 1LL * a * a % P) {
        if (b & 1) {
            ret = 1LL * ret * a % P;
        }
    }
    return ret;
}
int ni(int a) {
    return ksm(a, P - 2);
}

struct Matrix {
    int n, m;
    vector< vector<int> > a;
    void clear() {
        vector<int> tmp(m + 1);
        a.resize(0);
        for (int i = 0; i <= n; i++) {
            a.push_back(tmp);
        }
    }
    Matrix(int _n, int _m) : n(_n), m(_m) {
        clear();
    }
    Matrix(int _n) : n(_n), m(_n) {
        clear();
    }
    Matrix() {}

    Matrix operator * (const Matrix &b) {
        assert(m == b.n);
        Matrix ans(n, b.m);
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= b.m; j++) {
                long long tmp = 0;
                for(int k = 1; k <= m; k++) {
                    tmp += 1LL * a[i][k] * b.a[k][j] % P;
                }
                ans.a[i][j] = tmp % P;
            }
        }
        return ans;
    }

    void Gauss() {
    int i = 1, j = 1, r;
    while (i <= n && j <= m) {
        r = i;
        for (int k = i; k <= n; k++) {
            if (a[k][j]) {
                r = k; break;
            }
        }
        if (a[r][j]) {
            if (r != i) swap(a[i], a[r]);
            for (int k = j, t = ni(a[i][j]); k <= m; k++) {
                a[i][k] = 1LL * a[i][k] * t % P;
            }
            for (int k = 1; k <= n; k++) {
                if (k != i && a[k][j]) {
                    for (int l = j, t = a[k][j]; l <= m; l++) {
                        (a[k][l] += P - 1LL * t * a[i][l] % P) %= P;
                    }
                }
            }
            i++;
        }
        j++;
    }
}
};

Matrix inv(Matrix A) {
    int n = A.n, m = A.m;
    assert(n == m);
    A.m = A.n + A.n;
    for (int i = 1; i <= n; i++) {
        A.a[i].resize(2 * n + 1);
        A.a[i][n + i] = 1;
    }
    A.Gauss();
    Matrix ret;
    ret.n = ret.m = n; ret.clear();
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            ret.a[i][j] = A.a[i][j + n];
        }
    }
    return ret;
}

int main(int argc, const char * argv[]) {
    int n; 
    while (~scanf("%d", &n)) {
        Matrix a(n), b(1, n), c(n, 1);
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                scanf("%d", &a.a[i][j]);
                ((a.a[i][j] %= P) += P) %= P;
            }
        }
        for (int i = 1; i <= n; i++) {
            scanf("%d", &b.a[1][i]);
            ((b.a[1][i] %= P) += P) %= P;
            c.a[i][1] = b.a[1][i];
        }
        Matrix ans = (b * inv(a)) * c;
        printf("%d\n", ans.a[1][1]);
    }
    return 0;
}

E

F

G

H

I

J

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇