线性递推序列的连续项（Consecutive Terms of Linear Recurrent Sequence）

问题描述

一个整数序列 $(a_i)$ 满足如下线性递推关系：

$$a_i \equiv \sum_{j=1}^{d} c_j a_{i-j} \pmod{998244353}, \quad \text{对所有 } i \ge d.$$

给定初始项 $a_0, a_1, \dots, a_{d-1}$ 和系数 $c_1, c_2, \dots, c_d$，
输出从第 $k$ 项开始的连续 $M$ 项：

$$a_k, a_{k+1}, \dots, a_{k+M-1} \bmod 998244353.$$

约束条件

• $1 \leq d \leq 10^5$
• $0 \leq k \leq 10^{18}$
• $1 \leq M \leq 5 \times 10^5$
• $0 \leq a_i < 998244353$ （$0 \le i \le d-1$）
• $0 \leq c_i < 998244353$ （$1 \le i \le d$）

输入

$d\ k\ M$
$a_0\ a_1\ \cdots\ a_{d-1}$
$c_1\ c_2\ \cdots\ c_d$

输出

$a_k\ a_{k+1}\ \cdots\ a_{k+M-1}$

2 5 10
1 1
1 1

8 13 21 34 55 89 144 233 377 610

2 1 4
1 1
0 0

1 0 0 0

4 0 7
1 2 3 4
1 1 0 0

1 2 3 4 7 11 18