적어도 1명 이상이 자기 자신 것을 그대로 가져갈 확률은?(교란순열의 수렴)

13531번: Secret Santa (acmicpc.net)

 

 

n명의 사람이 모자에 이름을 쓰고, 한번 섞은 다음에 다시 가져가는데 적어도 1명 이상이 자기 자신 것을 그대로 가져갈 확률을 구하는 문제

 

https://deepdata.tistory.com/946

자기 것을 다시 갖지 않고 나눠주는 경우의 수 교란순열(완전순열) 배우기

 

1 - n명의 사람이 모두 자기 자신 것을 가져가지 않는 확률 = 적어도 1명 이상이 자기 자신 것을 가져갈 확률

 

따라서 사실상 교란순열을 구하는 것과 동일하다

 

점화식이 an = (n-1)(an-1+an-2)인데, 문제는 n 제한이 $10^{12}$라서.. O(N)으로 하더라도 시간안에 구할 수가 없다...

 

다른 방법이 있나??

 

일단 한번 구해봤는데 특이한 점을 발견했다

 

n이 18부터는 전부 0.6321205588285577...로 수렴한다는 점

 

 

 

 

문제에서 정답과 오차가 최대 $10^{-6}$이내에 있으면 정답처리한다고 함

 

n이 9부터는 0.632120으로 6자리가 전부 동일하므로, n이 8까지는 미리 구한 값을 그대로 출력하고

 

n이 9부터는 0.6321205588285577을 출력하면 정답이다

 

answer = [0,1.0,0.5,0.6666666666666666,0.625,0.6333333333333333,0.6319444444444444,0.6321428571428571,0.6321180555555556]

n = int(input())

if n <= 8:
    
    print(answer[n])

else:
    
    print(0.6321205588285577)

 

 

교란순열의 일반항은 다음과 같이 구해진다

 

 

 

이 문제는 n개의 모자를 섞는 경우의 수가 $n!$이므로, 구하고자 하는 확률은 $1 - \frac{D_{n}}{n!}$

 

이때, $$\frac{D_{n}}{n!} = \sum_{k=0}^{n} \frac{(-1)^{k}}{k!}$$인데, n이 무한대로 가면 $e^{k}$로 수렴한다

 

 

 

따라서, n이 커질수록 정답이 $1-\frac{1}{e} = 0.63212055882$로 수렴한다