출제

한사람 한 대의 PC를 지급받고 있는 직원 N인 전원이, 타인의 PC를 사용하는 조합은 몇 가지인가?

사고방식

이것은 사례 수의 완전 순열 (교란 순열이라고도 함)이라고합니다.
N이 2~4까지라면 수동으로 푸는 것이 편하지만, 그 이상의 경우는 점화식을 사용할 필요가 있다.
만약 총당으로 풀려고 하면 매우 난문이 된다.

여기는 고맙게 과거의 위인의 영지에 빠지기로 합니다.
완전 순열의 총수를 구하는 점화식은 이것.


이것을 보면 A1 or A2 가 될 때까지 재귀적으로 호출하면 좋은 것을 알 수 있다.

답변

이상의 내용에 의해 이런 느낌으로 해 보았다.

/* 完全順列の個数(モンモール数) */
long long montmort_number(int n) {

    if (n == 1) {
        return 0;
    }
    else if (n == 2) {
        return 1;
    }
    return (n - 1) * (montmort_number(n - 1) + montmort_number(n - 2));
}

int main() {
    int i, l, N;
    char s[80];

    for (; ~scanf("%s", s);) {
        l = strlen(s);
        for (N = 0, i = 0; i < l ; i++)
            N = (N * 10) + s[i] - '0';

        sprintf(s, "%lld", montmort_number(N));

        puts(s);
    }
    return 0;
}

[結果]
montmort_number(1) => 0
montmort_number(2) => 1
montmort_number(3) => 2
montmort_number(4) => 9
montmort_number(5) => 44
montmort_number(6) => 265
montmort_number(7) => 1854

감상

4명까지라면 수동으로 시도하는 것도 있지만 5명 이후라면 어려울까.
7명이라면 1854/5040거리도 있을까.

소스의 동작은 재귀를 사용하고 있기 때문에 매우 느립니다.
반복의 처리를 사용할 수 있으면 좀 더 빨라진다고 생각한다.