传统题 10000ms 2048MiB

体力分配

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

体力分配

题目描述

开拓者 ["舰长, 原神好玩吗"] 最近在玩新游戏 "ZZZ", 成为了一名光荣的绳匠(下称绳斤). 他注意到, "ZZZ"与其他几款游戏 ("Honkai Impact 3", "Genshin Impact", "Honkai: Star Rail") 不同, 这个游戏里面的体力消耗方式有很多方案, 所以他对体力消耗的方式按照自己的看法记录一张表:

  1. 完成一次 A ,消耗 2 体力, 不限次.
  2. 完成一次 B, 消耗 1 体力, 限 1 次.
  3. 完成一次 C, 消耗 1 体力, 限 2 次.
  4. 完成一次 D, 消耗 4体力, 不限次.
  5. 完成一次 E, 消耗 1 体力, 限 3 次.
  6. 完成一次 F, 消耗 1 体力, 限 1 次.
  7. 完成一次 G, 消耗 3 体力, 不限次.

现在, 绳斤上线发现有 k 瓶体力药, 以及 n 点体力. 一瓶体力药水可以恢复 x 点体力. 现在他想要知道, 在拥有这么多体力的情况下, 他有多少种体力分配方案. 这个数字可能很大, 对 998244353 取模.

注意, 体力未必要用完, 比如什么都不做即消耗 0 体力也是一种方案.

数据格式

输入

第一行, 一个正整数 T. 表示测试组数.

接下来 T 行, 每行两个非负整数 n, k, x 如题意.

输出

每组测试用例一行, 输出体力分配方案的数量. 对 998244353 取模.

样例

输入

3
1 0 10
0 1 5
1 1 6

输出

5
91
204

样例解释

对于第一个测试点, 方案分别为完成[B], [C], [E], [F], [], 共5种.

数据范围及约定

1n,k,x109.1 \le n, k, x \le 10^9.

T105.T \le 10^5.

2024年暑假算法队集训赛2

未参加
状态
已结束
规则
IOI
题目
14
开始于
2024-7-22 12:00
结束于
2024-7-24 12:00
持续时间
48 小时
主持人
参赛人数
19