Hiểu bài toán

Bài toán yêu cầu tính kết quả của một biểu thức đặc biệt liên quan đến số đường đi. Dựa trên các giải pháp được cung cấp, bài toán giải quyết bài toán tính giá trị của một công thức combinatorics là một biến thể của số Catalan hoặc một biểu thức có dạng nhân và chia các số nguyên tố. Cụ thể, các giải pháp thực hiện tính toán giá trị của biểu thức: (2(n-1))! / ( (n-1)! * n! ) hoặc tương tự. Ví dụ, với n=3, (22)! / (2! * 3!) = 4! / (2 * 6) = 24/12 = 2. Tuy nhiên, logic trong các code cho thấy phép tính là nhân dãy (n-1), (n), (n+1)... và chia cho các số từ 1 đến (n-1). Cụ thể, giải pháp HPNdeptra thực hiện tính toán C(n-1, 2*(n-1)) hoặc tương tự bằng cách nhân các số từ (n) đến (2n-2) và chia cho (n-1)!.

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

Cách Quản lý số lớn dạng vector

#include <bits/stdc++.h>
using namespace std;
int n;
int main()
{
    freopen("DUONGDI.INP","r",stdin);
    freopen("DUONGDI.OUT","w",stdout);
    cin>>n;
    vector<int>a(1,1);
    for(int i=1;i<=n-1;i++)
    {
        int m=n-1+i,c=0;
        for(int &d:a)
        {
            long long v=1LL*d*m+c;
            d=v%10;
            c=v/10;
        }
        while(c)
        {
            a.push_back(c%10);
            c/=10;
        }
        int d1=i,r=0;
        for(int j=a.size()-1;j>=0;j--)
        {
            int v=r*10+a[j];
            a[j]=v/d1;
            r=v%d1;
        }
        while(a.size()>1&&a.back()==0)
            a.pop_back();
    }
    for(int i=a.size()-1;i>=0;i--)
        cout<<a[i];
}

• Time Complexity: O(n * K) (K là số lượng chữ số)
• Space Complexity: O(K)

Giải pháp này sử dụng một vector các số nguyên để lưu trữ một số lớn, mỗi phần tử của vector đại diện cho một chữ số (từ 0 đến 9). Số được lưu theo thứ tự ngược (units at index 0). Trong mỗi bước lặp từ 1 đến n-1:

1. Nhân: Số lớn 'a' được nhân với một số nguyên 'm' (bằng n-1+i). Phép nhân được thực hiện digit-by-digit với carry.
2. Chia: Số lớn 'a' vừa nhân được chia cho một số nguyên 'd1' (bằng i). Phép chia được thực hiện digit-by-digit từ trái sang phải (từ chữ số cao nhất).
3. Dọn dẹp: Loại bỏ các số 0 thừa ở cuối (high-order zeros). Cuối cùng, in ra số. Phương pháp này kiểm soát tốt bộ nhớ và tốc độ so với việc sử dụng string vì thao tác với số nguyên trực tiếp.

Cách Quản lý số lớn dạng string

#include <bits/stdc++.h>
using namespace std;

string multiply(string num, int x) {
    int carry = 0;
    string res = "";
    for (int i = num.size() - 1; i >= 0; i--) {
        int prod = (num[i] - '0') * x + carry;
        res.push_back(char(prod % 10 + '0'));
        carry = prod / 10;
    }
    while (carry) {
        res.push_back(char(carry % 10 + '0'));
        carry /= 10;
    }
    reverse(res.begin(), res.end());
    return res;
}

string divide(string num, int x) {
    string res = "";
    int rem = 0;
    for (int i = 0; i < num.size(); i++) {
        int cur = rem * 10 + (num[i] - '0');
        res.push_back(char(cur / x + '0'));
        rem = cur % x;
    }
    int pos = 0;
    while (pos + 1 < res.size() && res[pos] == '0') pos++;
    return res.substr(pos);
}

int main() {
    // Code xử lý file và vòng lặp tương tự
    // ... Logic nhân và chia với string ...
}

• Time Complexity: O(n * K)
• Space Complexity: O(K)

Giải pháp này sử dụng chuỗi ký tự (string) để biểu diễn số lớn. Các hàm multiply và divide được viết để xử lý phép nhân và chia số lớn với số nguyên.

• Nhân: Duyệt chuỗi từ phải sang trái, nhân từng ký tự với số nguyên, cộng với carry.
• Chia: Duyệt chuỗi từ trái sang phải, thực hiện phép chia thực tế. Cách này logic rõ ràng, dễ hiểu nhưng thường tốn kém hơn một chút về mặt hiệu năng do thao tác với chuỗi ký tự (string manipulation) và việc đảo ngược chuỗi sau mỗi lần nhân.

Cách Xử lý trực tiếp số lớn (Digit-by-digit)

#include <bits/stdc++.h>
using namespace std;

string m ( string a , int b ) {
    int d = 0 ;
    for ( int i = a . size ( ) - 1 ; i >= 0 ; i -- ) {
        int s = ( a [ i ] - '0' ) * b + d ;
        a [ i ] = s % 10 + '0' ;
        d = s / 10 ;
    }
    while ( d ) {
        a . insert ( a . begin ( ) , d % 10 + '0' ) ;
        d /= 10 ;
    }
    while ( a . size ( ) > 1 && a [ 0 ] == '0' ) a . erase ( a . begin ( ) ) ;
    return a ;
}

string d ( string a , int b ) {
    string r ;
    long long g = 0 ;
    for ( char h : a ) {
        g = g * 10 + h - '0' ;
        r . push_back ( g / b + '0' ) ;
        g %= b ;
    }
    int p = 0 ;
    while ( p + 1 < r . size ( ) && r [ p ] == '0' ) p ++ ;
    return r . substr ( p ) ;
}

int main ( ) {
    // ... Code chính ...
}

• Time Complexity: O(n * K)
• Space Complexity: O(K)

Đây là biến thể của phương pháp dùng string, nhưng tối ưu hơn một chút về mặt cú pháp. Thay vì tạo chuỗi mới trong hàm nhân, nó sửa đổi trực tiếp chuỗi hiện tại (trừ trường hợp chèn vào đầu). Phương pháp chia vẫn sử dụng phép chia thực tế từng ký tự. Logic thuật toán cốt lõi vẫn là một vòng lặp từ 1 đến n-1, thực hiện nhân (với n-1+i) và chia (với i) để tính toán giá trị cuối cùng.

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

Bài học kinh nghiệm

• Bài toán có thể được giải quyết bằng cách tính toán biểu thức combinatorics sử dụng các thao tác số lớn (Big Integer).
• Thay vì tính giai thừa trực tiếp (dễ导致 tràn số), ta nên chia nhỏ phép tính thành các bước nhân và chia xen kẽ để duy trì kết quả ở kích thước vừa phải.
• Việc lưu trữ số lớn dạng vector (mỗi phần tử là một chữ số) thường hiệu năng tốt hơn so với string do truy cập trực tiếp và tránh overhead của class string.

Lỗi thường gặp

• Quên xử lý số 0 ở đầu (leading zeros) sau khi thực hiện phép chia, dẫn đến kết quả in ra sai hoặc lỗi logic.
• Sử dụng biến lưu trữ carry hoặc remainder quá nhỏ (ví dụ dùng int thay vì long long) có thể gây tràn số khi nhân các số lớn.
• Lỗi truy cập mảng: Khi xóa phần tử cuối cùng (pop_back) nhưng không kiểm tra xem vector có rỗng hay không.