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

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

요약
골롬 수열에서 길이가 N이고 마지막 값이 M인 순증가 부분 수열의 개수를 998244353으로 나눈 나머지를 구한다.
난이도

어려움10점 중 8점

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

문제

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

  • 모든 원소는 양의 정수이다.
  • 감소하지 않는 수열이다.
  • G_iG\_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으로 나눈 나머지로 출력한다.

힌트

G_1G\_1, G_2G\_2, ..., G_9G\_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