AT_arc118_f.[ARC118F] Growth Rate

给定一个正整数 $M$，以及一个包含 $N$ 项的整数序列 $A = (A_1, A_2, \ldots, A_N)$。请你计算满足以下所有条件的、包含 $N+1$ 项的整数序列 $X = (X_1, X_2, \ldots, X_{N+1})$ 的个数，并对 $998244353$ 取模。

• $1 \leq X_i \leq M$（$1 \leq i \leq N+1$）
• $A_i X_i \leq X_{i+1}$（$1 \leq i \leq N$）

输入通过标准输入给出，格式如下：

$N$ $M$ $A_1$ $A_2$ $\ldots$ $A_N$

输出满足条件的整数序列的个数，对 $998244353$ 取模。

限制条件

• $1 \leq N \leq 1000$
• $1 \leq M \leq 10^{18}$
• $1 \leq A_i \leq 10^9$
• $\prod_{i=1}^N A_i \leq M$

样例解释 1

满足条件的整数序列 $X$ 有如下 $7$ 个：

• $(1, 2, 6)$
• $(1, 2, 7)$
• $(1, 2, 8)$
• $(1, 2, 9)$
• $(1, 2, 10)$
• $(1, 3, 9)$
• $(1, 3, 10)$

样例解释 2

满足条件的整数序列 $X$ 有如下 $9$ 个：

• $(1, 3, 6)$
• $(1, 3, 7)$
• $(1, 3, 8)$
• $(1, 3, 9)$
• $(1, 3, 10)$
• $(1, 4, 8)$
• $(1, 4, 9)$
• $(1, 4, 10)$
• $(1, 5, 10)$

由 ChatGPT 4.1 翻译