Chương trình đếm số cách đặt cạnh không giao nhau nối tất cả nút trên vòng tròn C++

Mô tả bài toán

Cho n nút đặt trên vòng tròn (n chẵn). Đặt n/2 cạnh nối các cặp nút sao cho mọi nút thuộc đúng một cạnh và các cạnh không cắt nhau. Tính số cách modulo 10^9+7.

Ví dụ: n=4 → 2 cách.

Giải thuật (Số Catalan)

Số cách chính là số Catalan C_{n/2}. Dùng quy hoạch động:

• dp[0]=1, dp[1]=1.
• Với i từ 2 đến n/2:
  • dp[i] = Σ_{j=1}^{i/2} 2 * dp[j-1] * dp[i-j] (nếu i chẵn thì thêm dp[i/2]^2).
  • Mọi phép tính modulo 1e9+7.
• Kết quả dp[n/2].

Ví dụ minh họa (C++)

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

int solve(int n) {
    vector<long long> dp(n/2 + 1);
    dp[0] = 1; dp[1] = 1;
    const int MOD = 1000000007;
    for (int i = 2; i <= n/2; i++) {
        dp[i] = 0;
        for (int j = 1; j <= i/2; j++) {
            dp[i] = (dp[i] + 2 * dp[j-1] * dp[i-j]) % MOD;
        }
        if (i % 2) dp[i] = (dp[i] + dp[(i-1)/2] * dp[(i-1)/2]) % MOD;
    }
    return dp[n/2];
}

int main() {
    int n = 4;
    cout << solve(n);
    return 0;
}

Đầu vào

4

Đầu ra

2