問題一覧 > 通常問題

No.2857 Div Array

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 54
作問者 : dyktr_06dyktr_06 / テスター : ryota2357ryota2357 square1001square1001
4 ProblemId : 10858 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-08-20 19:26:25

問題文

長さが NN で各要素が 11 以上 MM 以下の整数列であって、以下の条件を満たすものを良い整数列と呼びます。

  • 整数列を AA とすると、1iN11 \leq i \leq N - 1 を満たす整数 ii について、MAiMAi+1K\displaystyle \left | \left \lfloor \frac{M}{A_i} \right \rfloor - \left \lfloor \frac{M}{A_{i + 1}} \right \rfloor \right | \leq K

良い整数列としてあり得るものは何通りあるでしょうか。

答えは非常に大きくなる可能性があるため、998244353998244353 で割ったあまりを出力してください。


制約

  • 1N1091 \leq N \leq 10^{9}
  • 1M10001 \leq M \leq 1000
  • 0KM0 \leq K \leq M
  • 入力はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

NN MM KK 

出力

問題の答えを 998244353998244353 で割ったあまりを一行に出力せよ。

サンプル

サンプル1
入力
2 3 1
出力
5

良い整数列としてあり得るものは (1,1),(2,2),(2,3),(3,2),(3,3)(1, 1), (2, 2), (2, 3), (3, 2), (3, 3)55 通りです。

サンプル2
入力
100 100 38
出力
412066770

998244353998244353 で割ったあまりを出力してください。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。