問題一覧 > 通常問題

No.2791 Beginner Contest

レベル : / AI推定難易度 : 800 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 142
作問者 : 👑 箱星 / テスター : dadas
お気に入りにしたユーザー ProblemId : 4333 / 自分の提出
問題文最終更新日: 2024-06-15 14:46:28
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 434 (順位表) の他の問題:

Problem Statement

A certain competitive programming site regularly holds Beginner Contests. Each participant on this site has an integer value called a rating.

Participating in a Beginner Contest changes one's rating according to the result. However, participating in a Beginner Contest never makes the rating greater than $N$.

Hakoboshi plans to participate in Beginner Contests $0$ or more times. Hakoboshi's current rating is $0$.

Hakoboshi dislikes having the rating go down or go up only slightly, and therefore wishes that the rating always increases by $K$ or more in every Beginner Contest participated in.

How many possible rating histories satisfy this wish?

Since the answer can be very large, find it modulo $998244353$.

Constraints

  • All inputs are integers.
  • $1 \le N \le 10^5$
  • $1 \le K \le 10^9$

Input

The input is given from Standard Input in the following format.
$N$ $K$

Output

Find the number of possible rating histories and print it modulo $998244353$.

Sample

Sample 1
Input
4 2
Output
5

The following $5$ rating histories are possible.

  • $0$
  • $0\to 2$
  • $0\to 3$
  • $0\to 4$
  • $0\to 2\to 4$
Sample 2
Input
1 2
Output
1

Participating in a Beginner Contest can never increase the rating by $2$ or more, so the only possibility is "not participating in any Beginner Contest", which is $1$ way.

Sample 3
Input
31415 9
Output
779869259

Note that you must print the answer modulo $998244353$.

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