Chương trình C++ đếm số cách tạo hình 12 cạnh (dodecagon) kích thước d

Cho số d. Có vô hạn gạch vuông và gạch tam giác đều cạnh 1. Hãy đếm số cách tạo hình 12 cạnh đều (dodecagon) cạnh d từ các gạch này. Kết quả lấy modulo 998244353.

Ví dụ

Với d = 1, đầu ra là 1.

Giải thuật

Công thức tổ hợp: kết quả là C(2d-1, d-1) (số cách chọn). Triển khai bằng cách tính tử số b = (2d-1) * (2d-2) * ... * (d+1) và mẫu số c = (d-1)!, kết quả b/c.

Mã C++

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

int solve(int d) {
    int b = ((d << 1) - 1);
    int c = 1;
    for (int i = 2; i < d; i++) {
        b *= (d << 1) - i;
        c *= i;
    }
    return (b / c);
}

int main() {
    int d = 1;
    cout << solve(d) << endl;
}

Đầu vào / Đầu ra

Input: 1
Output: 1