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

정석적으로 하면 $n$번의 덧셈을 해야하나 당연히 주어진 시간 내에 $10^{9} = 10$억번 연산가능할 리는 없습니다.
$n$번의 덧셈을 하는 대신 상대적으로 범위가 더 작은 $p$에 대한 식은 없을까? 라는 생각에서 파울하버의 공식 이 나오게 됩니다.
$$ \sum_{k = 1}^n k^{p} = \frac{n^{p + 1}}{p + 1}+\frac{1}{2}n^p+\sum_{j = 2}^p \frac{B_{j}}{j!} \frac{p!}{(p - j + 1)!} n^{p - j + 1} $$ 에서, 다른 식들은 충분히 구할 수 있으나, 가장 큰 문제는 $B_{j}$, 즉 베르누이 수 입니다.
베르누이 수의 일반항이 $$B_{n} = \sum_{k = 0}^n \frac{1}{k + 1} \sum_{r = 0}^{k} \binom{k}{r}(-1)^{r} r^{n}$$인 만큼 계산이 매우 복잡하고 번거롭습니다. (심지어 베르누이 수는 정수도 아니고 분수꼴로 나옵니다.)
따라서 다른 방법을 찾아보던 중...
$$ \sum_{k = 0}^n k^p = \sum_{k=0}^p \left\{{p\atop k}\right\}\frac{(n + 1)_{k + 1}}{k + 1} $$ 라는 공식을 발견했습니다.
$\left\{{p\atop k}\right\}$은 제 2종 스털링 수이고, $(n + 1)_{k + 1}$은 $(n + 1)$부터 $(n - k + 1)$까지 연속된 $k + 1$개의 정수의 곱 ( 하강계승 ) 입니다.
제 2종 스털링수는 $\left\{{n+1\atop k}\right\} = k \left\{{ n \atop k }\right\} + \left\{{n\atop k-1}\right\}$, $\left\{{ 0 \atop 0 }\right\} = 1$, $\left\{{ n \atop 0 }\right\} = \left\{{ 0 \atop n }\right\} = 0$, $\left\{{ n \atop n }\right\} = \left\{{ n \atop 1 }\right\} = 1$이라는 재귀공식으로 제 2종 스털링 수의 dp를 만들 수 있습니다.
$\left\{{p\atop k}\right\}{(n + 1)_{k + 1}}$가 정수이고, 거기에 페르마의 소정리 에 따른 $k + 1$의 mod $10^9 + 7$ 모듈러 곱셈 역원 인 ${(k + 1)}^{10^{9} + 5} \pmod{10^{9} + 7}$을 곱해주는 형식으로
$$ \sum_{k=0}^p \left\{{p\atop k}\right\}{(n + 1)_{k + 1}}{(k + 1)}^{10^{9} + 5} \mod\left(10^9+7\right) $$ 의 값을 구해주면 $$\left(\sum_{k = 1}^{n}k^{p}\right)\mod\left( 10^{9}+7 \right)$$의 값을 구할 수 있습니다.

여담으로... 이 글을 처음 쓰는 22년 11월 11일 기준으로 너무 최근 문제라 검색해도 특별히 해설도 안보이고 다른 분들 풀이를 봐도 무슨 방법인지 잘 보이지를 않습니다.
(심지어 글 쓰는 도중에 태그가 추가되는 경험도 했습니다. 제가 풀었을 때는 수학 / 벌리캠프 태그만 있었습니다.)
또, 좋은건지 나쁜건지 코드가 제가 2번째로 짧은 관계로 조금 더 짧게 고쳐서 숏코딩 탭에서 1위를 차지해보았습니다.

아마 어지간한 백준 문제 중에서 랭크에 올라간 몇 안되는 문제가 되지 않을까 생각해봅니다.
244번째 푼 문제 (2022/11/11)