最高分数:$1400$ 积分
他还定义了序列$d_1, d_2, d_3, \dots , d_n$,如下递归关系:
给定整数 $n$ 和 $m$。请计算$d_{n, m}$的值。
由于答案可能很大,因此打印答案对 $998,244,353$ 取模。
你能解决这个问题吗???
问题陈述
E869120 定义了一个序列 $a$,如下所示:- $a_1=a_2=1$, $a_{k+2}=a_{k+1}+a_k \ (k \ge 1)$
他还定义了序列$d_1, d_2, d_3, \dots , d_n$,如下递归关系:
- $d_{1, j} = a_j$
- $d_{i, j} = \sum_{k = 1}^j d_{i - 1, k} \ (i \ge 2)$
给定整数 $n$ 和 $m$。请计算$d_{n, m}$的值。
由于答案可能很大,因此打印答案对 $998,244,353$ 取模。
你能解决这个问题吗???
输入
输入由以下格式的标准输入给出。$n \quad m$
输出
- 打印 $d_{n, m}$ 模 $998,244,353$。
约束
- $1 \le n \le 200,000$
- $1 \le m \le 10^{18}$
子任务
子任务 1 [ $100$ 点 ]- 该子任务中的测试用例满足 $1 \le n, m \le 3,000$。
- 此子任务中的测试用例满足 $1 \le m \le 200,000$。
- 此子任务中的测试用例满足 $1 \le n \le 3$。
- 此子任务中的测试用例满足 $1 \le n \le 1000$。
- 没有其他限制。
示例输入 1
4 7
示例输出 1
176顺序如下:
| $d_{i, 1}$ | $d_{i, 2}$ | $d_{i, 3}$ | $d_{i, 4}$ | $d_{i, 5}$ | $d_{i, 6}$ | $d_{i, 7}$ | |
| $d_1$ | 1 | 1 | 2 | 3 | 5 | 8 | 13 |
| $d_2$ | 1 | 2 | 4 | 7 | 12 | 20 | 33 |
| $d_3$ | 1 | 3 | 7 | 14 | 26 | 46 | 79 |
| $d_4$ | 1 | 4 | 11 | 25 | 51 | 97 | 176 |
因此,答案是 $d_{4, 7} = 176$。
示例输入 2
12 20
示例输出 2
174174144
示例输入 3
16 30
示例输出 3
102292850您可以计算出 $d_{16, 30} = 1,193,004,294,685$。
请不要忘记打印答案 mod $998,244,353$。