[Python] 31537번 출근하기 싫어 1

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

---

 

25/07/02

 

 

플레티넘 200문제를 채우기 위해서 풀만한 플레티넘 문제를 밀다가 푼 문제 중 하나이다.

 

간단한 조합론 문제이다.

---

 

문제 접근 방식:

 

 

문제를 요약하면 다음과 같다.

 

매 시간마다 최대 $1$명이 회사에 없어도 됨. 즉, 매 시간마다 확인했을 때 모든 사람이 있거나 한 사람만 빠져있어야 함.

 

$M$시간을 확인하고, $N$명의 직원 각각 $M$시간 중 몇 시간동안 회사에 있었는지에 대한 정보가 $A_i$로 주어짐.

 

이때, $M$시간 동안 출근해 있는 직원들의 경우의 수를 구하는 것이 목적이다.

 

 

$i$번째 직원은 $M$시간 중 $A_i$시간 나온다. 즉, $M$시간 중에서 $M-A_i$시간만큼 빠져있다.

 

최대 $1$명이 출근하지 않는다라는 말은, $j$번째 시간에서는 한 명 빠질수도 있고, 아예 안빠질수도 있다는 뜻과 같다.

 

이제, 이걸 공으로 생각한다면, $i$번째 직원이 $M-A_i$시간만큼 빠진다는 것은 $i$번 색깔 공이 $M-A_i$개 있다는 말과 같고, $j$번째 시간에서 $i$번째 직원이 빠진다는 것은 해당 색깔 공을 뽑는다는 말과 같다.

 

이때 $j$번째 시간때 모두가 안빠지는 것은 흰 공을 뽑는 행위로 취급하면 된다.

 

즉, 정리하자면 한 명 빠지는 경우 = $i$번째 색깔 공 뽑는 행위, 안빠지는 경우 = 흰 공 뽑는 행위라고 생각하면 된다.

 

이 때 흰 공은 $M -$ (색깔 공들의 개수의 합) 만큼 존재함을 쉽게 알 수 있다.

 

물론 이는 흰 공이 존재할 때, 즉, $M$이 색깔 공들의 개수의 합보다 클 때만 가능하고, 만약 $M$이 색깔 공들의 개수의 합보다 작다면 적어도 하나의 시간대에서 2명이상이 빠지게 되므로 불가능하며, 같다면 흰 공이 존재하지 않는다.

 

 

조합론적으로 생각하면 이건 다항계수이므로, 다음과 같은 식을 구하는 것과 동일하다.

$$\frac{M!}{(M-A_1)! \cdot (M-A_2)! \cdots (M-A_n)! \cdot (M-S)!}$$

 

여기서 $S$는 색깔 공들의 개수의 합이다.

 

$M$의 제한이 $10^6$까지이기 때문에 해당 크기만큼의 팩토리얼 값의 모듈로 값과, 이것의 역원들을 미리 저장할 수 있다.

 

미리 저장한 뒤에 해당 공식을 계산하면 된다.

---

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

 

# 31537번 출근하기 싫어 1
# 조합론, 모듈로 역원
'''
접근 방법:
i번째 직원은 M시간 중 A_i시간 나옴
-> M시간 중 M-A_i시간 빠짐
최대 1명이 출근하지 않는다
= j번째 시간에서는 한명 빠질수도 있고 아예 안빠질 수도 있다
안빠진다면 -> 흰 공 뽑는 행위로 취급
빠진다면 -> i번째 색깔 공(M-A_i개 존재)뽑는 행위로 취급
=> 다항계수 빨리 구하기
'''
import sys
input = sys.stdin.readline
MOD = 1_000_000_000+7

fact = [1, 1]
fact_inv = [1, 1]
now = 1
for i in range(2, 1_000_001):
    now *= i
    now %= MOD
    fact.append(now)
    fact_inv.append(pow(now, -1, MOD))
N, M = map(int, input().split())
A = list(map(int, input().split()))
if sum(A) < (N-1)*M:
    print(0)
else:
    A = [M-a for a in A]
    if sum(A) < M:
        A.append(M-sum(A))
    ans = fact[M]
    for a in A:
        ans *= fact_inv[a]
        ans %= MOD
    print(ans)