Contents
概要
A | B | C | D | E | F | G | H | I | J | |
---|---|---|---|---|---|---|---|---|---|---|
总体 | ✔ | ✔ | ✔ | ? | ✔ | ? | ? | |||
wzgy | ✔ | ? | ||||||||
csz | ✔ | ✔ | ✔ | ? | ||||||
wh | ? |
比赛地址
题目
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;
}