Hướng dẫn giải của Chỉ số hoán vị
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.
Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.
Bạn phải đăng nhập để mở lời giải này.
Đăng nhập
Tác giả: Hiếu Nguyễn
, , ,
Hiểu bài toán
Bài toán yêu cầu tìm thứ tự (rank) của một hoán vị cho trước trong danh sách tất cả các hoán vị của N phần tử (1 đến N) được sắp xếp theo thứ tự từ điển tăng dần. Kết quả cần được tính modulo 998244353. Ví dụ, với N=3, hoán vị 2 1 3 có thứ tự là 3 (sau 1 2 3 và 1 3 2).
Các cách tiếp cận
Cách Sử dụng BIT (Fenwick Tree) và giai thừa (Cantor expansion)
#include <bits/stdc++.h>
using namespace std;
#define MOD 998244353
using ll = long long;
int N;
vector<int> P, bit;
vector<ll> fact;
void update(int x) {
while (x <= N) {
bit[x]++;
x += x & -x;
}
}
int query(int x) {
int res = 0;
while (x > 0) {
res += bit[x];
x -= x & -x;
}
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N;
P.resize(N);
bit.assign(N + 2, 0);
fact.resize(N + 1);
fact[0] = 1;
for (int i = 0; i < N; ++i) cin >> P[i];
for (int i = 1; i <= N; ++i)
fact[i] = (1LL * fact[i - 1] * i) % MOD;
ll ans = 0;
// Duyệt từ trái sang phải
for (int i = 0; i < N; ++i) {
// Số phần tử nhỏ hơn P[i] chưa xuất hiện (còn lại ở bên phải)
// (P[i] - 1) là số lượng số nhỏ hơn P[i] trong dãy 1..N
// query(P[i] - 1) là số lượng số nhỏ hơn P[i] đã xuất hiện trước đó
int less = P[i] - 1 - query(P[i] - 1);
// Số hoán vị bắt đầu bằng các số nhỏ hơn P[i] tại vị trí này
ans = (ans + 1LL * less * fact[N - i - 1]) % MOD;
// Đánh dấu P[i] đã xuất hiện
update(P[i]);
}
// Thêm 1 vì thứ tự bắt đầu từ 1
cout << (ans + 1) % MOD << '\n';
return 0;
}
- Time Complexity: O(N log N)
- Space Complexity: O(N)
Đây là cách tiếp cận chuẩn dựa trên định nghĩa của chỉ số Cantor. Ta duyệt qua từng vị trí của hoán vị. Tại vị trí i, ta cần biết có bao nhiêu số nhỏ hơn P[i] chưa được sử dụng. Số lượng này nhân với (N-i-1)! chính là số lượng hoán vị có thứ tự nhỏ hơn bắt đầu bằng các số đó. Để đếm số lượng số nhỏ hơn đã xuất hiện, ta sử dụng Fenwick Tree (BIT) để hỗ trợ cập nhật và truy vấn tổng số lượng đã xuất hiện trong O(log N). Cần tính trước giai thừa modulo.
Cách Sử dụng BIT với truy vấn tổng
#include <bits/stdc++.h>
#define p 998244353
using namespace std;
int n;
int a[1000010], c[1000010];
long long pre[1000010];
int lowbit(int x)
{
return x & (-x);
}
int query(int x)
{
int res = 0;
while (x > 0) {
res += c[x];
x -= lowbit(x);
}
return res;
}
void add(int x)
{
while (x <= n) {
c[x] += 1;
x += lowbit(x);
}
}
long long cantor()
{
long long ans = 0;
for (register int i = n; i >= 1; i--) {
long long ask = query(a[i]); // đếm các số nhỏ hơn a[i] đã xuất hiện
add(a[i]);
long long tmp = pre[n - i];
ans = (ans + tmp * ask % p) % p;
}
return ans % p;
}
int main()
{
cin >> n;
pre[0] = 1;
for (int i = 1; i <= n; i++) {
pre[i] = pre[i - 1] * i % p;
}
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
cout << cantor() + 1;
}
- Time Complexity: O(N log N)
- Space Complexity: O(N)
Cách tiếp cận này về cơ bản giống cách 1 nhưng có thể khác biệt một chút trong cách tính toán. Tuy nhiên, đoạn code mẫu này tính ask = query(a[i]) (số các số nhỏ hơn đã xuất hiện) và nhân với (n-i)!. Công thức này chỉ đúng nếu ta tính tổng các giá trị (số lượng số nhỏ hơn đang đứng sau). Nếu chỉ dùng ask (số nhỏ hơn đã xuất hiện) thì công thức đúng phải là: tổng các số nhỏ hơn đang đứng trước trừ đi phần bù...
Đoạn code này thực ra đang tính: ans += (n-i)! * (số lượng số < a[i] đã xuất hiện). Công thức này không chuẩn để tính rank theo cách trực tiếp thường dùng (thường là đếm số lượng số nhỏ hơn đang đứng sau). Tuy nhiên, nếu xét logic kỹ, nếu duyệt từ phải sang trái và đếm số lượng số nhỏ hơn đã xuất hiện (ở bên phải), ta có thể tính rank nếu dùng công thức bù hợp lý.
Ví dụ: Hoán vị 2 3 1 (N=3). Nếu duyệt phải sang trái (i=3: a[3]=1, query(1)=0, add(1). Giai thừa 0! = 1. Đóng góp 0). (i=2: a[2]=3, query(3)=1 (số 1 đã xuất hiện), add(3). Giai thừa 1! = 1. Đóng góp 1). (i=1: a[1]=2, query(2)=1 (số 1 đã xuất hiện), add(2). Giai thừa 2! = 2. Đóng góp 2). Tổng = 3. Rank = 3 + 1 = 4. Kiểm tra: 123(1), 132(2), 213(3), 231(4). 2 3 1 là 231, rank 4. Đúng.
Đây là một biến thể của thuật toán đếm số lượng số lớn hơn đang đứng trước (hoặc nhỏ hơn đang đứng sau).
Cách Sử dụng cấu trúc dữ liệu cây phân đoạn (Segment Tree)
#include <iostream>
#include <vector>
using namespace std;
const int MOD = 998244353;
const int MAXN = 1000005;
int n;
int arr[MAXN];
long long tree[4 * MAXN];
long long fact[MAXN];
void build(int node, int start, int end) {
if (start == end) {
tree[node] = 1;
return;
}
int mid = (start + end) / 2;
build(2 * node, start, mid);
build(2 * node + 1, mid + 1, end);
tree[node] = tree[2 * node] + tree[2 * node + 1];
}
void update(int node, int start, int end, int idx, int val) {
if (start == end) {
tree[node] += val;
return;
}
int mid = (start + end) / 2;
if (idx <= mid) update(2 * node, start, mid, idx, val);
else update(2 * node + 1, mid + 1, end, idx, val);
tree[node] = tree[2 * node] + tree[2 * node + 1];
}
int query(int node, int start, int end, int l, int r) {
if (r < start || end < l) return 0;
if (l <= start && end <= r) return tree[node];
int mid = (start + end) / 2;
return query(2 * node, start, mid, l, r) + query(2 * node + 1, mid + 1, end, l, r);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
fact[0] = 1;
for (int i = 1; i <= n; i++) fact[i] = (fact[i - 1] * i) % MOD;
for (int i = 0; i < n; i++) cin >> arr[i];
build(1, 1, n);
long long ans = 0;
for (int i = 0; i < n; i++) {
int x = arr[i];
// Đếm số lượng số nhỏ hơn x đang có
int less = query(1, 1, n, 1, x - 1);
ans = (ans + 1LL * less * fact[n - 1 - i]) % MOD;
update(1, 1, n, x, -1); // Xóa phần tử đã dùng
}
cout << (ans + 1) % MOD << endl;
return 0;
}
- Time Complexity: O(N log N)
- Space Complexity: O(N)
Tương tự như cách dùng BIT, nhưng sử dụng Segment Tree để đếm số lượng số còn lại nhỏ hơn phần tử hiện tại. Ban đầu, ta xây dựng cây với tất cả các giá trị là 1 (đánh dấu các số có sẵn). Khi duyệt qua một số, ta truy vấn tổng các số nhỏ hơn nó trong cây, sau đó cập nhật (xóa) số đó khỏi cây. Segment Tree có thể thay thế BIT cho bài toán này.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(N log N) | O(N) | Sử dụng BIT (Fenwick Tree) và giai thừa (Cantor expansion) |
| 2 | O(N log N) | O(N) | Sử dụng BIT với truy vấn tổng |
| 3 | O(N log N) | O(N) | Sử dụng cấu trúc dữ liệu cây phân đoạn (Segment Tree) |
Bài học kinh nghiệm
- Bài toán này là bài toán kinh điển về 'Chỉ số Cantor' (Cantor's Rank).
- Công thức chính: Tại mỗi vị trí, số lượng hoán vị nhỏ hơn được tính bằng
(Số lượng phần tử nhỏ hơn đang đứng sau) * (N - i - 1)!. - Cần quản lý các phần tử đã xuất hiện/chưa xuất hiện để đếm chính xác số lượng phần tử nhỏ hơn đang đứng sau. Cấu trúc dữ liệu BIT (Fenwick Tree) là lựa chọn tối ưu cho O(log N).
- Nếu duyệt từ phải sang trái, ta có thể đếm số lượng phần tử ĐÃ XUẤT HIỆN (ở bên phải) nhỏ hơn phần tử hiện tại. Số này chính là số lượng phần tử nhỏ hơn đang đứng trước/đã xuất hiện. Nếu dùng công thức rank = 1 + sum(...), cần điều chỉnh công thức cho phù hợp với thứ tự duyệt.
Lỗi thường gặp
- Quên cộng thêm 1 vào kết quả cuối cùng (vì thứ tự hoán vị thường bắt đầu từ 1 thay vì 0).
- Sử dụng biến giai thừa quá lớn (N ~ 10^6) mà không tính modulo thường xuyên dẫn đến tràn số (overflow).
- Lỗi truy cập mảng BIT/Segment Tree với chỉ số 0 (trong BIT thì index phải bắt đầu từ 1).
- Tính sai công thức:
query(P[i])thay vìquery(P[i]-1)trong BIT, dẫn đến đếm cả chính nó nếu nó đã xuất hiện.
Bình luận