11310: [yosupo] Other - Consecutive Terms of Linear Recurrent Sequence
[Creator : ]
Description
An integer sequence $(a_i)$ satisfies the following linear recurrence:
$a_{i} \equiv \sum_{j=1}^{d} c_j a_{i - j} \pmod{998244353},\ i\geq d$
Given $a_0,a_1,\ldots,a_{d-1}$, print $a _ {k + i} \bmod 998244353$ for $i=0,1,\ldots,M-1$.
$a_{i} \equiv \sum_{j=1}^{d} c_j a_{i - j} \pmod{998244353},\ i\geq d$
Given $a_0,a_1,\ldots,a_{d-1}$, print $a _ {k + i} \bmod 998244353$ for $i=0,1,\ldots,M-1$.
Input
$d$ $k$ $M$
$a_0$ $a_1$ $\ldots$ $a_{d-1}$
$c_1$ $c_2$ $\ldots$ $c_d$
$a_0$ $a_1$ $\ldots$ $a_{d-1}$
$c_1$ $c_2$ $\ldots$ $c_d$
Output
$a_k$ $a_{k+1}$ $\cdots$ $a_{k+M-1}$
Constraints
- $1 \leq d \leq 10^{5}$
- $0 \leq k \leq 10^{18}$
- $1 \leq M \leq 5\times 10^{5}$
- $0 \leq a_i \lt 998244353\ (0 \leq i \leq d-1)$
- $0 \leq c_i \lt 998244353\ (1 \leq i \leq d)$
- $0 \leq k \leq 10^{18}$
- $1 \leq M \leq 5\times 10^{5}$
- $0 \leq a_i \lt 998244353\ (0 \leq i \leq d-1)$
- $0 \leq c_i \lt 998244353\ (1 \leq i \leq d)$
Sample 1 Input
2 5 10
1 1
1 1
Sample 1 Output
8 13 21 34 55 89 144 233 377 610
Sample 2 Input
2 1 4
1 1
0 0
Sample 2 Output
1 0 0 0
Sample 3 Input
4 0 7
1 2 3 4
1 1 0 0
Sample 3 Output
1 2 3 4 7 11 18