폰친구

• 상하한이 있는 Composition의 개수 를 구하는 문제이다. 링크에서 설명했듯이 포함 배제의 원리 (PIE; Principle of Inclusion-Exclusion)나 생성함수 (Generating Function)를 이용해서 식을 유도한 뒤에 O(N+K)에 구할수 있다.
• 이 문제에서는 K⇐N*M으로 주어지므로 시간복잡도가 O(N*M)

"""Solution code for "BOJ 20296. 폰친구".

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

Tags: [combinatorics]
"""

from teflib import combinatorics

MOD = 10**9 + 7


def main():
    N, m, M, K = [int(x) for x in input().split()]
    print(combinatorics.count_compositions(K, N, MOD, lo=m, hi=M))


if __name__ == '__main__':
    main()

• Dependency: teflib.combinatorics.count_compositions