Logo
(追記) (追記ここまで)

30194번 - 징검다리 뒤로 건너기

시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 (추가 시간 없음) 1024 MB77484271.186%

문제

1ドル$번부터 $N$번까지 번호가 붙은 $N$개의 돌이 순서대로 일렬로 나열되어 있습니다. 1ドル$번 돌에서 출발하여 $N$번 돌까지 주어진 정수 $K$에 대해 다음 규칙을 만족하면서 이동하려 합니다.

  • $i$번 돌에서는 1ドル\le x\le K$인 정수 $x$에 대해 $i+x$번 돌로 이동하거나, $i-1$번 돌로 이동할 수 있습니다.
  • 돌이 없는 위치로는 이동할 수 없습니다.
  • 출발점과 도착점을 포함하여, 이미 밟은 돌은 다시 밟을 수 없습니다.

규칙에 따라 1ドル$번 돌에서 $N$번 돌까지 이동하는 경우의 수를 소수 1ドル,円 000,円 000,円 007(=10^9+7)$로 나눈 나머지를 구해봅시다. 밟은 돌의 번호를 순서대로 나열한 수열이 다르면 다른 이동으로 생각합니다.

입력

첫 번째 줄에 돌의 개수 $N$과 문제의 정수 $K$가 공백으로 구분되어 주어집니다. (1ドル\le N\le 2,円 000$; 1ドル\le K\le 50$)

출력

첫 번째 줄에 규칙에 따라 1ドル$번 돌에서 $N$번 돌까지 이동하는 경우의 수를 1ドル,円 000,円 000,円 007(=10^9+7)$로 나눈 나머지를 출력합니다.

제한

예제 입력 1 

5 3

예제 출력 1 

12

가능한 모든 경우는 다음과 같습니다.

  • 1ドル \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5$
  • 1ドル \rightarrow 2 \rightarrow 3 \rightarrow 5$
  • 1ドル \rightarrow 2 \rightarrow 4 \rightarrow 5$
  • 1ドル \rightarrow 2 \rightarrow 4 \rightarrow 3 \rightarrow 5$
  • 1ドル \rightarrow 2 \rightarrow 5$
  • 1ドル \rightarrow 3 \rightarrow 2 \rightarrow 4 \rightarrow 5$
  • 1ドル \rightarrow 3 \rightarrow 2 \rightarrow 5$
  • 1ドル \rightarrow 3 \rightarrow 4 \rightarrow 5$
  • 1ドル \rightarrow 3 \rightarrow 5$
  • 1ドル \rightarrow 4 \rightarrow 3 \rightarrow 2 \rightarrow 5$
  • 1ドル \rightarrow 4 \rightarrow 3 \rightarrow 5$
  • 1ドル \rightarrow 4 \rightarrow 5$

예제 입력 2 

8 4

예제 출력 2 

191

예제 입력 3 

1923 45

예제 출력 3 

703532137

힌트

출처

University > 서울대학교 > 서울대학교 프로그래밍 경시대회 > 2023 서울대학교 프로그래밍 경시대회 > Division 2 F번

(追記) (追記ここまで)

출처

대학교 대회

  • 사업자 등록 번호: 541-88-00682
  • 대표자명: 최백준
  • 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
  • 전화번호: 02-521-0487 (이메일로 연락 주세요)
  • 이메일: contacts@startlink.io
  • 통신판매신고번호: 제 2017-서울서초-2193 호

AltStyle によって変換されたページ (->オリジナル) /