[BOJ 7791 // C++] KBTU party

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 7791번 문제인 KBTU party이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/7791 

7791번: KBTU party

남자가 $n$명 있을 때 $k$쌍의 남녀를 뽑는 경우의 수를 $dp[n][k]$라 하자.

 

이 때, $dp[n][k]=dp[n-1][k]+(2n-k)dp[n-1][k-1]$와 같은 점화식이 성립함을 관찰할 수 있다. (n번째 사람이 k개의 쌍을 구성하는 데에 포함이 되었는지 여부를 기준으로 나누어 생각해보자.) 하지만 이 점화식을 이용해 문제를 직접 해결하기에는 문제에서 주어지는 $n$과 $k$의 값의 범위가 너무 크다.

 

다행히 위의 점화식으로 충분히 작은 n과 k값에 대해 값을 뽑아보면 답이 매우 규칙적으로 나오는 것을 관찰할 수 있다. 이를 닫힌 형태의 공식으로 나타낸 뒤 이 값을 계산하는 것으로 문제를 해결하자.

 

2,946,859는 소수이므로 이를 적극적으로 이용해 문제의 답을 계산해내자.

 

아래는 제출한 소스코드이다.

#define MOD 2946859
#include <iostream>
using namespace std;
typedef long long ll;

ll fact[1000001];
ll invfact[1000001];

void init() {
	fact[0] = fact[1] = 1;
	for (ll i = 2; i < 1000001; i++) {
		fact[i] = (fact[i - 1] * i) % MOD;
	}
	invfact[0] = invfact[1] = 1;
	for (ll i = 2; i < 1000001; i++) {
		invfact[i] = MOD - ((MOD / i) * invfact[MOD % i]) % MOD;
	}
	for (int i = 2; i < 1000001; i++) {
		invfact[i] = (invfact[i] * invfact[i - 1]) % MOD;
	}
}

int N, K;
ll ans = 1;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	init();

	cin >> N >> K;

	if (K > N) cout << 0;
	else {
		ans = (fact[N] * ((invfact[N - K] * invfact[K]) % MOD)) % MOD;
		ans = (ans * ans) % MOD;

		cout << (ans * fact[K]) % MOD;
	}
}