R01422
계단 경로
골드 IV레이팅
의견: 0
설명
격자 위 \((0,0)\)에서 출발하여 \((N, M)\)에 도달하는 경로를 생각한다. 한 번의 이동으로 오른쪽(\((x,y)\to(x+1,y)\)) 또는 위쪽(\((x,y)\to(x,y+1)\))으로만 이동할 수 있다.
경로가 지나는 모든 점 \((x,y)\)에서 \(y \le x\)를 만족해야 한다. 즉, 항상 '위로 올라간 횟수 \(\le\) 오른쪽으로 이동한 횟수'인 경로만 허용된다.
조건을 만족하는 경로의 수를 \(10^9+7\)로 나눈 나머지를 출력하여라.
제약
- \(0 \le M \le N \le 200\,000\)
- \(N + M \le 200\,000\)
입력 형식
한 줄에 정수 \(N\)과 \(M\)이 공백으로 구분되어 주어진다.
출력 형식
조건을 만족하는 경로의 수를 \(10^9+7\)로 나눈 나머지를 출력한다.
예제 1
입력
3 2
출력
5
설명
\((3,2)\)까지 가는 \(\binom{5}{2}=10\)개의 경로 중 한 번이라도 \(y > x\)가 되는 경로를 뺀다. 반사 원리에 의해 금지 경로는 \(\binom{5}{1}=5\)개이므로 답은 \(10 - 5 = 5\)이다.
예제 2
입력
4 4
출력
14
설명
\(N = M\)이면 카탈란 수 \(C_N\)이 된다. \(C_4 = 14\)이다.
문제 정보
riseoj 작성
출처 Original
태그
평가 및 의견
계단 경로
개별 의견
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
계단 경로
게스트로 둘러보고 있습니다. 로그인하면 풀이를 제출하고 진행 상황을 확인할 수 있습니다.
로그인하고 제출하기