사용자 도구

사이트 도구


ps:problems:boj:1492

ps
링크acmicpc.net/…
출처BOJ
문제 번호1492
문제명
레벨플래티넘 2
분류

수학

시간복잡도O(K^2)
인풋사이즈K<=50
사용한 언어Python
제출기록76ms
최고기록56ms
해결날짜2021/05/30

풀이

코드

"""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()

토론

댓글을 입력하세요:
B J H B J
 
ps/problems/boj/1492.txt · 마지막으로 수정됨: 2023/02/09 16:04 저자 teferi