Bài toán này yêu cầu chúng ta tìm số lượng hoán vị của các số từ 1 đến n sao cho có chính xác K số i (1 < i < n) thỏa mãn điều kiện a_{i-1} < a_i và a_i > a_{i+1}. Một số a_i thỏa mãn điều kiện này được gọi là một "điểm cực đại cục bộ" hay "đỉnh" của hoán vị. Kết quả cần được tính theo modulo 998244353.
Để giải quyết bài toán này, chúng ta sử dụng Quy hoạch động (DP) bằng cách xây dựng hoán vị từng bước, thêm các số từ 1 đến n theo thứ tự tăng dần. Khi thêm số i (là số lớn nhất trong các số đã được thêm vào), nó sẽ luôn lớn hơn các phần tử kề nó. Điều này giúp đơn giản hóa việc xác định xem i có tạo thành một đỉnh mới hay không.
Định nghĩa trạng thái DP
Chúng ta định nghĩa dp[i][j] là số lượng hoán vị của các số từ 1 đến i mà có chính xác j đỉnh.
Các trường hợp cơ sở
- Với i=1: Hoán vị chỉ có [1]. Không có đỉnh nào (vì điều kiện đỉnh là 1 < i < n). Vậy dp[1][0] = 1.
- Với i=2: Các hoán vị là [1,2] và [2,1]. Cả hai đều không có đỉnh (vì điều kiện đỉnh là 1 < i < n và n=2). Vậy dp[2][0] = 2.
Công thức chuyển trạng thái
Để tính dp[i][j], chúng ta xem xét cách chèn số i vào một hoán vị của 1, ..., i-1 đã có j_{prev} đỉnh. Có i vị trí có thể để chèn i (bao gồm hai đầu và i-2 vị trí giữa các phần tử).
Khi chèn i (số lớn nhất) vào một hoán vị của i-1 phần tử có j_{prev} đỉnh:
Số lượng đỉnh không đổi (j_{prev} \to j_{prev}): Có 2 \cdot j_{prev} + 2 vị trí mà khi chèn i vào, số lượng đỉnh vẫn giữ nguyên là j_{prev}. Các vị trí này bao gồm:
- Hai vị trí ở hai đầu của hoán vị. i ở đây không thể là đỉnh vì nó chỉ có một phần tử kề.
- Các vị trí bên cạnh các đỉnh hiện có, nơi i được chèn vào và có thể thay thế một đỉnh cũ, hoặc không tạo ra đỉnh mới.
Góp phần vào dp[i][j_{prev}] là dp[i-1][j_{prev}] \times (2 \cdot j_{prev} + 2).
Số lượng đỉnh tăng thêm 1 (j_{prev} \to j_{prev}+1): Có i - (2 \cdot j_{prev} + 2) vị trí mà khi chèn i vào, số lượng đỉnh tăng lên thành j_{prev}+1. Đây là các vị trí còn lại không thuộc trường hợp trên. Khi i được chèn vào giữa hai số a_x và a_y (ví dụ: ...a_x, i, a_y...), do i là số lớn nhất, nó sẽ tự động trở thành một đỉnh (a_x < i > a_y). Nếu vị trí đó không làm mất đi một đỉnh cũ, nó sẽ tạo ra một đỉnh mới.
Góp phần vào dp[i][j_{prev}+1] là dp[i-1][j_{prev}] \times (i - (2 \cdot j_{prev} + 2)).
Tổng hợp lại, công thức chuyển trạng thái cho dp[i][j] là:
dp[i][j] = (dp[i-1][j] * (2LL * j + 2)) % MOD; // Từ j đỉnh lên j đỉnh
if (j > 0) {
dp[i][j] = (dp[i][j] + dp[i-1][j-1] * (i - 2LL * j)) % MOD; // Từ j-1 đỉnh lên j đỉnh
}
Mã nguồn minh họa
#include <iostream>
#include <vector>
#include <algorithm>
const int MAX_N_PERM = 2005;
const int MOD_VAL_1 = 998244353;
long long perm_dp[MAX_N_PERM][MAX_N_PERM]; // perm_dp[i][j]: số hoán vị của 1..i có j đỉnh
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
int n_val, k_val;
std::cin >> n_val >> k_val;
// Khởi tạo các trường hợp cơ sở
perm_dp[1][0] = 1; // Hoán vị [1] có 0 đỉnh
perm_dp[2][0] = 2; // Hoán vị [1,2] và [2,1] đều có 0 đỉnh
// Tính toán DP
for (int i = 3; i <= n_val; ++i) {
for (int j = 0; j <= std::min(i / 2, k_val); ++j) {
// Cập nhật số hoán vị với j đỉnh từ trạng thái có j đỉnh trước đó
perm_dp[i][j] = (perm_dp[i][j] + perm_dp[i-1][j] * (2LL * j + 2)) % MOD_VAL_1;
// Cập nhật số hoán vị với j đỉnh từ trạng thái có j-1 đỉnh trước đó
if (j > 0) {
perm_dp[i][j] = (perm_dp[i][j] + perm_dp[i-1][j-1] * (i - 2LL * j)) % MOD_VAL_1;
}
}
}
std::cout <>> perm_dp[n_val][k_val] << std::endl;
return 0;
}
Đường đi thay đổi hướng của Kangaroo
Một chú Kangaroo đang thực hiện một cuộc hành trình trong một khu vườn có n bụi cây được đánh số từ 1 đến n theo một hàng. Kangaroo bắt đầu từ bụi cây s, đi qua mỗi bụi cây đúng một lần, và kết thúc tại bụi cây t. Rõ ràng, Kangaroo sẽ thực hiện n-1 bước nhảy.
Để tránh bị phát hiện, Kangaroo phải tuân thủ một quy tắc nghiêm ngặt: hướng của mỗi bước nhảy phải ngược với hướng của bước nhảy trước đó. Cụ thể, nếu Kangaroo đang ở current\_bush, vừa nhảy từ previous\_bush đến current\_bush, và sẽ nhảy đến next\_bush:
- Nếu previous\_bush < current\_bush (nhảy lên), thì next\_bush phải nhỏ hơn current\_bush (nhảy xuống).
- Nếu current\_bush < previous\_bush (nhảy xuống), thì next\_bush phải lớn hơn current\_bush (nhảy lên).
Yêu cầu là tính số lượng đường đi khác nhau từ s đến t theo modulo 10^9 + 7. Hai đường đi được coi là khác nhau nếu thứ tự các bụi cây được ghé thăm khác nhau.
Bài toán này yêu cầu đếm số lượng hoán vị có tính chất "lên-xuống" hoặc "xuống-lên" xen kẽ, với điểm bắt đầu s và điểm kết thúc t cố định. Chúng ta sẽ sử dụng Quy hoạch động bằng cách chèn các số từ 1 đến n theo thứ tự tăng dần.
Định nghĩa trạng thái DP
Chúng ta định nghĩa kangaroo_dp[i][j] là số cách để hình thành j chuỗi xen kẽ không giao nhau bằng cách sử dụng các số từ 1 đến i. Các chuỗi này tuân thủ quy tắc thay đổi hướng. Việc xử lý s và t đặc biệt để đảm bảo chúng là điểm bắt đầu và kết thúc của đường đi cuối cùng.
Trường hợp cơ sở
- Với i=1: Số 1 tự nó tạo thành một chuỗi duy nhất. Vậy kangaroo_dp[1][1] = 1.
Công thức chuyển trạng thái
Để tính kangaroo_dp[i][j], chúng ta xem xét cách chèn số i (số lớn nhất hiện tại) vào các chuỗi đã được hình thành từ 1, ..., i-1.
Trường hợp 1: Số i không phải là s hoặc t
Nếu i không phải là điểm bắt đầu hay kết thúc của đường đi cuối cùng, nó có thể được chèn theo hai cách:
Ghép hai chuỗi lại với nhau: Nếu từ trạng thái kangaroo_dp[i-1][j+1] (có j+1 chuỗi), chúng ta chèn i vào một trong j khoảng trống giữa các chuỗi. Điều này sẽ ghép hai chuỗi lại thành một, làm giảm tổng số chuỗi từ j+1 xuống j. kangaroo_dp[i][j] = (kangaroo_dp[i][j] + kangaroo_dp[i-1][j+1] \times j) % MOD;
Mở rộng hoặc tạo mới một chuỗi: Nếu từ trạng thái kangaroo_dp[i-1][j-1] (có j-1 chuỗi), chúng ta chèn i vào một trong các đầu của chuỗi hiện có, hoặc tạo một chuỗi mới. Số lượng "đầu trống" khả dụng cho việc này là j - (i > s) - (i > t). Ở đây, (i > s) là 1 nếu s đã được đặt (tức là s < i), và 0 nếu chưa. Tương tự cho t. Nếu s hoặc t đã được đặt, chúng đã chiếm giữ một "đầu" và không thể được mở rộng bởi i để trở thành điểm bên trong. kangaroo_dp[i][j] = (kangaroo_dp[i][j] + kangaroo_dp[i-1][j-1] \times (j - (i > s) - (i > t))) % MOD;
Trường hợp 2: Số i là s hoặc t
Nếu i là s hoặc t, nó phải luôn là một điểm cuối của một chuỗi. Nó không thể được sử dụng để ghép hai chuỗi (nếu không nó sẽ không phải là điểm cuối).
Từ trạng thái kangaroo_dp[i-1][j-1] (có j-1 chuỗi), i được đặt như một đầu mới của một chuỗi (tạo thành j chuỗi). kangaroo_dp[i][j] = (kangaroo_dp[i][j] + kangaroo_dp[i-1][j-1]) % MOD;
Từ trạng thái kangaroo_dp[i-1][j] (có j chuỗi), i được đặt như một đầu của một chuỗi hiện có (giữ nguyên j chuỗi). kangaroo_dp[i][j] = (kangaroo_dp[i][j] + kangaroo_dp[i-1][j]) % MOD;
Kết quả cuối cùng
Sau khi điền xong bảng DP, đáp án chính là kangaroo_dp[n][1], vì chúng ta cần một đường đi duy nhất (tức là một chuỗi) từ s đến t.
Mã nguồn minh họa
#include <iostream>
#include <vector>
#include <algorithm>
const int MAX_BUSHES = 2005;
const int MOD_VAL_2 = 1e9 + 7;
long long kangaroo_dp[MAX_BUSHES][MAX_BUSHES]; // kangaroo_dp[i][j]: số cách hình thành j chuỗi xen kẽ dùng 1..i
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
int num_bushes, start_node, end_node;
std::cin >> num_bushes >> start_node >> end_node;
// Khởi tạo trường hợp cơ sở
kangaroo_dp[1][1] = 1; // Số 1 tạo thành 1 chuỗi
// Tính toán DP
for (int i = 2; i <= num_bushes; ++i) {
for (int j = 1; j <= i; ++j) {
if (i != start_node && i != end_node) {
// Trường hợp 1: i không phải s hoặc t
// Ghép 2 chuỗi (từ j+1 chuỗi thành j chuỗi)
kangaroo_dp[i][j] = (kangaroo_dp[i][j] + kangaroo_dp[i-1][j+1] * j) % MOD_VAL_2;
// Mở rộng hoặc tạo mới (từ j-1 chuỗi thành j chuỗi)
kangaroo_dp[i][j] = (kangaroo_dp[i][j] + kangaroo_dp[i-1][j-1] * (j - (i > start_node) - (i > end_node))) % MOD_VAL_2;
} else {
// Trường hợp 2: i là s hoặc t
// i được đặt ở một đầu của chuỗi (từ j-1 chuỗi thành j chuỗi)
kangaroo_dp[i][j] = (kangaroo_dp[i][j] + kangaroo_dp[i-1][j-1]) % MOD_VAL_2;
// i mở rộng một chuỗi (từ j chuỗi thành j chuỗi)
kangaroo_dp[i][j] = (kangaroo_dp[i][j] + kangaroo_dp[i-1][j]) % MOD_VAL_2;
}
}
}
std::cout <>> kangaroo_dp[num_bushes][1] << std::endl; // Kết quả là 1 chuỗi hoàn chỉnh
return 0;
}
Hoán vị với tổng Max kề cận giới hạn K
Bài toán này yêu cầu chúng ta tìm số lượng hoán vị của các số từ 1 đến n sao cho tổng của giá trị lớn nhất giữa hai số kề nhau (\sum_{k=1}^{n-1} \max(a_k, a_{k+1})) không vượt quá K. Kết quả cần được tính theo modulo 998244353.
Đây là một bài toán Quy hoạch động phức tạp hơn do phải theo dõi tổng max của các cặp kề nhau. Chúng ta sẽ tiếp cận bằng cách xây dựng hoán vị bằng cách chèn các số từ 1 đến n theo thứ tự tăng dần. Khi chèn số i, nó sẽ là số lớn nhất trong các số đã có. Điều này đơn giản hóa việc tính \max(X, i) thành i.
Định nghĩa trạng thái DP
Chúng ta định nghĩa sum_max_dp[i][j][current_total_sum] là số lượng cách để tạo ra một cấu trúc hoán vị sử dụng các số từ 1 đến i, sao cho:
- i: Số lượng phần tử đã được đặt (từ 1 đến i).
- j: Số lượng "điểm nối tiềm năng" (các khoảng trống bên trong) trong cấu trúc hoán vị. Một điểm nối tiềm năng là một vị trí mà ở đó có thể chèn một số để hợp nhất hai đoạn hoặc tách một đoạn. Khi j=0, hoán vị là một chuỗi liên tục duy nhất.
- current_total_sum: Tổng \sum \max(a_x, a_{x+1}) đã được tính cho các cặp kề nhau được "đóng" (tức là đã nằm bên trong một đoạn liên tục).
Trường hợp cơ sở
- Với i=1: Hoán vị chỉ có [1]. Không có điểm nối tiềm năng nào (j=0), và tổng max hiện tại là 0. Vậy sum_max_dp[1][0][0] = 1.
Công thức chuyển trạng thái
Để tính sum_max_dp[i][j_{new}][new_sum], chúng ta xem xét cách chèn số i (là số lớn nhất hiện tại) vào một cấu trúc được hình thành từ 1..i-1 với j_{prev} điểm nối tiềm năng và prev_sum. Có i vị trí có thể chèn i.
Chèn i vào một trong hai đầu của chuỗi hiện có:
Giả sử ta chèn i vào vị trí i, X, ... hoặc ..., X, i.
Trường hợp 1a: Tạo một điểm nối tiềm năng mới, tổng không đổi. Số điểm nối tiềm năng tăng lên j_{prev}+1, tổng current\_total\_sum không đổi. Điều này xảy ra khi i được chèn vào một trong hai đầu, tạo ra một "điểm uốn" mới nhưng không làm thay đổi tổng các cặp kề nhau đã tính (do cặp (i,X) chỉ có một phần tử kề). Có 2 cách để thực hiện. sum_max_dp[i][j_{prev}+1][prev_sum] = (sum_max_dp[i][j_{prev}+1][prev_sum] + sum_max_dp[i-1][j_{prev}][prev_sum] \times 2) % MOD;
Trường hợp 1b: Giữ nguyên số điểm nối tiềm năng, tổng tăng i. Số điểm nối tiềm năng giữ nguyên j_{prev}, tổng current\_total\_sum tăng thêm i. Điều này xảy ra khi i được chèn vào một trong hai đầu, tạo thành một cặp (X, i) hoặc (i, X). Vì i là số lớn nhất, \max(X, i) = i. Tổng tăng thêm i. sum_max_dp[i][j_{prev}][prev_sum + i] = (sum_max_dp[i][j_{prev}][prev_sum + i] + sum_max_dp[i-1][j_{prev}][prev_sum] \times 2) % MOD;
Chèn i vào bên trong chuỗi, nếu có j_{prev} > 0 điểm nối tiềm năng:
Giả sử ta chèn i vào vị trí ... X, i, Y ....
Trường hợp 2a: Giữ nguyên số điểm nối tiềm năng, tổng tăng i. Số điểm nối tiềm năng giữ nguyên j_{prev}, tổng current\_total\_sum tăng thêm i. Điều này xảy ra khi i được chèn cạnh một điểm nối tiềm năng (mở rộng một đoạn). Nó tạo ra một cặp (X, i) hoặc (i, Y), thêm i vào tổng. Có j_{prev} \times 2 cách (mỗi điểm nối có 2 phía). sum_max_dp[i][j_{prev}][prev_sum + i] = (sum_max_dp[i][j_{prev}][prev_sum + i] + sum_max_dp[i-1][j_{prev}][prev_sum] \times j_{prev} \times 2) % MOD;
Trường hợp 2b: Tăng số điểm nối tiềm năng lên 1, tổng không đổi. Số điểm nối tiềm năng tăng lên j_{prev}+1, tổng current\_total\_sum không đổi. Điều này xảy ra khi i được chèn vào một khoảng trống bên trong, tách nó thành hai. Điều này tạo ra một điểm nối tiềm năng mới. Tổng max không thay đổi ngay lập tức. Có j_{prev} cách. sum_max_dp[i][j_{prev}+1][prev_sum] = (sum_max_dp[i][j_{prev}+1][prev_sum] + sum_max_dp[i-1][j_{prev}][prev_sum] \times j_{prev}) % MOD;
Trường hợp 2c: Giảm số điểm nối tiềm năng xuống 1, tổng tăng 2i. Số điểm nối tiềm năng giảm xuống j_{prev}-1, tổng current\_total\_sum tăng thêm 2i. Điều này xảy ra khi i được chèn giữa hai đoạn liên tục, hợp nhất chúng lại (ví dụ từ ...X và Y... thành ...X, i, Y...). Vị trí i này "đóng" hai cặp (X,i) và (i,Y). Vì i là lớn nhất, nó đóng góp 2i vào tổng (giả định \max(X,Y) chưa được tính vào tổng trước đó). Có j_{prev} cách. sum_max_dp[i][j_{prev}-1][prev_sum + 2*i] = (sum_max_dp[i][j_{prev}-1][prev_sum + 2*i] + sum_max_dp[i-1][j_{prev}][prev_sum] \times j_{prev}) % MOD;
Kết quả cuối cùng
Sau khi điền xong bảng DP, đáp án là tổng của tất cả sum_max_dp[n][0][current_total_sum] cho mọi current_total_sum từ 0 đến K. Điều kiện j=0 đảm bảo rằng tất cả các đoạn đã được hợp nhất thành một hoán vị liên tục duy nhất.
Mã nguồn minh họa
#include <iostream>
#include <vector>
#include <algorithm>
const int MAX_ELEMENTS = 55;
const int MAX_ALLOWED_SUM = MAX_ELEMENTS * MAX_ELEMENTS; // Max K is N^2, e.g., 50*50 = 2500
const int MOD_VAL_3 = 998244353;
long long sum_max_dp[MAX_ELEMENTS][MAX_ELEMENTS][MAX_ALLOWED_SUM + 5]; // sum_max_dp[i][j][k]
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
int n_elements, k_limit;
std::cin >> n_elements >> k_limit;
// Khởi tạo trường hợp cơ sở: 1 số, 0 điểm nối tiềm năng, tổng 0
sum_max_dp[1][0][0] = 1;
// Tính toán DP
for (int i = 2; i <= n_elements; ++i) { // Duyệt qua số lượng phần tử đã dùng (1 đến i)
for (int j = 0; j <= i - 1; ++j) { // Duyệt qua số điểm nối tiềm năng
for (int current_k = 0; current_k <= k_limit; ++current_k) { // Duyệt qua tổng max hiện tại
if (!sum_max_dp[i-1][j][current_k]) continue;
// Trường hợp 1a: Chèn i vào 2 đầu, tăng j (điểm nối tiềm năng) thêm 1
if (j + 1 <= n_elements - 1) { // j+1 không vượt quá số khoảng trống tối đa
sum_max_dp[i][j+1][current_k] = (sum_max_dp[i][j+1][current_k] + sum_max_dp[i-1][j][current_k] * 2) % MOD_VAL_3;
}
// Trường hợp 1b: Chèn i vào 2 đầu, giữ j, tổng tăng i
if (current_k + i <= k_limit) {
sum_max_dp[i][j][current_k + i] = (sum_max_dp[i][j][current_k + i] + sum_max_dp[i-1][j][current_k] * 2) % MOD_VAL_3;
}
if (j > 0) { // Nếu có điểm nối tiềm năng bên trong
// Trường hợp 2a: Chèn i cạnh điểm nối, giữ j, tổng tăng i
if (current_k + i <= k_limit) {
sum_max_dp[i][j][current_k + i] = (sum_max_dp[i][j][current_k + i] + sum_max_dp[i-1][j][current_k] * j * 2) % MOD_VAL_3;
}
// Trường hợp 2b: Chèn i vào điểm nối, tăng j thêm 1, tổng không đổi
if (j + 1 <= n_elements - 1) {
sum_max_dp[i][j+1][current_k] = (sum_max_dp[i][j+1][current_k] + sum_max_dp[i-1][j][current_k] * j) % MOD_VAL_3;
}
// Trường hợp 2c: Chèn i giữa 2 đoạn, giảm j đi 1, tổng tăng 2*i
if (current_k + 2 * i <= k_limit) {
sum_max_dp[i][j-1][current_k + 2 * i] = (sum_max_dp[i][j-1][current_k + 2 * i] + sum_max_dp[i-1][j][current_k] * j) % MOD_VAL_3;
}
}
}
}
}
long long final_answer = 0;
// Tổng hợp kết quả: khi tất cả N số đã được đặt và 0 điểm nối tiềm năng (1 đoạn hoàn chỉnh)
for (int k_sum = 0; k_sum <= k_limit; ++k_sum) {
final_answer = (final_answer + sum_max_dp[n_elements][0][k_sum]) % MOD_VAL_3;
}
std::cout <>> final_answer << std::endl;
return 0;
}