준오는 심술쟁이!!

• 바꿔쓰면 0≤x_i≤25 일때, x_1+x_2+..+x_l = s 가 되는 (x_1,…,x_l) 의 개수를 세는 문제이다
• 공식 풀이는 O(s*l) 의 DP이지만, 조합론적 방법으로 O(s+l) 에 해결이 가능하다. 풀이는 상한이 주어진 composition 참고

"""Solution code for "BOJ 14437. 준오는 심술쟁이!!".

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

Tags: [combinatorics]
"""

from teflib import combinatorics

MOD = 1_000_000_007


def main():
    s = int(input())
    problem = input()
    print(combinatorics.count_compositions(s, len(problem), MOD, hi=25))


if __name__ == '__main__':
    main()

• Dependency: teflib.combinatorics.count_compositions