← 返回题目列表

AtCoder · tkppc6_1_f

F. 青蛙和蝌蚪

中文机器翻译题面 查看原题

配点 : 500 点

問題文

N 个格子横向排列。从左边开始 i 第几格是格子 i 我们称之为。起初,所有的格子都被涂成白色。

青蛙目前在格子 1 上,并重复以下动作,试图到达格子 N 。

  • 将青蛙所在的格子称为 i ,跳到格子 i+1, i+2, \ldots, i+K 中的任意一个。但不能移动到不存在的格子或被涂成黑色的格子。

那么,听到这个的调皮蝌蚪决定将除了格子以外的几个格子涂成黑色。 1, N 我决定把除了几个以外的格子涂成黑色。

可以考虑的黑色格子选择方法有 2^{N-2} 种,但是对于所有这些方法,要计算青蛙到达格子的移动方式的数量,并且其总和 N 求到达的方法数,并求其总和 998244353 后的余数。

制約

  • 2 \leq N \leq 3 \times 10^5
  • 1 \leq K \leq N-1
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

N K

出力

计算出的总和为 998244353 后的余数 在 1 行输出。


入力例 1

4 2

出力例 1

5

蝌蚪会将格子中的几个格子涂成黑色。 2, 3 将其中的一些方格涂黑。

  • 质量 从 2 是白色且格子 3 也是白色的情况下,青蛙有 1 \rightarrow 2 \rightarrow 3 \rightarrow 4, 1 \rightarrow 2 \rightarrow 4, 1 \rightarrow 3 \rightarrow 4 可以得到第 3 种移动方式。
  • 质量 从 2 是白色且格子 3 是黑色的情况下,青蛙有 1 \rightarrow 2 \rightarrow 4 可以得到第 1 种移动方式。
  • 质量 从 2 是黑色且格子 3 是白色的情况下,青蛙有 1 \rightarrow 3 \rightarrow 4 可以得到第 1 种移动方式。
  • 质量 从 2 是黑色且格子 3 也是黑色的情况下,青蛙到格子 4 无法到达。

答案是 不超过 3 + 1 + 1 + 0 = 5 。


入力例 2

6 1

出力例 2

1

青蛙 1 只能每次移动一格,所以即使有一格被小蝌蚪涂成黑色,也会卡住。 N 无法到达。


入力例 3

64 26

出力例 3

677439847

998244353 后的余数。

原案: 夏美曾严