Spoiler Alert

Hint 1

• Vì số quá lớn, việc bignum sẽ TLE đấy 😢 tin tui đi, hướng này không tiếp cận được đâu

Thay vào đó bạn có thể sài Hash và nó sẽ không TLE đâu UwU

Nhưng vấn đề là bạn Hash và xử lí toán học sao là một chuyện QaQ

Hint 2

• Khi bạn sài Hash, xâu kí tự sẽ giảm đi thành giá trị \(x \in [0, modulo)\)

Bạn có thể coi đây là tính \(modulo\) bignum (số lớn \(K\) cho số nhỏ \(modulo\))

Số \(modulo\) nên lớn hơn giá trị \(C_n\) nên ta cũng sài modulo để tính \(C_n\)

Hint 3

• Tính modulo số lớn cho số nhỏ

Với \(base\) là hệ của 2 số, trong trường hợp này là hệ thập phân hay \(base = 10\)

Với \(digit_i\) là từng chữ số trong hệ \(base\) được duyệt \(i = 1 -> n\)

Ta có \(res = (res \times base + digit_i)\) \(mod\) \(m\)

Cẩn thận tràn số

Hint 4

• Trong phép toán modulo chỉ có phép cộng, trừ, nhân chứ không có phép chia

Thay vào đó bạn có thể dùng Modular Inverse với \(\phi(modulo)\)

Gọi \(inverse(a) \equiv a^{-1} \equiv \frac{1}{a}\) \((mod\) \(m)\)

Việc tính toán sẽ trở thành \(C_n = \frac{(2n)!}{(n+1)! \times n!}\) \((mod\) \(m)\)

\(\equiv (2n)! \times inverse(n + 1, m)! \times inverse(n, m)!\) \((mod\) \(m)\)

Hint 5

• Công thức Modular Inverse để tính \(\frac{1}{a} (mod\) \(m)\)

Khi \((a, m)\) là cặp số nguyên tố cùng nhau ta có \(a ^ {\phi(m) - 1} \equiv a ^ {-1} (mod\) \(m)\)

Có \((a, m)\) là cặp số nguyên tố cùng nhau khi \(gcd(a, b) = 1\)

Ta cũng có \(gcd(a, p) = 1\) với \(p\) nguyên tố

Đồng thời ta cũng có \(\phi(p) = p - 1\) với \(p\) nguyên tố

Nên ta có công thức \(a ^ {m - 2} \equiv a ^ {-1}\) \((mod\) \(m)\)

Vậy ta chọn các modulo \(m\) nguyên tố

Hint 6

• Sài Hash cần cẩn thận: \(A = B \Rightarrow f(A) = f(B)\) không phải là mũi tên hai chiều

Tuy nhiên nếu \(f(A) \neq f(B) \Rightarrow A \neq B\) nên sẽ loại ngay trường hợp này

Còn trường hợp còn lại, ta sẽ thử rất nhiều trường hơp \(f(A) ? f(B) \Rightarrow A ? B\) để nó đúng

Hash phụ thuộc vào biến A và số modulo p. Nên ta sẽ kiểm tra nhiều trường hợp \(f(A, p) ? f(B, p)\)

Hint 7

• Bạn cũng có thể tiền xử lí phần giai thừa và nghịch đảo giai thừa

Gọi các mảng sau

\(invs[p][]\) là mảng các số nghịch đảo modulo \(p\). Có \(invs[x] \equiv x ^ {-1}\) \((mod\) \(p)\)

\(fact[p][]\) là mảng giai thừa tự nhiên modulo \(p\). Có \(fact[x] = 1 \times 2 \times ... \times x\) \((mod\) \(p)\)

\(tcaf[p][]\) là mảng giai thừa nghịch đảo modulo \(p\). Có \(tcaf[x] = invs[1] \times invs[2] \times ... \times invs[x]\) \((mod\) \(p)\)

Ta có công thức:

\(invs[p][i] \equiv invs[p][p % i] \times (p - p / i)\) \((mod\) \(p)\)

\(fact[p][i] \equiv fact[p][i - 1] \times i\) \((mod\) \(p)\)

\(tcaf[p][i] \equiv tcaf[p][i - 1] \times invs[i]\) \((mod\) \(p)\)

Từ đó ta tính \(C_n\) \(mod\) \(m\)

\(C_n = \frac{(2n)!}{(n+1)! \times n!}\) \((mod\) \(m)\)

\(\equiv (2n)! \times invs(n + 1, m)! \times invs(n, m)!\) \((mod\) \(m)\)

\(\equiv fact[m][2n] \times tcaf[m][n + 1] \times tcaf[m][n]\) \((mod\) \(m)\)

Hint 8

• Online Solving

Ta cũng có thể không cần lưu mảng string mà cứ nhận từng kí tự là chữ số và thực hiện tính toán

Ta có \(res = (res \times base + digit)\) \(mod\) \(m\)

Cẩn thận tràn số

Reference AC code | \(O(n)\) time + \(O(q)\) \(\times\) \(O(log_{10}K)\) query | \(O(n)\) auxiliary space | Online Solving, Precalculation, Query-problem, Hashing, Modular Inverse, Math, String

vector<int> modulo = {1000000007, 1000000009, 1000000021, 1000000033, 1000000087, 1000000093, 1000000097, 1000000103, 1000000123, 1000000181};

/// Tien xu li
vector<vector<int> > invs, fact, tcaf;
void gen_inv(int lim = LIM)
{
    invs = fact = tcaf = vector<vector<int> >(10, vector<int>(2, 1));
    for (int p = 0; p < 10; ++p)
    {
        int m = modulo[p];
        for (int i = 2; i <=     lim; ++i) invs[p].push_back(mulMOD(invs[p][m % i], (m - m / i), m));
        for (int i = 2; i <= 2 * lim; ++i) fact[p].push_back(mulMOD(fact[p].back(),      i     , m));
        for (int i = 2; i <=     lim; ++i) tcaf[p].push_back(mulMOD(tcaf[p].back(), invs[p][i] , m));
    }
}

/// Cong thuc tinh so Catalan
inline int C(int n, int p) { return 1LL * fact[p][2 * n] * tcaf[p][n + 1] % modulo[p] * tcaf[p][n] % modulo[p]; }

/// Kiem tra neu ki tu hien tai la chu so
inline bool isDigit(char c) { return '0' <= c && c <= '9'; }

/// Xu li truy van
int query()
{
    /// Input dau vao
    int n = readInt();

    /// Loai bo cac ki tu khong phai chu so
    char c;
    while (c = getchar(), !isDigit(c));

    /// Tinh res[i] = K % modulo[i]
    vector<int> res(10, 0);
    do {
        /// Duyet qua tung res[i]
        for (int i = 0; i < 10; ++i)
            res[i] = (10LL * res[i] + (c - '0')) % modulo[i]; /// Tinh toan
    } while (c = getchar(), isDigit(c)); /// Nhan chu so tiep theo

    /// Kiem tra
    for (int i = 0; i < 10; ++i)
        if (C(n, i) != res[i]) /// f(A) # f(B) => A # B
            return cout << "NO\n", 0;

    return cout << "YES\n", 0; /// f(A) = f(B) => co the A = B
}