풀이
모든 열쇠를 얻으러면, 열쇠들 사이에 사이클이 생겨야한다.
우리에겐 k개의 폭탄이 있기 때문에, 이 열쇠들을 k개의 집합으로 나눠서 사이클을 만드는 경우의 수를 세면 된다.
n개의 원소를 k개의 원순열로 분할하기 위해, 제1종 스털링 수라는 걸 사용해보자.
s(n, k) = s(n-1, k-1) + (n-1)*s(n-1, k)라는 점화식이 나온다.
gcd로 최대공약수를 구하고, 합으로 나눠주면 끝!
코드
#include <stdio.h>
typedef long long ll;
int n, m, i, j;
ll dp[21][21] = { 1 }, div;
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
int main() {
scanf("%d %d", &n, &m);
for (i = 1; i <= n; i++) for (j = 1; j <= i; j++)
dp[i][j] = dp[i - 1][j - 1] + (i - 1)*dp[i - 1][j];
for (i = 1; i <= n; i++) dp[n][i] += dp[n][i - 1];
div = gcd(dp[n][n], dp[n][m]);
printf("%lld/%lld", dp[n][m]/div, dp[n][n]/div);
return 0;
}
아무말
백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이