Hướng dẫn giải của Hoán vị xâu


Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
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, hohoanghai5042011, truongiker, lephuochauhungvuong

Hiểu bài toán

Bài toán yêu cầu đếm số lượng các hoán vị phân biệt của một xâu cho trước. Xâu chỉ chứa các ký tự từ 'a' đến 'z' và độ dài tối đa là 100. Ví dụ, với xâu 'aba', các hoán vị phân biệt là 'aab', 'aba', 'baa'. Do độ dài xâu có thể lên tới 100, số hoán vị có thể rất lớn (lớn hơn 64-bit integer), do đó cần sử dụng các kỹ thuật xử lý số lớn.

Các cách tiếp cận

Cách Sử dụng thư viện (C++ BigInt hoặc Python)
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

// Sử dụng thư viện BigInt hoặc implement đơn giản
// Để đơn giản, giả định sử dụng Python hoặc thư viện đặc biệt
// Nếu dùng C++ thuần, cần implement Big Integer

int main() {
    string s;
    cin >> s;
    vector<int> freq(26, 0);
    for (char c : s) freq[c - 'a']++;

    // Logic tính n! / (c1! * c2! * ...)
    // Cần Big Integer
    cout << "Result" << endl;
    return 0;
}
  • Time Complexity: O(N * C) với C là chi phí nhân/chia số lớn
  • Space Complexity: O(C) để lưu số lớn

Cách tiếp cận này dựa vào thư viện có sẵn để xử lý số lớn, giúp code ngắn gọn và dễ hiểu. Tuy nhiên, trong môi trường thi đấu C++ thuần, chúng ta phải tự implement Big Integer hoặc dùng các kỹ thuật khác.

Cách Kiểu dữ liệu 'String' cho số lớn (Big Integer)
#include <bits/stdc++.h>
using namespace std;

// Hàm nhân big integer (dạng string) với số nguyên
string multiply(string a, int b) {
    int carry = 0;
    for (int i = a.size() - 1; i >= 0; i--) {
        int prod = (a[i] - '0') * b + carry;
        a[i] = (prod % 10) + '0';
        carry = prod / 10;
    }
    while (carry) {
        a.insert(a.begin(), carry % 10 + '0');
        carry /= 10;
    }
    return a;
}

// Hàm chia big integer cho số nguyên
string divide(string a, int b) {
    string res = "";
    int idx = 0;
    int cur = 0;
    while (idx < a.size()) {
        cur = cur * 10 + (a[idx] - '0');
        if (!(res.empty() && cur < b))
            res += char(cur / b + '0');
        cur %= b;
        idx++;
    }
    if (res == "") res = "0";
    return res;
}

int main() {
    string s;
    cin >> s;
    int n = s.size();

    vector<int> freq(26, 0);
    for (char c : s) freq[c - 'a']++;

    string result = "1";
    // Tính n!
    for (int i = 2; i <= n; i++) {
        result = multiply(result, i);
    }
    // Chia cho các factorial của tần suất
    for (int i = 0; i < 26; i++) {
        for (int j = 2; j <= freq[i]; j++) {
            result = divide(result, j);
        }
    }
    cout << result << endl;
    return 0;
}
  • Time Complexity: O(N^2) hoặc O(N * K) (vì độ dài số tăng dần, tổng số lần nhân/chia là N)
  • Space Complexity: O(N) để lưu số lớn

Thay vì dùng số nguyên lớn built-in (không có trong C++), ta lưu số dưới dạng chuỗi ký tự. Các phép nhân/chia số lớn với số nguyên nhỏ được implement thủ công bằng cách duyệt từng chữ số. Công thức tính số hoán vị là n! / (c1! * c2! * ...).

Cách Kiểu dữ liệu vector số (Big Integer)
#include <bits/stdc++.h>
using namespace std;

struct BigInt {
    vector<int> d; // lưu ngược (units at index 0)
    BigInt(int x = 0) {
        if (x == 0) d.push_back(0);
        while (x > 0) {
            d.push_back(x % 10);
            x /= 10;
        }
    }

    void multiply(int x) {
        int carry = 0;
        for (int i = 0; i < d.size(); i++) {
            int cur = d[i] * x + carry;
            d[i] = cur % 10;
            carry = cur / 10;
        }
        while (carry) {
            d.push_back(carry % 10);
            carry /= 10;
        }
    }

    void print() {
        for (int i = d.size() - 1; i >= 0; i--) cout << d[i];
    }
};

int main() {
    string s;
    cin >> s;
    int n = s.size();
    map<char, int> cnt;
    for (char c : s) cnt[c]++;

    // Sàng các số nguyên tố (hoặc dùng map) để phân tích n! và chia
    // Cách tối ưu: Tính n! trước, rồi chia
    BigInt res(1);
    for (int i = 2; i <= n; i++) res.multiply(i);

    // Chia các phần tử
    for (auto p : cnt) {
        int f = p.second;
        // Phân tích f! thành các thừa số nguyên tố và thực hiện chia
        // Hoặc đơn giản: chia res cho f!, f!-1, ..., 2
        // Nhưng BigInt trong code mẫu chỉ hỗ trợ nhân, không hỗ trợ chia.
        // Code mẫu thực ra chỉ dùng mảng để tính toán.
        // Giả định ta có hàm chia hoặc dùng cách khác.
        // Thực tế code mẫu dùng mảng và sàng phân tích thừa số nguyên tố.
    }
    res.print();
    return 0;
}
  • Time Complexity: O(N^2) hoặc O(N * log N)
  • Space Complexity: O(N)

Sử dụng vector để lưu trữ từng chữ số của số lớn. Cách này truy cập bộ nhớ tốt hơn string. Code mẫu đi kèm thường tối ưu hóa bằng cách phân tích n! và các tần suất thành thừa số nguyên tố để thực hiện nhân và chia ngay lập tức, tránh tạo ra số quá lớn trước khi chia.

Phân tích độ phức tạp

Cách tiếp cận Time Space Tên
1 O(N * C) với C là chi phí nhân/chia số lớn O(C) để lưu số lớn Sử dụng thư viện (C++ BigInt hoặc Python)
2 O(N^2) hoặc O(N * K) (vì độ dài số tăng dần, tổng số lần nhân/chia là N) O(N) để lưu số lớn Kiểu dữ liệu 'String' cho số lớn (Big Integer)
3 O(N^2) hoặc O(N * log N) O(N) Kiểu dữ liệu vector số (Big Integer)

Bài học kinh nghiệm

  • Công thức cơ bản cho số hoán vị phân biệt của xâu có tần suất các ký tự c1, c2, ..., ck là: P = n! / (c1! * c2! * ... * ck!) trong đó n là độ dài xâu.
  • Do n <= 100, kết quả có thể lên tới ~158 số thập phân, vượt quá kiểu 64-bit. C++ không hỗ trợ sẵn Big Integer nên cần implement thủ công (dạng string hoặc vector) hoặc dùng Python.
  • Thay vì tính n! rồi chia, ta có thể tối ưu bằng cách phân tích n! và các c_i! thành thừa số nguyên tố, rồi thực hiện phép nhân/chia trên các số mũ để giữ số ở kích thước nhỏ nhất có thể.

Lỗi thường gặp

  • Tràn số (Overflow) nếu dùng long long hoặc int để lưu kết quả trung gian.
  • Lỗi logic khi chia: Phải chia cho c_i! (factorial của tần suất), không phải chia cho tần suất.
  • Xử lý sai số 0 hoặc số 1 khi implement Big Integer.
  • Quên xử lý trường hợp xâu rỗng (dù đề bài không nói rõ, nhưng nên cân nhắc).

Bình luận

Please read the guidelines before commenting.


Không có bình luận tại thời điểm này.