테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.

====== 합 ======

===== 풀이 =====
  * [[ps:여러가지 수학 정리|거듭제곱의 합]]을 계산하는 문제.
  * 풀이 방법은 [[ps:여러가지 수학 정리|거듭제곱의 합]]을 참고. n≤50으로 매우 작기 때문에, O(n^2) DP를 이용해도 순식간에 풀린다
  * 라그랑주 보간법을 이용한 코드는 [[ps:problems:boj:25974]] 참고.

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 1492. 합".

- Problem link: https://www.acmicpc.net/problem/1492
- Solution link: http://www.teferi.net/ps/problems/boj/1492
"""

MOD = 1_000_000_007

from teflib import combinatorics


def main():
    N, K = [int(x) for x in input().split()]
    s = [N] + [None] * K
    comb_table = combinatorics.CombTable(K + 1, MOD)
    for i in range(1, K + 1):
        sigma = sum(comb_table.get(i + 1, p) * s[p] for p in range(i))
        s[i] = (pow(N + 1, i + 1, MOD) - 1 - sigma) * pow(i + 1, -1, MOD) % MOD
    print(s[K])


if __name__ == '__main__':
    main()
</dkpr>
  * Dependency: [[:ps:teflib:combinatorics#CombTable|teflib.combinatorics.CombTable]]

{{tag>BOJ ps:problems:boj:플래티넘_2}}