問題一覧 > 通常問題

No.2791 Beginner Contest

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 122
作問者 : 👑 箱星箱星 / テスター : dadasdadas
0 ProblemId : 4333 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-06-15 14:46:28

問題文

ある競技プログラミングサイトでは定期的に Beginner Contest が開催されています。このサイトの参加者にはレーティングと呼ばれる整数値が定まっています。

Beginner Contest に参加すると結果に応じてレーティングが変動します。ただし Beginner Contest に参加してもレーティングが $N$ より大きくなることはありません。

箱星さんは Beginner Contest に $0$ 回以上参加しようと思っています。箱星さんの現在のレーティングは $0$ です。

箱星さんはレーティングが下がることや少ししか上がらないことが嫌いなので、参加した Beginner Contest では必ずレーティングが $K$ 以上増加することを望んでいます。

この希望をみたすレーティングの推移としてあり得るものは何通りあるでしょうか。

ただし答えは非常に大きくなる場合があるので、$998244353$ で割った余りを求めてください。

制約

  • 入力はすべて整数
  • $1 \le N \le 10^5$
  • $1 \le K \le 10^9$

入力

入力は以下の形式で標準入力から与えられます。
$N$ $K$

出力

レーティングの推移としてあり得るものが何通りあるかを求め、$998244353$ で割った余りを出力してください。

サンプル

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

レーティング推移としてあり得るものは次の $5$ 通りです。

  • $0$
  • $0\to 2$
  • $0\to 3$
  • $0\to 4$
  • $0\to 2\to 4$
サンプル2
入力
1 2
出力
1

Beginner Contest に参加してもレーティングを $2$ 以上増加させることはできないので、「Beginner Contest に参加しない」 $1$ 通りのみです。

サンプル3
入力
31415 9
出力
779869259

$998244353$ で割った余りを出力することに注意してください。

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