문제: https://gall.dcinside.com/mgallery/board/view/?id=github&no=30577

테스트 케이스: https://gall.dcinside.com/mgallery/board/view/?id=github&no=30588




0. 문제 역사



호랑이 전담피던 시절, 큼푸타 배울 때 위와 같은 반복문을 작성해보고 가장 안쪽 반복문이 몇 번 실행되는 지 출력하라는 문제가 있었음


그 때는 3중 반복문이 문제였었지만 4중 5중 6중 ... r중 반복문이라면 가장 안쪽 반복문이 얼마나 실행될 지가 궁금했고 이게 이 문제의 시초가 됨 ㅇㅅㅇ


단지 C 로 하면 overflow 문제가 있으니 파이썬으로 각색함


1. 문제 분석


위 코드에서 최종적 x 값은 가장 안쪽 반복문이 실행되는 횟수와 같다.


1중 반복문이라면 가장 안쪽 반복문이 n번 실행되고


2중 반복문이라면 가장 안쪽 반복문이 n + (n-1) + (n-2) + ... + 1 번 실행되고


3중 반복문부터 쓰기가 어려워지는데 어렴풋이 2중 반복문을 다시 n번 실행하는 형태가 됨을 알 수 있다.


3중 반복문부터 어려워지는 계산을 식으로 쓰면 명쾌하게 쓸 수 있는데



위 처럼 for 문 하나당 합 기호(시그마)가 나오는 형태가 되고


반복문이 r개라면 합 기호가 r번 등장하고 마지막에 1이 나온다.


문제는 이제 r중 반복문을 어떻게 계산하냐이다.



위 식을 계산하는 여러 방법이 있지만 쉬운 방식 중 하나로 고1의 방식을 설명함


고1 때 다들 배운 순열과 조합 중 중복 조합을 떠올려보자


중복 조합 nHr 은 n개 중 r개를 중복을 허락하여 선택하는 가짓수로



r + (n - 1)개의 공을 늘여놓고 n - 1개 공을 막대기로 바꿔 막대기를 기준으로 어떤 공이 몇 번 뽑혔는 지 구별해주어 중복 조합을 계산할 수 있다.


이건 잘 알려진 방식이고 다른 방식으로 중복 조합을 계산할 수 있다.


1 2 3 4 ... n


숫자를 1부터 n까지 일렬로 늘여놓고 서로 다른 r개의 포인터가 1 ~ n 중 하나를 가리킨다고 상상한다. 여러 개의 포인터가 같은 번호를 가리킬 수 있다. 예를 들어 모든 포인터가 전부 1을 가리킬 수 있다.


각 번호를 가리키고 있는 포인터의 개수를 모아서 하나의 상태로 보면 상태의 가짓수가 중복 조합이 된다. 왜냐하면 중복 조합의 정의가 n개 중 r개를 중복을 허용해서 뽑는 가짓수인데 여기서 r개의 포인터를 뽑는 선택이라 보면 말 그대로 중복 조합 정의이기 때문이다.


처음에는 포인터가 전부 1을 가리키고 있다고 생각하고 순차적으로 포인터를 하나씩 오른쪽으로 움직인다.


첫번째 포인터는 1번에서 시작해 n번으로 차례대로 움직인다.


두번째 포인터는 첫번째 포인터와 같은 번호에서 시작해서 n번으로 차례대로 움직인다.


두번째 포인터가 첫번째 포인터보다 왼쪽에 있으면 이미 첫번째 포인터가 거기 있었을 때 카운팅을 했기에 너무 많이 카운팅하게 된다. 그런 경우가 없게끔 두번째 포인터는 최소한 첫번째 포인터에서 시작한다.


세번째 포인터도 같은 방식으로 두번째 포인터와 같은 번호에서 시작해서 n번으로 차례대로 움직인다.


r번째 포인터까지 반복하면 포인터의 위치를 한 번 옮길 때 마다 서로 다른 경우가 나온다.


이런 식으로 카운팅 하면 마지막 r번째 포인터는 r-1번째 포인터에서 시작해서 n번으로 움직이고 i번째 포인터는 i-1번째 포인터에서 시작해서 n번으로 움직인다.


한 번씩 움직일 때 마다 하나씩 카운팅된다. 따라서 총 카운팅 횟수는



이 되고 이 값은 중복 조합과 같다.


한편, 위 식의 좌변이 우리가 구하려는 값이다. 우변을 정리하면




조합이 된다.


이상으로 가장 안쪽 반복문이 몇 번 실행되는 지 구했다.









2. 루카스 정리




위 식의 끔찍한 좌변보다 깔끔한 우변이 낫긴 하지만 우변 역시 n, r의 범위가 10^15 로 너무 커서 계산이 어렵긴 매한가지다.


그래서 문제에선 수가 커지지 않게끔 2000003 으로 나눈 나머지를 구하라고 한다.



참으로 다행인 점은 2000003이 소수라는 점이다. 왜냐하면 조합을 소수로 나눈 나머지를 쉽게 구하는 방법이 있기 때문이다!




https://en.wikipedia.org/wiki/Lucas%27s_theorem


큰 조합의 나머지를 구하는 방식을 루카스 정리라 한다.


루카스 정리를 요약하면 큰 조합은 더 작은 조합들의 곱이고 더 작은 조합들은 m, n의 p진 전개의 계수 구성된다..


이걸 활용하면 10^15 같은 엄청 큰 수의 조합 p로 나눈 나머지를 p = 2_000_003 이하의 수의 조합으로 계산할 수 있다.




증명은 위키에 너무 잘 되어 있어 따라가면 알 수 있다.


마지막에 곱 기호와 합 기호가 뒤바뀐 이유는 X^n의 계수를 계산해야 하는데 n의 p진 전개는 유일하므로 X^n의 계수를 구하려면 n의 p진 전개의 계수끼리 곱해야 하기 때문이다. 또한 왜 m < n이면 0이 나오는 지도 당연하다.



이상으로 엄청 큰 조합을 작은 조합으로 구하는 방법으로 알았다.








3. 조합 계산




조합에서 n, r < p 로 범위가 작아진 건 다행이지만 범위가 작아졌어도 여전히 조합은 수가 너무 커서 계산이 어렵다.




고1 때 배우는 조합 합 성질로 조합을 빠르게 계산할 수 있지만 모든 n과 r을 계산하라면 1/2*p^2 크기를 계산해야 하는데 p가 약 2백만이라 이건 너무 크다.


다른 방법으로 조합의 팩토리얼 정의를 사용하는 방법이다. 잠시 고1 때 배운 항등원과 역원을 다시 떠올려보자



조합 정의를 그대로 쓰고 양변에 (n-r)!r! 을 곱한 후 p는 소수니까 양변에 역원을 곱하면 손쉽게 p로 나눈 나머지를 구할 수 있다.

이 방법은 팩토리얼을 p로 나눈 나머지를 손쉽게 구할 수 있어야 의미가 있다.

참고: 나머지 세상에서 역원이란 3 * 5 = 15를 7로 나눈 나머지가 1인 것 처럼 곱했더니 1이 되는 수를 말한다. 3*5 % 7 = 15 % 7 = 1 이니까 3의 역원은 5, 반대로 5의 역원은 3이 된다. 역원을 쓸 땐 3^-1 = 5 처럼 3 제곱할 때 제곱 대신 -1을 쓴다.

참고: 또한 7 처럼 나누는 수가 소수라면 0 빼고 1 ~ 6 까진 전부 역원이 있다. 위 문제는 p가 소수니까 1 ~ p-1 까지 전부 역원이 있다. 이것을 군(그룹)이라 부른다.


팩토리얼의 재귀적인 관계를 이용해 팩토리얼과 그 역원도 손쉽게 계산할 수 있다.




이 때 n의 역원도 필요한데 나머지 정리를 활용한 재귀적인 관계를 이용하면 손쉽게 계산할 수 있다.


이상으로 팩토리얼과 팩토리얼 역원을 O(p)로 선형 시간안에 계산할 수 있다.







4. 구현




먼저 팩토리얼과 그 역원을 뚝딱뚝딱 계산해준다.





루카스 정리를 활용하여 조합도 계산해준다.




프로그램을 만든다.




실행하면 약 274ms로 250000개 테스트를 통과할 수 있다. ㅇㅅㅇ


끝