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 翻译