아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

서로 다른 합mand 개수 세기

시간 제한2초메모리 제한256 MB

요약
양의 정수 n을 m개의 양의 정수 합으로 나타내는 모든 순서 있는 분할에 대해, 서로 다른 값의 개수 f를 모두 더한 값을 998244353으로 나눈 나머지를 구한다. n은 1e18까지, m은 500까지 주어진다.
난이도

어려움10점 중 9점

유형
조합론, 수학, 정수론, 동적 계획법
정답자
아직 제출이 없습니다

문제

양의 정수 nn을 mm개의 양의 항으로 나누는 모든 순서 있는 분할 n=a1+a2+…+amn = a_1 + a_2 + \ldots + a_m을 생각하자. f(a1,a2,…,am)f(a_1, a_2, \ldots, a_m)을 a1,a2,…,ama_1, a_2, \ldots, a_m 중 서로 다른 정수의 개수라고 하자. nn의 모든 순서 있는 분할에 대해 f(a1,a2,…,am)f(a_1, a_2, \ldots, a_m)의 합을 구하고, 이를 998 244 353998\,244\,353으로 나눈 나머지를 출력하시오.

두 순서 있는 분할 a1+a2+…+am=na_1 + a_2 + \ldots + a_m = n과 b1+b2+…+bm=nb_1 + b_2 + \ldots + b_m = n은 어떤 i∈{1,2,…,m}i \in \{1, 2, \ldots, m\}에 대해 ai≠bia_i \neq b_i이면 서로 다른 것으로 본다.

입력

입력은 한 줄이며 두 정수 nn과 mm이 주어진다. (1≤n≤10181 \le n \le 10^{18}, 1≤m≤5001 \le m \le 500, m≤nm \le n)

출력

답을 998 244 353998\,244\,353으로 나눈 나머지를 출력하시오.

예제2

  1. 예제 1

    입력
    10 2
    
    예상 출력
    17
    
  2. 예제 2

    입력
    20 4
    
    예상 출력
    3413