Tea time in the grand garden

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

요약
길이 N+2이고 양 끝이 0인 음이 아닌 정수 수열 중 상승분의 합(양의 증가량의 합)이 정확히 K인 수열의 개수를 998244353으로 나눈 나머지를 구한다.
난이도

보통10점 중 7점

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

문제

Appropriate temperature changes are essential for brewing delicious tea. Noli has been taught a recipe for delicious tea.

The recipe is represented by a sequence of non-negative integers A=a_0,a_1,a_2,…,a_N,a_N+1A = a\_0, a\_1, a\_2, \dots, a\_N, a\_{N+1} of length N+2N+2. She must change the temperature accordingly.

Raising the temperature is hard work. The cost of a recipe AA is defined by the following f(A)f(A).

f(A)=∑_i=0Nmax⁡(0,a_i+1−a_i)f(A) = \sum\_{i=0}^{N}{\max(0, a\_{i+1} - a\_i)}

Noli has forgotten the recipe she was taught. All she remembers is that a_0=a_N+1=0a\_0 = a\_{N+1} = 0 and that the cost was KK.

How many possible recipes can be considered? Find the remainder of the number of possible recipes divided by 998244353998244353.

Note that two recipes are different when the values of a_ia\_i are different for any ii (0≤i≤N+10 \le i \le N+1).

입력

NN KK

출력

Output the remainder of the number of possible recipes divided by 998244353998244353. Add a new line at the end of the output.

제한

  • All inputs consist of integers.
  • 1≤N≤2×1051 \le N \le 2 \times 10^5
  • 0≤K≤2×1050 \le K \le 2 \times 10^5

힌트

In Sample Input 1, There are five possible sequences AA.

  • 0,2,0,0\\{0,2,0,0\\}
  • 0,0,2,0\\{0,0,2,0\\}
  • 0,1,2,0\\{0,1,2,0\\}
  • 0,2,1,0\\{0,2,1,0\\}
  • 0,2,2,0\\{0,2,2,0\\}

예제4

  1. 예제 1

    입력
    2 2
    
    예상 출력
    5
    
  2. 예제 2

    입력
    100 0
    
    예상 출력
    1
    
  3. 예제 3

    입력
    300 300
    
    예상 출력
    527212271
    
  4. 예제 4

    입력
    200000 200000
    
    예상 출력
    885086300