← 返回题目列表

AtCoder · s8pc_3_g

G. 斐波那契数列之和

中文机器翻译题面 查看原题
最高分数:$1400$ 积分

问题陈述

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$。
子任务 2 [ $170$ 点 ]
  • 此子任务中的测试用例满足 $1 \le m \le 200,000$。
子任务 3 [ $230$ 点 ]
  • 此子任务中的测试用例满足 $1 \le n \le 3$。
子任务 4 [ $420$ 点 ]
  • 此子任务中的测试用例满足 $1 \le n \le 1000$。
子任务 5 [ $480$ 点 ]
  • 没有其他限制。

示例输入 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
有趣的数字。它仅包含 $1$、$4$ 和 $7$。

示例输入 3

16 30

示例输出 3

102292850
您可以计算出 $d_{16, 30} = 1,193,004,294,685$。
请不要忘记打印答案 mod $998,244,353$。
作者:square1001