Hướng dẫn cho LQDOJ CUP 2022 - Round 5 - LOCALMAX
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.
Authors:
Subtask \(1\) (\(10\%\) số điểm): \(n \cdot m \le 10\), \(k \le 5\).
Tutorial
Ta quay lui để điền vào các ô các giá trị. Sau đó chỉ cần đếm số lượng ô đỉnh.
Độ phức tạp: \(\mathcal{O}(T \cdot k^{n \cdot m} \cdot n \cdot m)\).
Solution
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 15;
int numTest;
int n, m, k;
int a[MAX_N][MAX_N];
int cnt[MAX_N], ok[MAX_N][MAX_N];
int check() {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
ok[i][j] = 1;
}
}
for (int i = 1; i <= n; ++i) {
int mx = -1;
for (int j = 1; j <= m; ++j) {
if (a[i][j] <= mx) {
ok[i][j] = false;
}
mx = max(mx, a[i][j]);
}
mx = -1;
for (int j = m; j >= 1; --j) {
if (a[i][j] <= mx) {
ok[i][j] = false;
}
mx = max(mx, a[i][j]);
}
}
for (int j = 1; j <= m; ++j) {
int mx = -1;
for (int i = 1; i <= n; ++i) {
if (a[i][j] <= mx) {
ok[i][j] = false;
}
mx = max(mx, a[i][j]);
}
mx = -1;
for (int i = n; i >= 1; --i) {
if (a[i][j] <= mx) {
ok[i][j] = false;
}
mx = max(mx, a[i][j]);
}
}
int ans = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
ans += ok[i][j];
}
}
return ans;
}
pair<int, int> get_next(int u, int v) {
if (v < m)
++v;
else {
++u;
v = 1;
}
return make_pair(u, v);
}
void back_track(int u, int v) {
if (u == n + 1 && v == 1) {
++cnt[check()];
return;
}
for (int i = 1; i <= k; ++i) {
a[u][v] = i;
int nxt_u, nxt_v;
tie(nxt_u, nxt_v) = get_next(u, v);
back_track(nxt_u, nxt_v);
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
freopen("LOCALMAX.inp", "r", stdin);
freopen("LOCALMAX.out", "w", stdout);
cin >> numTest;
while (numTest--) {
cin >> n >> m >> k;
memset(cnt, 0, sizeof cnt);
back_track(1, 1);
int res = 0;
for (int i = 0; i <= n * m; ++i) {
res += (i + 1) * cnt[i];
}
cout << res << "\n";
}
return 0;
}
Subtask \(2\) (\(20\%\) số điểm): \(n, m \le 2000\), \(k = 2\).
Tutorial
Vì \(k = 2\) nên các ô đỉnh sẽ có giá trị \(2\), các ô còn lại luôn có giá trị \(1\). Hai ô đỉnh khác nhau phải nằm trên hai hàng khác nhau và hai cột khác nhau.
Giả sử \(n \le m\), ta chỉ có tối đa \(n\) ô đỉnh. Xét cách điền có \(g\) \((g \le n)\) ô đỉnh. Ta cần chọn ra \(g\) hàng. Mỗi cách chọn hàng, ta cần chọn có thứ tự \(g\) cột để ghép tương ứng các hàng. Vậy có \(C^g_n \cdot A^g_n\) cách chọn ra \(g\) ô đỉnh. Các ô cùng hàng hoặc cùng cột những ô được chọn này hiển nhiên phải là \(1\). Tuy nhiên vẫn còn thừa một số ô khác, việc đếm chính xác \(g\) ô đỉnh là rất khó khăn.
Trong ví dụ trên, ta thấy còn thừa \(8\) ô không được chọn. Nếu đếm chính xác \(g\) ô đỉnh, ta không biết phải chọn \(1\) hay \(2\) vào các ô này.
Ta chuyển hướng sang việc tính \(B(g)\): số cách chọn ra ít nhất \(g\) ô đỉnh. Vậy \(B(g) = C^g_n \cdot A^g_n \cdot k^{(n - i) \cdot (m - i)}\).
Ta có công thức bao hàm loại trừ: \(A(g) = B(g) - C^g_{g+1} \cdot A(g + 1) - C^g_{g+2} \cdot A(g+2) - \ldots\).
Độ phức tạp: \(\mathcal{O}(T \cdot n^2)\).
Solution
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 2007;
const int MAX = MAX_N * MAX_N;
const int MOD = 1e9 + 7;
int numTest;
int numRow, numCol, limit;
int fac[MAX_N], inv[MAX_N];
int pw[MAX];
int num[MAX_N];
void selfSub(int &x, int y) {
if ((x -= y) < 0) {
x += MOD;
}
}
void selfAdd(int &x, int y) {
if ((x += y) >= MOD) {
x -= MOD;
}
}
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 C(int k, int n) {
if (k > n) {
return 0;
}
return mul(mul(fac[n], inv[k]), inv[n - k]);
}
int A(int k, int n) {
return mul(fac[n], inv[n - k]);
}
int B(int x) {
return mul(mul(C(x, numRow), A(x, numCol)), pw[(numRow - x) * (numCol - x)]);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
freopen("LOCALMAX.inp", "r", stdin);
freopen("LOCALMAX.out", "w", stdout);
fac[0] = 1;
for (int i = 1; i < MAX_N; ++i) {
fac[i] = mul(fac[i - 1], i);
}
inv[MAX_N - 1] = myPow(fac[MAX_N - 1], MOD - 2);
for (int i = MAX_N - 2; i >= 0; --i) {
inv[i] = mul(inv[i + 1], i + 1);
}
cin >> numTest;
while (numTest--) {
cin >> numRow >> numCol >> limit;
pw[0] = 1;
for (int i = 1; i <= numRow * numCol; ++i) {
pw[i] = mul(pw[i - 1], limit);
}
int res = 0;
for (int i = min(numRow, numCol); i >= 0; --i) {
num[i] = B(i);
for (int j = i + 1; j <= min(numRow, numCol); ++j) {
selfSub(num[i], mul(C(i, j), num[j]));
}
selfAdd(res, mul(i + 1, num[i]));
}
cout << res << '\n';
}
return 0;
}
Subtask \(3\) (\(30\%\) số điểm): \(n, m, k \le 200\).
Tutorial
Vì \(k \le 200\) nên lúc này giá trị các ô cùng hàng hoặc cùng cột với các ô đỉnh cũng rất quan trọng. Trong những bài toán như này, ta nghĩ ngay đến quy hoạch động.
Nhận thấy: nếu ta xáo trộn hai hàng và hai cột của hai ô đỉnh khác nhau, kết quả không thay đổi. Nhờ vậy nếu xét \(g\) ô đỉnh, ta coi như \(g\) ô đấy nằm ở \(g\) ô đầu đường chéo chính, nói cách khác là các vị trí \((1, 1)\), \((2, 2)\), \(\ldots\), \((g, g)\). Việc này giúp ta dễ dàng tưởng tượng cách quy hoạch động hơn.
Ngoài ra ta sẽ đặt các ô đỉnh theo thứ tự giá trị không giảm. Khi đó, ta không cần quan tâm các ô cùng hàng hoặc cùng cột với các ô đỉnh nữa. Bởi lẽ chúng luôn bị giới hạn bởi ô đỉnh đầu tiên ảnh hưởng. Ví dụ:
- các ô \(1\) được điền đầu tiên, sẽ giới hạn giá trị của các ô đỏ.
- Các ô \(2\) được điền thứ hai, sẽ giới hạn giá trị của các ô vàng.
- Các ô \(3\) được điền sau cùng, sẽ giới hạn giá trị của các ô xanh xám.
Gọi \(dp[i][j]\) là số cách chọn ra \(i\) ô đỉnh theo cách trên và ô hiện tại có giá trị là \(j\). Ta sẽ chọn ra \(h\) ô trong \(i\) ô để điền giá trị \(j\). Khi đó số lượng ô cùng hàng hoặc cùng cột với \(h\) ô đỉnh này sẽ là \(h \cdot (n + m - 2 \cdot (i - h)) - h \cdot h - h\) (các bạn tự nháp để ra). Như đã phân tích, giá trị tối đa của các ô này sẽ là \(j - 1\). Vậy ta có công thức:
\(\displaystyle dp[i][j] = \sum_{h=0}^i dp[i-h][j-1] \cdot C^h_i \cdot (j - 1)^{h \cdot (n + m - 2 \cdot (i - h)) - h \cdot h - h}\)
Đến đây ta tính phần bù như subtask 2 là xong. Lưu ý: \(dp\) chỉ xét cách chọn theo đường chéo chính. Không phải toàn bộ số cách (trước khi xáo trộn).
Độ phức tạp: \(\mathcal{O}(T \cdot n^2 \cdot k)\).
Solution
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
const int MAX_N = 205;
const int MAX = MAX_N * MAX_N;
int numTest;
int n, m, k;
int dp[MAX_N][MAX_N];
int f[MAX_N];
int fact[MAX];
int ifact[MAX];
int pw[MAX_N][MAX];
void add(int &a, int b) {
a += b;
if (a < 0) {
a += MOD;
}
if (a >= MOD) {
a -= MOD;
}
}
int prod(int a, int b) {
return 1LL * a * b % MOD;
}
int binpow(int a, int b) {
int c = 1;
for (; b; b >>= 1, a = prod(a, a)) {
if (b & 1) {
c = prod(c, a);
}
}
return c;
}
void build() {
for (int i = 0; i < MAX_N; ++i) {
pw[i][0] = 1;
for (int j = 1; j < MAX; ++j) {
pw[i][j] = prod(pw[i][j - 1], i);
}
}
fact[0] = 1;
for (int i = 1; i < MAX; ++i) {
fact[i] = prod(fact[i - 1], i);
}
ifact[MAX - 1] = binpow(fact[MAX - 1], MOD - 2);
for (int i = MAX - 1; i > 0; --i) {
ifact[i - 1] = prod(ifact[i], i);
}
}
int C(int n, int k) {
if (k < 0 || n < k) {
return 0;
}
return prod(fact[n], prod(ifact[k], ifact[n - k]));
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
freopen("LOCALMAX.inp", "r", stdin);
freopen("LOCALMAX.out", "w", stdout);
build();
cin >> numTest;
while (numTest--) {
cin >> n >> m >> k;
if (n > m) {
swap(n, m);
}
for (int i = 0; i <= k; ++i) {
dp[0][i] = 1;
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= k; ++j) {
dp[i][j] = 0;
for (int h = 0; h <= i; ++h) {
int tmp = dp[i - h][j - 1];
tmp = prod(tmp, C(i, h));
tmp = prod(tmp, pw[j - 1][h * (n + m - 2 * (i - h)) - h * h - h]);
add(dp[i][j], tmp);
}
}
}
int res = 0;
for (int i = n; i >= 0; --i) {
int tmp = dp[i][k];
tmp = prod(tmp, C(n, i));
tmp = prod(tmp, C(m, i));
tmp = prod(tmp, pw[k][(n - i) * (m - i)]);
tmp = prod(tmp, fact[i]);
for (int j = i + 1; j <= n; ++j) {
int cur = prod(f[j], C(j, i));
add(tmp, -cur);
}
f[i] = tmp;
add(res, prod(i + 1, f[i]));
}
cout << res << "\n";
}
return 0;
}
Subtask \(4\) (\(30\%\) số điểm): \(n, m \le 10^6\).
Tutorial
Ta biến đổi:
\(\displaystyle \sum_{g = 0}^{n \cdot m} (g + 1) \cdot A(g) = \displaystyle \sum_{g = 0}^{n \cdot m} A(g) + \sum_{g = 0}^{n \cdot m} g \cdot A(g)\)
Vế trái hiển nhiên bằng \(k^{n \cdot m}\). Ta chỉ cần quan tâm vế phải:
\(\displaystyle \sum_{g = 0}^{n \cdot m} g \cdot A(g) = \displaystyle \sum_{g = 0}^{n \cdot m} A(g) + A(g) + \ldots + A(g)\)
Xét một cách có \(g\) ô đỉnh bất kì. Nó đóng góp vào \(A(g)\) một lần nên đóng góp vào cả biểu thức \(g\) lần. Vậy ta có thể coi là mỗi ô đỉnh trong cách này đóng góp vào đáp án một lần, có \(g\) ô như thế (đáp án không thay đổi, chỉ là paraphrase). Vì mỗi ô chỉ đóng góp vào kết quả khi nó là ô đỉnh nên với mỗi ô trong \(n \cdot m\) ô, ta chỉ cần đếm số lượng bảng nhận nó là ô đỉnh. Ngoài ra các ô có tính tổng quát nên ta có thể tính nhanh hơn. Đáp số:
\(\displaystyle k^{n \cdot m} + \sum_{i = 1}^k n \cdot m \cdot (i - 1)^{n + m - 2} \cdot k^{(n - 1) \cdot (m - 1)}\)
Độ phức tạp: \(\mathcal{O}(T \cdot k)\).
Solution
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
int numTest;
int n, m, k;
int bpow(int a, long long b) {
int c = 1;
for (; b; b >>= 1, a = 1LL * a * a % MOD) {
if (b & 1) {
c = 1LL * c * a % MOD;
}
}
return c;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
freopen("LOCALMAX.inp", "r", stdin);
freopen("LOCALMAX.out", "w", stdout);
cin >> numTest;
while (numTest--) {
cin >> n >> m >> k;
int ans = bpow(k, 1LL * n * m);
for (int i = 1; i <= k; ++i) {
ans += 1LL * n * m % MOD * bpow(i - 1, n + m - 2) % MOD * bpow(k, 1LL * (n - 1) * (m - 1)) % MOD;
ans %= MOD;
}
cout << ans << "\n";
}
return 0;
}
Subtask \(5\) (\(10\%\) số điểm): Không có ràng buộc gì thêm.
Tutorial
Ta có tính chất \(a^p \mod (10^9 + 7) = a^{p \mod (10^9 + 6)} \mod (10^9 + 7)\) nên có thể làm được với \(n\), \(m\) lớn.
Độ phức tạp: \(\mathcal{O}(T \cdot k)\).
Solution
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
int numTest;
string n, m;
int k;
int bpow(int a, int b) {
int c = 1;
for (; b; b >>= 1, a = 1LL * a * a % MOD) {
if (b & 1) {
c = 1LL * c * a % MOD;
}
}
return c;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
freopen("LOCALMAX.inp", "r", stdin);
freopen("LOCALMAX.out", "w", stdout);
cin >> numTest;
while (numTest--) {
cin >> n >> m >> k;
int mod_n = 0, mod_nn = 0;
for (int i = 0; i < n.size(); ++i) {
mod_n = mod_n * 10LL % (MOD - 1) + n[i] - '0';
mod_n %= (MOD - 1);
mod_nn = mod_nn * 10LL % MOD + n[i] - '0';
mod_nn %= MOD;
}
int mod_m = 0, mod_mm = 0;
for (int i = 0; i < m.size(); ++i) {
mod_m = mod_m * 10LL % (MOD - 1) + m[i] - '0';
mod_m %= (MOD - 1);
mod_mm = mod_mm * 10LL % MOD + m[i] - '0';
mod_mm %= MOD;
}
int mod_n1 = (mod_n - 1 + MOD - 1) % (MOD - 1);
int mod_m1 = (mod_m - 1 + MOD - 1) % (MOD - 1);
int mod_sum_n1_n2 = (mod_n1 + mod_m1) % (MOD - 1);
int mod_prod_n_m = 1LL * mod_n * mod_m % (MOD - 1);
int mod_prod_n1_n2 = 1LL * mod_n1 * mod_m1 % (MOD - 1);
int ans = bpow(k, mod_prod_n_m);
for (int i = 1; i <= k; ++i) {
ans += 1LL * mod_nn * mod_mm % MOD * bpow(i - 1, mod_sum_n1_n2) % MOD * bpow(k, mod_prod_n1_n2) % MOD;
ans %= MOD;
}
cout << ans << "\n";
}
return 0;
}
Bình luận