3169 问题 G: 蓝桥杯2023年第十四届省赛真题-高塔

时间限制: 1s 内存限制: 256MB 提交: 114 解决: 25
题目描述
小蓝正在玩一个攀登高塔的游戏。高塔的层数是无限的,但游戏最多只有 n 回合。
小蓝一开始拥有 m 点能量,在每个回合都有一个值 Ai 表示小蓝的角色状态。小蓝每回合可以选择消费任意点能量 Ci (最低消费 1 点,没有上限),他在这回合将最多可以向上攀爬 Ai · Ci 层。实际攀爬的层数取决于小蓝自己在这回合的表现,不过最差也会向上爬一层。
当某回合小蓝的能量点数耗尽,那么在完成这个回合后,游戏结束。n 回合结束后,不管能量还有没有剩余,游戏都会直接结束。
给出小蓝每回合的 Ai 和自己一开始的能量点数 m。小蓝想知道有多少种不同的可能出现的游玩过程。如果小蓝在两种游玩过程中的任一对应回合花费的能量点数不同或该回合结束时所处层数不同,那么这两种游玩过程就被视为不同。
输入
输入的第一行包含两个整数 n, m,用一个空格分隔。
第二行包含 n 个整数 Ai,相邻整数之间使用一个空格分隔,表示小蓝每回合的状态值。
输出
输出一行包含一个整数表示给定条件下不同游玩过程的数量。由于答案可能很大,你只需要输出答案对 998244353 取模的结果。
样例输入
9 15
3 2 5 7 1 4 6 8 3
样例输出
392149233
提示
对于 40% 的评测用例,n ≤ 300,m ≤ 500 ;
对于所有评测用例,1 ≤ n ≤ 2 × 105,n ≤ m ≤ 1018,1 ≤ Ai ≤ 109

比赛公告

加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油