No.1011 Infinite Stairs
タグ : / 解いたユーザー数 259
作問者 :
otamay6
/ テスター :
Lemma299
polylogK
問題文
無限に続く階段があります。あなたは最初 $0$ 段目にいて、次の行動を $N$ 回繰り返そうとしています。
・$i$ 段目にいるとき、 $i+1$ 段目, $i+2$ 段目, $\dots$ , $i+d$ 段目のいずれかに移動する
$N$ 回の移動のあと、$K$ 段目に辿りつく移動方法が何通りあるかを求めて下さい。
ただし答えは非常に大きくなることがあるので $10^9+7$ で割った余りを求めて下さい
入力
$N\ d\ K$
入力は全て整数で与えられる
$1 \le N,d \le 300$
$N \le K \le d \times N$
出力
$N$ 回の移動のあと、$K$ 段目に辿りつく移動方法が何通りあるかを出力してください。
最後に改行してください。
サンプル
サンプル1
入力
3 2 5
出力
3
(2,2,1), (2,1,2), (1,2,2) の3通りの移動方法があります
サンプル2
入力
6 3 10
出力
90
ありえる移動方法のうち昇順なものは (1,1,1,1,3,3), (1,1,1,2,2,3), (1,1,2,2,2,2) の3通りで、このうちどれかを並び替えたものは
${}_{6}{\rm C}_{2}$ + ${}_{6}{\rm C}_{3}\times {}_{3}{\rm C}_{2}$ + ${}_{6}{\rm C}_{2}$ = 90 通りあります
サンプル3
入力
256 12 1444
出力
866273184
答えは $10^9+7$ で割った余りを出力してください
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。