[Python] 백준 26331 - Gold Rush

문제

After learning about the gold rush in school, your friends have decided to have a gold mining tournament. This one-of-a-kind tournament will be the largest of its kind!

For the tournament, everyone will all line up in a row. Every pair of consecutive people will then face off in a "round" of the tournament. Assuming there are 7 people in the tournament, the first round would look something like this when pairing off: (1, 2) (3, 4) (5, 6) (7).

Notice that when there are an odd number of people in a round, the last person automatically advances to the next round. The remaining players in that round play a best-of-k format where k is an odd number of games. The first person to win ceiling(k/2) games advances to the next round, the other player is eliminated from the tournament, and no more games are played between those players.

For example, let's say players 2, 3, 5, and 7 advance from the first round above. The following round then pairs off in order and the match ups look like this: (2, 3) (5, 7).

The rounds continue in this fashion until a single player remains, the tournament winner!

You would like to know, for a given tournament layout, how many ways the tournament records can play out. Two tournament records are considered different if one of the following conditions is met:

1. The number of games played by a player in the tournament is different.
2. The outcome of the i-th game played by a player is different.

Given the number of players in a tournament and its format (as in best-of-k), determine the number of possible win-loss records.

입력

The input begins with a single positive integer, t, representing the number of tournaments to evaluate. Each of the next t lines contains two integers, n (1 ≤ n ≤ 10^17) and k (1 ≤ k ≤ 10^17), representing the number of players and the best-of-k format, respectively.

출력

For each tournament, output the number of possible win-loss records. As this number may be quite large, output the result modulo 1,000,003.

---

풀이

(이번 문제는 내가 처음으로 블로그를 써보는 것 같다. 인터넷에 아무리 찾아봐도 안나온다)

(애초에 정답자가 나 포함 7명밖에 없는 문제라....)

 

일단 문제를 대충 요약해보자면 다음과 같다.

 

N명의 사람들이 토너먼트제로 게임을 한다. 이때, 각 게임은 K판 ceil(K/2)선승제이다(K는 홀수). 이때, 토너먼트 경기의 결과로 나올 수 있는 모든 경우의 수를 모듈로 1,000,003에 대해 구하시오.

 

조합론 문제임을 쉽게 알 수 있다.

 

N명의 사람들이 토너먼트 게임을 할 때 이루어지는 게임의 수는 N-1번이라는 사실이 널리 알려져있으므로, 각 게임에서 나올 수 있는 경우의 수를 N-1승하면 될 것이다.

 

그렇가면 각 게임에서 나올 수 있는 경우의 수는 얼마일까?

 

예를 들어 K=7이라고 해보자. 최소한 4판을 이겨야 하므로, 4번째에서 이기는 경우의 수, 5번째에서 이기는 경우의 수, 6번째에서 이기는 경우의 수, 7번째에서 이기는 경우의 수를 더하면 될 것이다.

 

이는 3C0, 4C1, 5C2, 6C3의 합과 같다. 

아래 그림에서 쉽게 알 수 있다.

발로 그린 것 같다

 

하키스틱 정리에 의해 구하는 값은 3C0 + 4C1 + 5C2 + 6C3 = 7C3이 된다.

그런데, 이길 수 있는 사람의 경우의 수가 2명이므로 최종적으로는 2*(7C3)이 각 게임에서 나올 수 있는 경우의 수일것이다.

몇 개의 K값만 더해보면 다음과 같이 식을 세울 수 있음을 알 수 있다.

 

2*(K C K//2)

 

그러면 2*comb(K, K//2)를 구해야 하는데, 이는 지난번에 떡파이어 문제에서도 쓴 뤼카의 정리를 이용하도록 하자.

 

그러면 최종적인 코드는 다음과 같다.

from math import ceil
prime = 1000003
def fac(n, P):
    ans = 1
    for i in range(1, n+1):
        ans = (ans*i)%P
    return ans

def com(n, k, P):
    if n < k:
        return 0
    num = (fac(n-k, P) * fac(k, P))%P
    large = pow(num, P - 2, P)
    return (fac(n, P) * large) % P

def C(n, k, P):
    f = 1
    while n:
        f *= com(n % P, k % P, P)
        f %= P
        n //= P
        k //= P
    return f

T = int(input())
for _ in range(T):
    N, K = map(int, input().split())

    game = (2*C(K, K//2, prime)) % prime
    ans = pow(game, N-1, prime)
    print(ans)

실패의 흔적

 

푼사람이 얼마 안되서 그런지, 파이썬 코더인 나는 이 문제에서 당당히 숏코딩 1등을 찍었다.