이진 트리 개수 세기

시간 제한15초메모리 제한512 MB

요약

각 내부 노드에서 왼쪽 서브트리의 잎 개수가 오른쪽보다 k를 넘게 많지 않은 전이진 트리의 개수를 잎 n개 기준으로 구하고 998244353으로 나눈 나머지를 출력합니다.

난이도: 어려움10점 중 8점
유형: 동적 계획법, 조합론, 분할 정복
정답자: 아직 제출이 없습니다

문제

정점마다 자식이 0개 또는 2개인 완전 이진 트리 중에서, 잎이 정확히 $n$ 개인 트리의 개수를 구하라. 자식을 두 개 가진 모든 정점에 대해, 왼쪽 서브트리의 잎 개수가 오른쪽 서브트리의 잎 개수보다 $k$ 를 넘게 많아서는 안 된다. 답은 998244353으로 나눈 나머지로 출력한다.

입력과 출력

한 줄에 정수 $n$ 과 $k$ 가 주어진다 ( $2 \le n \le 10^6$ , $0 \le k \le 100$ ).

구하는 개수를 출력한다.

예제3

예제 1
입력
```
2 0
```
예상 출력
```
1
```
예제 2
입력
```
3 0
```
예상 출력
```
1
```
예제 3
입력
```
3 1
```
예상 출력
```
2
```