만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

증가하는 부분 수열의 개수 G

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

요약
골롬 수열의 부분수열 중 길이가 N이고 마지막 원소가 M인 증가하는 것의 개수를 998244353으로 나눈 나머지로 구합니다.
난이도

보통10점 중 7점

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

문제

수열 G={G1,G2,G3,⋯ }G = \{ G_1, G_2, G_3, \cdots \}는 Golomb 수열이다. 즉, 다음 조건을 만족하는 유일한 무한수열이다.

  • 모든 원소는 양의 정수이다.
  • 감소하지 않는 수열이다.
  • GiG_i는 수열 GG에 존재하는 원소 ii의 개수이다.

수열 GG에서 길이가 NN이면서 마지막 수가 MM인 증가하는 부분 수열의 개수를 구하는 프로그램을 작성하시오.

입력

정수 NN과 MM이 공백으로 구분되어 주어진다. (1≤N≤M≤300 000)(1 \le N \le M \le 300\,000)

출력

문제의 정답을 998 244 353998\,244\,353으로 나눈 나머지로 출력한다.

힌트

G1G_1, G2G_2, ..., G9G_9를 적어보면 다음과 같다.

11, 22, 22, 33, 33, 44, 44, 44, 55, ⋯\cdots

예제4

  1. 예제 1

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

    입력
    2 3
    
    예상 출력
    6
    
  3. 예제 3

    입력
    3 4
    
    예상 출력
    24
    
  4. 예제 4

    입력
    4 4
    
    예상 출력
    12