1413번: 박스 안의 열쇠

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


$O(n^2+lgs)$

n개 수가 m개 이하의 사이클을 이룰 확률을 구하면 된다.
제 1종 스털링 수 = 사이클 만들어질 경우의 수인데 n개 수로 m개의 사이클을 만드는 경우의 수를 c(n,m)이라 하면
c(0,0)=1 c(n,m)=c(n-1,m-1)+c(n-1,m)*(n-1)이 성립한다.

답은 c(n,1) + ... + c(n,m) / c(n,1) + ... + c(n,n) 이다.

#include<cstdio>
typedef long long lint;
lint gcd(lint x, lint y) { return y ? gcd(y, x%y) : x; }
int n, m;
lint dp[21][21], d;
int main() {
    scanf("%d %d", &n, &m);
    dp[0][0] = 1;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= i; j++) dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j] * (i - 1);
    for (int i = 1; i <= n; i++) dp[n][i] += dp[n][i - 1];
    d = gcd(dp[n][m], dp[n][n]);
    printf("%lld/%lld", dp[n][m] / d, dp[n][n] / d);
    return 0;
}