마법 학교 배치
골드 III의견: 0
마법 학교에 \(N\)명의 신입생이 입학했다. 학교에는 \(K\)개의 기숙사 방이 있으며, 각 방에는 몇 명이든 들어갈 수 있다. 단, 학교의 방침에 따라 모든 방에 학생이 최소 한 명 이상 배정되어야 한다.
\(N\)명을 \(K\)개의 방에 배정하는 방법의 수를 \(10^9+7\)로 나눈 나머지를 구하여라. 방 번호와 학생 번호가 다르면 다른 배정으로 본다.
- \(1 \le K \le N \le 200\,000\)
- 답은 \(10^9+7\)로 나눈 나머지로 출력한다.
한 줄에 학생 수 \(N\)과 방 수 \(K\)가 공백으로 구분되어 주어진다.
방법의 수를 \(10^9+7\)로 나눈 나머지를 출력한다.
3 2
6
학생 \(3\)명을 방 \(2\)개에 각 방에 최소 \(1\)명씩 배정하는 방법: \(\{1\}\{2,3\}\), \(\{2\}\{1,3\}\), \(\{3\}\{1,2\}\), \(\{1,2\}\{3\}\), \(\{1,3\}\{2\}\), \(\{2,3\}\{1\}\) → 포함 배제로 \(2^3 - 2 \cdot 1^3 = 6\).
4 3
36
포함 배제: \(3^4 - 3\cdot2^4 + 3\cdot1^4 = 81 - 48 + 3 = 36\).
riseoj 작성
출처 Original
평가 및 의견
마법 학교 배치
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
마법 학교 배치