증가하는 부분 수열의 개수 G
시간 제한3초메모리 제한1024 MB
골롬 수열에서 길이가 N이고 마지막 값이 M인 순증가 부분 수열의 개수를 998244353으로 나눈 나머지를 구한다.
문제
수열 는 Golomb 수열이다. 즉, 다음 조건을 만족하는 유일한 무한수열이다.
- 모든 원소는 양의 정수이다.
- 감소하지 않는 수열이다.
- 는 수열 에 존재하는 원소 의 개수이다.
수열 에서 길이가 이면서 마지막 수가 인 증가하는 부분 수열의 개수를 구하는 프로그램을 작성하시오.
입력
정수 과 이 공백으로 구분되어 주어진다.
출력
문제의 정답을 으로 나눈 나머지로 출력한다.
힌트
, , ..., 를 적어보면 다음과 같다.
, , , , , , , , ,