다항 계수

• 문제를 바꿔쓰면, [0..n] 범위의 자연수 m개로 이루어진 튜플 중에서 합이 k가 되는 것의 개수를 세는 문제이다.
• 공식 풀이는 O(m*k)의 DP 이지만, 조합론적 방법으로 O(m+k)에 푸는 것이 가능하다. 풀이는 상한이 주어진 composition 참고
• 이 문제에서는 k의 범위가 k⇐m*n 으로 주어져 있으므로, 시간복잡도가 O(m*n)이 된다

"""Solution code for "BOJ 16725. 다항 계수".

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

Tags: [combinatorics]
"""

from teflib import combinatorics


MOD = 1_000_000_009


def main():
    n, m, k = [int(x) for x in input().split()]
    print(combinatorics.count_compositions(k, m, MOD, hi=n))


if __name__ == '__main__':
    main()

• Dependency: teflib.combinatorics.count_compositions