#6519. 魔力环

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Imagine

题目描述

Shone 喜欢收集黑色与白色的魔力珠。

Shone 希望能够得到一个由 n 个魔力珠串成的环。不过他对普通的环并不感兴趣,因此他提出了如下的要求:

  • Shone 希望在这个环上,恰好 m 个黑色的魔力珠与 n - m 个白色的魔力珠。
  • 由于 Shone 认为黑色魔力珠不应过于密集,因此 Shone 希望这个环上不会出现一段连续的黑色魔力珠,其长度超过 k

在 Shone 的心目中,满足上述要求的环才是美妙的。

不过这样的环可能并不唯一。 Shone 想要知道共有多少种不同的环满足他所提出的要求。然而 Shone 并不喜欢计算,他希望聪明的你能够告诉他答案。

在这里,我们认为两个环是不同的,当且仅当其中一个环仅通过旋转无法得到另一个环。

输入格式

输入包含一行,在这一行中有三个非负整数 n, m, k ,其意义见题目描述。相邻的两个数用单个空格隔开。

输出格式

输出包含一行一个整数,表示满足要求的环的数量。由于答案可能过大,因此输出答案对 998, 244, 353 取模后的结果。

样例

样例输入 1

6 3 2

样例输出 1

3

样例解释 1

6 个魔力珠串成,满足其中恰好有 3 个黑色魔力珠与 3 个白色魔力珠,且不存在长度超过 2 的连续的黑色魔力珠的不同的环共有 3 种,如下图所示。

QQ20181002002120.png

下图所示的环不满足 Shone 提出的要求,因为在这个环中,存在一段连续的黑色魔力珠,长度超过了 2

QQ20181002002148.png

样例输入 2

17 8 6

样例输出 2

1421

样例输入 3

50000 20000 1

样例输出 3

683811528

数据范围与提示

所有测试点均满足 1 \leq n \leq 10^5, 1 \leq k \leq 10^5, 0 \leq m \leq 10^5 m \leq n

单个子任务的具体限制与约定见下表。

子任务 分值 限制与约定
1 3 m = 0
2 5 n \leq 4
3 8 n \leq 18
4 7 m = 2
5 19 k = 1
6 27 n m 的最大公约数不超过 2
7 31 无特殊限制