백준 BOJ 29719 브실이의 불침번 근무
https://www.acmicpc.net/problem/29719
파이썬 python 문제 풀이
문제
브실이는 브실사단에서 브실브실 중대에 군 복무 중인 군인으로 여느 때와 다름없이 군 생활 중 한 공지문을 보게 됐다.
<공지사항>
행정반에서 공지사항 전파 말씀드립니다.
상급 부대의 지시에 의해 우리 브실브실 중대에서는 N일 동안 불침번을 서게 되었습니다. 이러한 이유로 현재 중대에 있는 M명의 용사를 넣어 불침번을 서게 할 생각입니다.
불침번은 혼자서도 할 수 있으므로 하루마다 용사 한 명씩 넣을 계획입니다. 불침번을 여러 번 서는 용사가 있을 수 있음에 유의해 주시기 바랍니다.
브실이는 당연히 군 복무 중인 군인이기에 M명의 불침번 후보에 본인도 포함되어 있다는 것을 안다.
브실이는 이러한 공지를 보고 자신이 불침번에 들어갈 경우의 수가 얼마나 되는지 궁금해졌다.
궁금해진 브실이를 위해 대신 당신이 알려주자. 단, 투입되는 인원이 같아도 들어가는 순서가 다르면 다른 경우가 되며 수가 너무 커질 수 있으므로 1000000007로 나눈 나머지를 출력하자.
입력
첫 번째 줄에 정수 N과 M이 공백으로 구분되어 주어진다. (1≤N,M≤10^6)
출력
브실이가 하루 이상 불침번에 들어갈 경우의 수를 1000000007로 나눈 나머지를 출력한다.
풀이
# 29719 브실이의 불침번 근무
# 실버 4
import sys
# n일 동안, m명
n, m = map(int, sys.stdin.readline().split())
# 모듈러 상수
MOD = 1000000007
# 전체 경우의 수: M^N
total = pow(m, n, MOD)
# 브실이가 한 번도 불침번을 서지 않는 경우의 수: (M-1)^N
no = pow(m-1, n, MOD)
# 브실이가 하루 이상 불침번을 서는 경우의 수: M^N - (M-1)^N
yes = (total - no) % MOD
print(yes)
pow(x, y)는 x를 y 제곱한 값x^y를 반환함.pow(x, y, z)는(x^y) % z를 반환함.- 큰 수의 거듭제곱을 계산할 때 유용한 형태