[Python] 27533번 따로 걸어가기

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

27533번: 따로 걸어가기

---

 

23/11/27

 

 

LGV Lemma를 알고 있다면 쉽게 해결할 수 있는 문제로, 굳이 LGV Lemma를 알고 있지 않아도 포함 배제의 원리로 풀 수 있는 문제이다. (정확히 말하면, LGV Lemma가 이거의 일반화긴 하다.)

---

 

문제 접근 방식:

 

 

LGV Lemma에 대한 자세한 설명은 아래 글을 참고하자.

 

2023.12.17 - [수학 공부 기록] - [조합론] 린드스트롬-게셀-비엔노 보조정리(LGV Lemma)

[조합론] 린드스트롬-게셀-비엔노 보조정리(LGV Lemma)

 

이 문제는 $(1, 2)$와 $(2, 1)$이 두 시작지점이고, $(N, M-1)$과 $(N-1, M)$이 두 도착지점인 교차하지 않는 경로의 개수를 구하는 문제와 사실 같음을 우린 알고 있다.

 

그리고 이는 LGV Lemma를 통해 쉽게 구할 수 있다.

 

왜냐하면 교차하도록 만드는 Permutation이 오직 $\mathrm{id}$밖에 없기 때문이다.

 

실제로 그 값을 구하면 아래 식과 같이 나온다.

$$\left(\binom{n+m-4}{m-2}\right)^2 - \binom{n+m-4}{m-1} \binom{n+m-4}{n-1}$$

 

토순이가 시작하는 지점이 서로 바뀔 수도 있으므로, 저 값에 $2$를 곱해주면 정답이 된다.

 

모듈로 값을 구하는 것에 유의하자.

 

---

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

# 27533번 따로 걸어가기
# LGVLemma
'''
접근 방법:
LGVLemma에 의하면 2*(comb(n+m-4, m-2)^2 - comb(n+m-4, m-1)*comb(n+m-4, n-1))
n*facinv(n) % mod = facinv(n-1)
'''
import sys
input = sys.stdin.readline

MOD = 1_000_000_000+7
N, M = map(int, input().rstrip().split())
fac = [-1 for _ in range(N+M+1)]
fac_inv = [-1 for _ in range(N+M+1)]
fac[0] = 1
for i in range(1, N+M+1):
    fac[i] = (fac[i-1]*i)%MOD
fac_inv[N+M] = pow(fac[N+M], MOD-2, MOD)
for i in range(N+M, 0, -1):
    fac_inv[i-1] = (i*fac_inv[i])%MOD
def comb(n, r):
    if n < r:
        return 0
    return (((fac[n]*fac_inv[r])%MOD)*fac_inv[n-r])%MOD
ans = (((comb(N+M-4, M-2)*comb(N+M-4, M-2))%MOD - (comb(N+M-4, M-1)*comb(N+M-4, N-1))%MOD)%MOD)*2%MOD
print(ans)