C++에서 행/열에 둘 이상의 항목이 포함되지 않도록 n^2 위치에 항목을 배치하는 방법

이 문제에서는 세로로 n개의 선이 있고 가로로 n개의 선이 있고 이 선 사이에 n2개의 교차점이 있도록 배치되는 정수 n이 주어집니다. 우리의 임무는

행과 열에 하나 이상의 항목이 포함되지 않도록 합니다.

문제를 이해하기 위해 예를 들어보겠습니다.

입력

n=4

출력

24

설명

이 문제를 해결하려면 nC4 항목이 있는 n줄에서 4개의 수평선을 선택해야 합니다. 이제 모든 수평선에는 n개의 수직선이 있으므로 첫 번째 선택된 수평선에 항목을 배치하는 n가지 방법이 있습니다. 그런 다음 n-1개의 가능한 배치가 있는 다음 선택된 수평선으로 이동합니다. 그리고 같은 방식으로 세 번째는 n-2에, 앞으로는 n-3에 배치할 수 있습니다. 따라서 총 와트 수는 ⁿ 이 됩니다. C4*n*(n-1)*(n-2)*(n-3)

알고리즘의 구현을 보여주는 프로그램,

예

#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<<"The number of way is which 4 items can be placed in the intersection of "<<n;
   cout<<" lines vertically and horizotally are "<<placeItems(n);
   return 0;
}

출력

The number of way is which 4 items can be placed in the intersection of 4 lines vertically and horizotally are 24