[Python] 32390번 과녁 맞히기

 

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

---

 

24/11/17

 

 

이전에 KCPC때 검수 못했던 문제 중 하나인데, 이제서야 풀어본다.

 

사실 그때 한 30분 정도 생각해보다가 답이 안나와서 그냥 GG치고 다른 문제를 봤다.

 

이제서야 붙잡은 이유는 큰 이유는 없고, 그냥 좀 붙잡으면 풀릴 것 같아서 붙잡았다.

 

이 문제를 풀기 위해선, 모듈로 곱셈 역원에 대한 지식이 필요하다.

---

 

문제 접근 방식:

 

 

문제가 뭔가 수능에서 나올법 한 경우의 수 문제랑 비스무리 하다.

 

$M$개의 줄이 있고, 각 줄에는 과녁이 $A_i$개 만큼 달려있다. 나는 과녁을 쏠 때, 각 줄에서 위 또는 아래만 쏠 수 있다.

이 문제에서 구하고자 하는 것은 과녁을 쏘는 전체 경우의 수이다.

 

 

일단 각 줄 별로 생각을 하면, 위 또는 아래를 쏠 수 있고, 마지막 과녁 하나가 남을 때까지 그렇게 위 또는 아래를 쏠 수 있다.

 

따라서, "하나의 줄"만 고려하였을 때의 경우의 수는 $2^{A_i - 1}$이다.

 

예시를 들어보자. 첫번째 줄에 4개의 과녁이 달려있다고 하고, 각 과녁에는 $[1, 2, 3, 4]$라고 숫자가 붙여져있다 가정해보자.

 

그러면 다음과 같이 8개의 순열이 나온다.

 

$$[1, 2, 3, 4], [1, 2, 4, 3], [1, 4, 2, 3], [1, 4, 3, 2], [4, 1, 2, 3], [4, 3, 1, 2], [4, 1, 3, 2], [4, 3, 2, 1]$$

 

그렇게 우리는 $i$번째 줄 마다 $2^{A_i - 1}$개의 순열을 얻을 수 있다.

 

따라서, 모든 줄에 대하여 순열을 얻는 경우의 수는 $\prod_{i=1}^{M} 2^{A_i - 1}$가 된다.

 

 

이제 여기에 각 줄마다 고려했을 때의 "순서를 유지한 채로 순열을 뒤섞는" 경우의 수를 곱하면 될 것이다.

 

사실, 이미 모든 줄에 대해서 그렇게 순서를 정해놨다면, 하나의 줄에 달려있는 과녁들은 같은 색깔의 과녁이라고 생각해도 된다.

 

예를 들어, 2개의 줄이 있고, 첫번째 줄에는 [1, 2, 3]이라는 과녁이, 두번째 줄에는 [4, 5, 6]이라는 과녁이 있다고 해보자.

 

우리가 이전에 첫번째 줄은 [1, 3, 2]순으로 맞아야 한다고 정했고, 두번째 줄은 [6, 5, 4]순으로 맞아야 한다고 정했다고 해보자.

 

이전에 우리가 [1, 3, 2]와 [6, 5, 4]라는 순서를 이미 정해두었기 때문에, 각 줄마다의 순서는 "이미" 고정이다.

 

따라서, 첫번째 줄의 과녁들을 전부 같은 색깔의 공, 예를 들어 빨간 공 3개라고 하고, 두번째 줄의 과녁들도 전부 같은 색깔의 공, 예를 들어 파란 공 3개라고 하자.

 

그러면 빨간 공 3개와 파란 공 3개를 일렬로 나열하는 경우의 수는 $6!/3!3!$이다.

 

위의 예시처럼, 앞에서 이미 순서를 고정해놨기 때문에 $N! / (A_{1}!A_{2}! \cdots A_{M}!)$이 "순서를 유지한 채로 뒤섞는" 경우의 수가 될 것이다.

 

 

따라서, 다음 식이 최종 답이 된다.

 

$$\prod_{i=1}^{M}2^{A_i - 1} \cdot \frac{N!}{A_{1}! A_{2}! \cdots A_{M}!}$$

 

$2^{A_i -1}$들은 분할정복을 이용한 거듭제곱을 통해 빠르게 구할 수 있고, $A_{i}!$들을 나누는 것은 페르마의 소정리를 통해 구할 수 있다. (MOD가 소수이기 때문에 항상 역원이 존재한다.)

 

혹은, 파이썬은 pow()함수의 인자로 $-1$을 줌으로써 역원을 쉽게 구할 수 있으니, 이를 참고하여 구현하면 된다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 32390번 과녁 맞히기
# 조합론
'''
접근 방법:
각 줄마다 위,아래를 쏠 수 있음. 마지막 하나 남으면 위나 아래나 상관이 없음.
따라서, 각 줄마다 2^(Ai-1)가지 만큼의 순열이 생김.
모든 줄에 대해서 쏘기 때문에, 이 순열의 "순서"를 유지하면서 쏠거임.
따라서, 각 줄별로 이미 순서는 정해져있음.
같은 줄의 과녁은 같은 색깔의 공이라고 생각해보자.
이 공을 나열하는 경우의 수는 N!/(A1! A2! ... AN!).
어차피 각 줄별로 순서가 정해지면 거기에 넣으면 된다.
각 줄별로 순서를 정하는 경우의 수는 2^(A1-1)*2^(A2-1) ... 2^(An-1)
'''
import sys
input = sys.stdin.readline
MOD = 1_000_000_000+7

DP = dict()
N, M = map(int, input().split())
A = sorted(map(int, input().split()))
ans, mul, j = 1, 1, 0
for i in range(1, N+1):
    mul *= i
    mul %= MOD
    while j < M and i == A[j]:
        ans *= pow(mul,-1,MOD)
        ans %= MOD
        ans *= pow(2,A[j]-1,MOD)
        ans %= MOD
        j += 1
ans *= mul
ans %= MOD
print(ans)