โปรแกรม C++ นับจำนวนรูปทรง 12 ด้านที่สร้างได้จากกระเบื้อง

คำอธิบายปัญหา

สมมติว่าเรามีตัวเลข d มีกระเบื้องสี่เหลี่ยมจัตุรัสและกระเบื้องสามเหลี่ยมด้านเท่าจำนวนไม่จำกัด ด้านยาว 1 ต้องการหาว่าสามารถสร้างรูปทรง 12 ด้าน (dodecagon) ที่ด้านยาว d ได้กี่วิธี หากคำตอบใหญ่เกิน ให้คืนค่า mod 998244353

ขั้นตอนการแก้ปัญหา

b := floor(d/2) - 1
c := 1
สำหรับ i := 2 ถึง d-1:
    b := b * floor(d/2)
    c := c * i
คืนค่า (b / c)

ตัวอย่างโค้ด 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;
}

อินพุต

1

เอาต์พุต

1