백준 01492번 / 1492번 해설

II-eugene-II Note

백준 01492번 - 합 해설

백준 01492번 / 1492번 문제 링크
문제 이름 : 합
주 언어 : Python
태그 : 수학 / 다이나믹 프로그래밍 / 정수론 / 조합론 / 분할 정복을 이용한 거듭제곱 / 모듈로 곱셈 역원
solved.ac 등급 : Platinum II (2022/11/21 확인)

문제 보기

문제 :

$N$ 과

$K$ 가 주어졌을 때,

$1^{K} + 2^{K} + 3^{K} + ... + N^{K}$ 를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오.

입력 :

첫째 줄에

$N$ 과

$K$ 가 주어진다.

$N$ 은

$10^{9}$ 보다 작거나 같은 자연수이고,

$K$ 는

$50$ 보다 작거나 같은 자연수이다.

출력 :

첫째 줄에

$1^{K} + 2^{K} + 3^{K} + ... + N^{K}$ 를 1,000,000,007로 나눈 나머지를 출력한다.

백준 25974번 - 거듭제곱의 합 1 과 거의 동일한 문제입니다. (이 문제가 조금 더 제한이 작습니다. 즉, 25974번을 풀 수 있다면 이 문제또한 풀 수 있습니다.)

	mod = pow(10, 9) + 7
	dp = [[0 for _ in range(51)] for _ in range(51)]

	for i in range(0, 51): # 제 2종 스털링 수
	for j in range(0, i+1):
	if j == 0: dp[i][j] = 0
	elif i == j: dp[i][j] = 1
	elif j == 1: dp[i][j] = 1
	else: dp[i][j] = (dp[i-1][j-1]+j*dp[i-1][j])%mod

	dp[0][0] = 1
	Ans = 0

	n, p = input().split()
	n = int(n)
	p = int(p)
	fallFac = n + 1

	for k in range(1, p + 1):
	fallFac *= n + 1 - k
	fallFac = fallFac % mod
	Ans += dp[p][k] * fallFac * pow(k+1, mod-2, mod) % mod
	Ans = Ans % mod

	print(Ans)

view raw BOJ01492.py hosted with ❤ by GitHub

-번째 푼 문제 (2022/--/--)