BOJ 32064 Sharing Bread

문제 링크입니다.

문제 요약

토스트 $N$개가 있습니다. $M$명의 사람들이 순서대로 각자 정해진 위치에서 출발해 오른쪽으로 가면서 만나는 첫 토스트를 먹습니다. 모든 사람이 토스트를 먹을 수 있도록 각자의 위치를 정하는 방법의 수를 구하세요.

뭐라도 먹이기

사람들이 반드시 토스트를 먹게끔 하기 위해, $N$번 토스트를 얻는 데 실패했다면 $1$번 토스트로 돌려보냅시다. 이러면 모든 사람들에게 번호를 부여하면 그에 따라 하나의 토스트에 배정됩니다.

실제로는 $N$번에서 $1$번 토스트로 넘어갈 수 없기 때문에 이를 체크해 줄 방법이 필요합니다. 그 방법은, 토스트가 있으면 반드시 먹어야 함에서 착안해 $N+1$번째 토스트를 들이는 것입니다.

$N+1$번째 토스트를 먹는 배치는 모두 불가능하고, 그렇지 않은 배치는 모두 가능함을 알 수 있습니다. 배정된 번호를 하나씩 옆으로 밀면 배정받는 토스트의 번호도 하나씩 밀리므로, 조건을 만족하도록 사람들에게 번호를 부여하는 방법의 수는 $N+1$개의 토스트가 있을 때의 방법의 수에서 $N+1$을 포함하지 않는 배치의 비율을 곱한 것이 됩니다. 옆으로 밀면서 만들어지는 $N+1$개의 배치 중 $N+1$번째 토스트를 포함하지 않는 배치는 $N+1-M$개이므로, 답은 ${ (N-M+1) \over N+1 } (N+1)^M$입니다.

코드

n, m = map(int, input().split())
print((n-m+1)*pow(n+1, m-1, 998244353)%998244353)