Số cách đặt vật phẩm vào n^2 vị trí sao cho hàng/cột không chứa hơn một trong C++

Trong bài toán này, chúng ta được cho một số nguyên n sao cho có n đường thẳng dọc và n đường ngang được đặt sao cho có n2 giao điểm giữa các đường này. Nhiệm vụ là tìm tổng số cách để đặt 4 vật phẩm lên các giao điểm này

sao cho không hàng và cột nào chứa hơn một vật phẩm.

Hãy xem ví dụ để hiểu bài toán,

Đầu vào

n=4

Đầu ra

24

Giải thích

Để giải bài toán này, chúng ta sẽ phải chọn 4 đường ngang từ n đường sẽ có vật phẩm, tức là nC4. Bây giờ, mỗi đường ngang có n đường dọc nên, sẽ có n cách đặt vật phẩm trong đường ngang đầu tiên được chọn. Sau đó, chuyển đến đường ngang tiếp theo được chọn nơi sẽ có n-1 vị trí đặt có thể. Và theo cách tương tự, thứ ba có thể đặt trong n-2 và thứ tư trong n-3 cách. Vì vậy, tổng số cách sẽ là ⁿC4*n*(n-1)*(n-2)*(n-3)

Chương trình triển khai thuật toán,

Ví dụ

#include <iostream> using namespace std; long long placeItems(int n) {    return (1LL * (1LL *    ((n) * (n - 1) * (n - 2) * (n - 3)) / (4 * 3 * 2 * 1)) *    ((1LL * (n) * (n - 1) * (n - 2) * (n - 3)))); } int main() {    int n = 4;    cout<<"Số cách đặt 4 vật phẩm tại giao điểm của "<<n;    cout<<" đường dọc và ngang là "<<placeItems(n);    return 0; }

Đầu ra

Số cách đặt 4 vật phẩm tại giao điểm của 4 đường dọc và ngang là 24