Hướng dẫn cho LQDOJ Cup 2023 - Final Round - MathChef
Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Subtask \(1\) \(-\) \(26\%\) số điểm
Tutorial
Với mỗi truy vấn, duyệt và tính tích mọi ô nằm trong tam giác vuông cân.
Độ phức tạp: \(O(q \cdot n^2)\).
Solution
C++
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9+7;
int mul(long long x, int y) {
return x * y % MOD;
}
int myPow(int a, int n) {
int res = 1;
for (; n; n>>=1, a=mul(a, a)) {
if (n & 1) res = mul(res, a);
}
return res;
}
int inv(int x) {
return myPow(x, MOD-2);
}
struct Query {
int x1, y1, x2, y2, x3, y3;
};
const int N = 1007;
const int Q = 2e5+7;
int numRow, numCol, a[N][N];
int numQue;
Query que[Q];
namespace sub1 {
void solve() {
for (int i = 0; i < numQue; ++i) {
int x1 = que[i].x1, y1 = que[i].y1;
int x2 = que[i].x2, y2 = que[i].y2;
int x3 = que[i].x3, y3 = que[i].y3;
int minX = min({x1, x2, x3});
int minY = min({y1, y2, y3});
int maxX = max({x1, x2, x3});
int maxY = max({y1, y2, y3});
int sX = x1 ^ x2 ^ x3;
int sY = y1 ^ y2 ^ y3 ^ minY ^ maxY;
int dX = sX == maxX ? -1 : 1;
int dY = sY == maxY ? -1 : 1;
int res = 1;
int x = sX, y = sY;
for (int _ = 0; _ < maxX - minX + 1; ++_) {
for (int j = sY; j != y + dY; j += dY) {
res = mul(res, a[x][j]);
}
x += dX;
y += dY;
}
cout << res << '\n';
}
}
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
freopen("mathchef.inp", "r", stdin);
freopen("mathchef.out", "w", stdout);
cin >> numRow >> numCol;
for (int i = 1; i <= numRow; ++i) {
for (int j = 1; j <= numCol; ++j) {
cin >> a[i][j];
}
}
cin >> numQue;
for (int i = 0; i < numQue; ++i) {
cin >> que[i].x1 >> que[i].y1 >> que[i].x2 >> que[i].y2 >> que[i].x3 >> que[i].y3;
}
sub1::solve();
return 0;
}
Subtask \(2\) \(-\) \(43\%\) số điểm
Tutorial
Ta sẽ tính trước tích tiền tố của từng cột, gọi \(p_{i,j}\) là tích tiền tố của cột \(j\) từ hàng \(1\) đến hàng \(i\), khi đó \(p_{i,j} = (a_{1,j} \cdot a_{2,j} \cdot \ldots \cdot a_{i,j}) \mod (10^9+7)\).
Để lấy được tích từ ô \(a_{i,j}\) đến ô \(a_{k,j}\) \((i \leq k)\), ta có công thức \(p_{k,j} \div p_{i-1,j}\), nhưng vì kết quả có chia lấy dư cho \(10^9 + 7\) nên ta phải tính nghịch đảo của \(p_{i-1,j}\) trước. Để tính nghịch đảo của \(p_{i-1,j}\), ta có thể dùng định lý Fermat nhỏ với công thức là \(inv_{i-1,j} = p_{i-1,j}^{10^9 + 5} \mod (10^9+7)\). Nhưng nếu làm vậy thì độ phức tạp sẽ là \(O(n^2 \cdot \log (10^9 + 5))\).
Cách tối ưu là ta sẽ tính mảng \(p\) trước với độ phức tạp \(O(n^2)\), sau đó với mỗi cột \(j\), đầu tiên ta tính \(inv_{n, j} = p_{n, j}^{10^9+5} \mod (10^9+7)\), tiếp theo tính \(inv_{n-1, j} = inv_{n, j} * a_{n, j} \mod (10^9+7), \ inv_{n-2, j} = inv_{n-1, j} * a_{n-1, j} \mod (10^9+7), \ \ldots\) Cứ như vậy ta sẽ tính được mảng \(inv\) với độ phức tạp \(O(n^2)\).
Với mỗi truy vấn, duyệt từng cột của tam giác cân và tính tích của các ô trong cột nằm trong tam giác vuông cân đó.
Độ phức tạp: \(O(n^2 + q \cdot n)\).
Solution
C++
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9+7;
int mul(long long x, int y) {
return x * y % MOD;
}
int myPow(int a, int n) {
int res = 1;
for (; n; n>>=1, a=mul(a, a)) {
if (n & 1) res = mul(res, a);
}
return res;
}
void exEuclid(int a, int b, int &x, int &y) {
if (b == 0) {
x = 1;
y = 0;
return;
}
int x0, y0;
exEuclid(b, a % b, x0, y0);
x = y0;
y = x0 - (a / b) * y0;
}
int inv(int x) {
return myPow(x, MOD-2);
}
int fast_inv(int a) {
int x, y;
exEuclid(a, MOD, x, y);
return (x % MOD + MOD) % MOD;
}
struct Query {
int x1, y1, x2, y2, x3, y3;
};
const int N = 1007;
const int Q = 2e5+7;
int numRow, numCol, a[N][N];
int numQue;
Query que[Q];
namespace sub2 {
int pref[N][N];
int invPref[N][N];
void prepare() {
for (int i = 1; i <= numRow; ++i) {
pref[i][0] = 1;
}
for (int i = 1; i <= numRow; ++i) {
for (int j = 1; j <= numCol; ++j) {
pref[i][j] = mul(pref[i][j-1], a[i][j]);
}
}
for (int i = 1; i <= numRow; ++i) {
invPref[i][numCol] = fast_inv(pref[i][numCol]);
for (int j = numCol-1; j >= 0; --j) {
invPref[i][j] = mul(invPref[i][j+1], a[i][j+1]);
}
}
}
int get(int x, int y1, int y2) {
return mul(pref[x][y2], invPref[x][y1-1]);
}
void solve() {
prepare();
for (int i = 0; i < numQue; ++i) {
int x1 = que[i].x1, y1 = que[i].y1;
int x2 = que[i].x2, y2 = que[i].y2;
int x3 = que[i].x3, y3 = que[i].y3;
int minX = min({x1, x2, x3});
int minY = min({y1, y2, y3});
int maxX = max({x1, x2, x3});
int maxY = max({y1, y2, y3});
int sX = x1 ^ x2 ^ x3;
int sY = y1 ^ y2 ^ y3 ^ minY ^ maxY;
int dX = sX == maxX ? -1 : 1;
int dY = sY == maxY ? -1 : 1;
int res = 1;
int x = sX, y = sY;
for (int _ = 0; _ < maxX - minX + 1; ++_) {
if (sY == minY) {
res = mul(res, get(x, minY, y));
} else {
res = mul(res, get(x, y, maxY));
}
x += dX;
y += dY;
}
cout << res << '\n';
}
}
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
freopen("mathchef.inp", "r", stdin);
freopen("mathchef.out", "w", stdout);
cin >> numRow >> numCol;
for (int i = 1; i <= numRow; ++i) {
for (int j = 1; j <= numCol; ++j) {
cin >> a[i][j];
}
}
cin >> numQue;
for (int i = 0; i < numQue; ++i) {
cin >> que[i].x1 >> que[i].y1 >> que[i].x2 >> que[i].y2 >> que[i].x3 >> que[i].y3;
}
sub2::solve();
return 0;
}
Subtask \(3\) \(-\) \(31\%\) số điểm
Tutorial
Đối với các tam giác có cạnh huyền cùng phương với đường chéo chính (đường chéo có phương từ trái trên đến phải dưới), thay vì tính tích các cột, ta sẽ tính tích các đường chéo. Với mỗi đường chéo (theo phương của đường chéo chính), ta tính tích tiền tố theo hướng từ trái trên đến phải dưới, tức là \(p_{i,j} = p_{i-1,j-1} \cdot a_{i,j} \mod (10^9+7)\).
Khi đó ta có thể trả lời từng truy vấn tương tự như cách ở Subtask 2, nhưng độ phức tạp sẽ là \(O(q \cdot n)\). Nhận thấy rằng ta có thể:
- Tính tích từ \(p_{i, j}\) đến \(p_{i, k}\) \((j \leq k)\) bằng cách tính trước tích tiền tố \(pr_{i,j} = pr_{i,j-1} \cdot p_{i,k} \mod (10^9+7)\).
- Tính tích từ \(p_{i, j}\) đến \(p_{k, j}\) \((i \leq k)\) bằng cách tính tích tiền tố \(pc_{i,j} = pc_{i-1,j} \cdot p_{i,k} \mod (10^9+7)\).
- Tính được giá trị nghịch đảo của \(pr_{i,j}\) và \(pc_{i,j}\).
Khi đó ta có thể trả lời mỗi truy vấn trong \(O(1)\).
Các tam giác có cạnh huyền cùng phương với đường chéo phụ được xử lý tương tự như trên, nhưng ta phải tính tích tiền tố theo hướng từ phải trên đến trái dưới.
Độ phức tạp \(O(n^2 + q)\).
Solution
C++
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9+7;
int mul(long long x, int y) {
return x * y % MOD;
}
int myPow(int a, int n) {
int res = 1;
for (; n; n>>=1, a=mul(a, a)) {
if (n & 1) res = mul(res, a);
}
return res;
}
void exEuclid(int a, int b, int &x, int &y) {
if (b == 0) {
x = 1;
y = 0;
return;
}
int x0, y0;
exEuclid(b, a % b, x0, y0);
x = y0;
y = x0 - (a / b) * y0;
}
int inv(int x) {
return myPow(x, MOD-2);
}
int fast_inv(int a) {
int x, y;
exEuclid(a, MOD, x, y);
return (x % MOD + MOD) % MOD;
}
struct Query {
int x1, y1, x2, y2, x3, y3;
};
const int N = 1007;
const int Q = 2e5+7;
int numRow, numCol, a[N][N];
int numQue;
Query que[Q];
namespace sub3 {
int mDiag[N][N], cDiag[N][N];
int mHori[N][N], mVert[N][N];
int cHori[N][N], cVert[N][N];
int mHoriInv[N][N], mVertInv[N][N];
int cHoriInv[N][N], cVertInv[N][N];
void prepare() {
// Diagonal
for (int i = 0; i <= numRow; ++i) {
a[i][0] = a[i][numCol+1] = 1;
mDiag[i][0] = mDiag[i][numCol+1] = 1;
cDiag[i][0] = cDiag[i][numCol+1] = 1;
}
for (int i = 0; i <= numCol+1; ++i) {
a[0][i] = 1;
mDiag[0][i] = 1;
cDiag[0][i] = 1;
}
for (int i = 1; i <= numRow; ++i) {
for (int j = 1; j <= numCol+1; ++j) {
mDiag[i][j] = mul(mDiag[i-1][j-1], a[i][j]);
}
}
for (int i = 1; i <= numRow; ++i) {
for (int j = numCol; j >= 0; --j) {
cDiag[i][j] = mul(cDiag[i-1][j+1], a[i][j]);
}
}
// Horizontal
for (int i = 0; i <= numRow; ++i) {
mHori[i][0] = 1;
cHori[i][0] = 1;
}
for (int i = 0; i <= numRow; ++i) {
for (int j = 1; j <= numCol+1; ++j) {
mHori[i][j] = mul(mHori[i][j-1], mDiag[i][j]);
cHori[i][j] = mul(cHori[i][j-1], cDiag[i][j]);
}
}
for (int i = 0; i <= numRow; ++i) {
mHoriInv[i][numCol+1] = fast_inv(mHori[i][numCol+1]);
cHoriInv[i][numCol+1] = fast_inv(cHori[i][numCol+1]);
for (int j = numCol; j >= 0; --j) {
mHoriInv[i][j] = mul(mHoriInv[i][j+1], mDiag[i][j+1]);
cHoriInv[i][j] = mul(cHoriInv[i][j+1], cDiag[i][j+1]);
}
}
// Vertical
for (int i = 0; i <= numCol+1; ++i) {
mVert[0][i] = 1;
cVert[0][i] = 1;
}
for (int i = 1; i <= numRow; ++i) {
for (int j = 0; j <= numCol+1; ++j) {
mVert[i][j] = mul(mVert[i-1][j], mDiag[i][j]);
cVert[i][j] = mul(cVert[i-1][j], cDiag[i][j]);
}
}
for (int j = 0; j <= numCol+1; ++j) {
mVertInv[numRow][j] = fast_inv(mVert[numRow][j]);
cVertInv[numRow][j] = fast_inv(cVert[numRow][j]);
}
for (int i = numRow-1; i >= 0; --i) {
for (int j = 0; j <= numCol+1; ++j) {
mVertInv[i][j] = mul(mVertInv[i+1][j], mDiag[i+1][j]);
cVertInv[i][j] = mul(cVertInv[i+1][j], cDiag[i+1][j]);
}
}
}
inline int getMHor(int x, int y1, int y2) {
if (y1 == 0) return mHori[x][y2];
return mul(mHori[x][y2], mHoriInv[x][y1-1]);
}
inline int getCHor(int x, int y1, int y2) {
if (y1 == 0) return cHori[x][y2];
return mul(cHori[x][y2], cHoriInv[x][y1-1]);
}
inline int getMVer(int x1, int x2, int y) {
if (x1 == 0) return mVert[x2][y];
return mul(mVert[x2][y], mVertInv[x1-1][y]);
}
inline int getCVer(int x1, int x2, int y) {
if (x1 == 0) return cVert[x2][y];
return mul(cVert[x2][y], cVertInv[x1-1][y]);
}
inline int getMHorInv(int x, int y1, int y2) {
if (y1 == 0) return mHoriInv[x][y2];
return mul(mHoriInv[x][y2], mHori[x][y1-1]);
}
inline int getCHorInv(int x, int y1, int y2) {
if (y1 == 0) return cHoriInv[x][y2];
return mul(cHoriInv[x][y2], cHori[x][y1-1]);
}
inline int getMVerInv(int x1, int x2, int y) {
if (x1 == 0) return mVertInv[x2][y];
return mul(mVertInv[x2][y], mVert[x1-1][y]);
}
inline int getCVerInv(int x1, int x2, int y) {
if (x1 == 0) return cVertInv[x2][y];
return mul(cVertInv[x2][y], cVert[x1-1][y]);
}
void solve() {
prepare();
for (int i = 0; i < numQue; ++i) {
int x1 = que[i].x1, y1 = que[i].y1;
int x2 = que[i].x2, y2 = que[i].y2;
int x3 = que[i].x3, y3 = que[i].y3;
int minX = min({x1, x2, x3});
int minY = min({y1, y2, y3});
int maxX = max({x1, x2, x3});
int maxY = max({y1, y2, y3});
int x = x1 ^ x2 ^ x3 ^ minX ^ maxX;
int y = y1 ^ y2 ^ y3 ^ minY ^ maxY;
int res = 1;
if (x == minX && y == minY) {
res = mul(getCVer(minX, maxX, y), getCHorInv(x-1, minY+1, maxY+1));
} else if (x == minX && y == maxY) {
res = mul(getMVer(minX, maxX, y), getMHorInv(x-1, minY-1, maxY-1));
} else if (x == maxX && y == minY) {
res = mul(getMHor(x, minY, maxY), getMVerInv(minX-1, maxX-1, y-1));
} else if (x == maxX && y == maxY) {
res = mul(getCHor(x, minY, maxY), getCVerInv(minX-1, maxX-1, y+1));
} else {
assert(false);
}
cout << res << '\n';
}
}
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
freopen("mathchef.inp", "r", stdin);
freopen("mathchef.out", "w", stdout);
cin >> numRow >> numCol;
for (int i = 1; i <= numRow; ++i) {
for (int j = 1; j <= numCol; ++j) {
cin >> a[i][j];
}
}
cin >> numQue;
for (int i = 0; i < numQue; ++i) {
cin >> que[i].x1 >> que[i].y1 >> que[i].x2 >> que[i].y2 >> que[i].x3 >> que[i].y3;
}
sub3::solve();
return 0;
}
Bình luận