let menu = ["Home", "Algorithms", "CodeHub", "VNOI Statistics"];

Overview

VOI 2011 TREELINE - Hàng cây

solution.md

Với yêu cầu đầu tiên, ta chỉ cần for từ n ngược về để tìm vị trí đầu tiên có a[i]>a[i+1].

Trong yêu cầu thứ 2, kết quả của bài toán chính là số Catalan thứ n+1. Công thức số Catalan:

\[C_n = \frac{1}{n+1}\binom{2n}{n} = \frac{(2n)!}{(n+1)!n!} = \prod_{k=2}^{n} \frac{n+k}{k}\]

Ngoài ra có thể xem bài ORGAN để có một cái nhìn tổng quát hơn về bài này.

Vì đề yêu cầu tính trong module \(10^9\) không phải là số nguyên tố nên ta không thể sử dụng phép nghịch đảo module để tính thương. Trong bài này, ta dùng cách phân tích thành thừa số nguyên tố. Dùng công thức \(C_n = \prod_{k=2}^{n} \frac{n+k}{k}\), ta phân tích thành thừa số nguyên tố mỗi số nguyên trên tử rồi cộng các số mũ lại với nhau, tương tự ta cũng phân tích các số nguyên dưới mẫu.

Vì cần phân tích nhiều số nguyên nên đoạn code trên kết hợp việc phân tích nguyên tố với sàng nguyên tố.

main.cpp
Open in Github • Download 
#include <iostream>
#include <vector>
using namespace std;

#define LL long long

const LL M = 1000000000;

LL pow(LL x, int n) {
    if (n==0) return 1;
    int t = pow(x, n >> 1);
    t = t * t % M;
    if (n & 1) return t * x % M;
    return t;
}

int find(int x, int p) {
    int res = 0;
    while (x % p == 0) res++, x /= p;
    return res;
}

LL catalan(LL n) {
    vector<bool> prime(2*n+1, true);
    vector<int> count(2*n+1, 0);
    for (int i=2; i<=2*n; i++) if (prime[i]) {
        int c = 0;
        for (int j=i; j<=2*n; j+=i) {
            prime[j] = false;
            if (n+2 <= j) c += find(j, i);
            if (j<=n) c -= find(j, i);
        }
        count[i] = c;
    }
    LL res = 1;
    for (int i=1; i<=2*n; i++) {
        res = res * pow(i, count[i]) % M;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int n, t; cin >> n >> t;
    vector<int> h(n);
    for (auto &h: h) cin >> h;
    int res = 2;
    for (int i=n-2; i >= 0; i--) {
        if (h[i] < h[i+1]) res++;
        else break;
    }
    cout << res << '\n' << catalan(n+1);
    return 0;
}
Comments