8973: [yosupo] Other - Find Linear Recurrence
[Creator : ]
Description
You are given a sequence of integers $a_0, \ldots, a_{N-1}$.
Find a sequence of integers $c_1, \ldots, c_d$ of the minimum length $d \ge 0$ such that
$0 \le c_j < 998244353$ for $1 \le j \le d$ and
$a_i \equiv \sum_{j=1}^d c_j a_{i-j} \pmod{998244353} \quad \text{for} \quad d \le i < N.$
Find a sequence of integers $c_1, \ldots, c_d$ of the minimum length $d \ge 0$ such that
$0 \le c_j < 998244353$ for $1 \le j \le d$ and
$a_i \equiv \sum_{j=1}^d c_j a_{i-j} \pmod{998244353} \quad \text{for} \quad d \le i < N.$
Input
$N$
$a_0$ $\ldots$ $a_{N-1}$
$a_0$ $\ldots$ $a_{N-1}$
Output
$d$
$c_1$ $\ldots$ $c_d$
If there are multiple answers minimizing $d$, output any of them.
$c_1$ $\ldots$ $c_d$
If there are multiple answers minimizing $d$, output any of them.
Constraints
$0 \le N \le 10^4$
$0 \le a_i < 998244353$
$0 \le a_i < 998244353$
Sample 1 Input
6
3 4 6 10 18 34
Sample 1 Output
2
3 998244351
Sample 2 Input
6
3 4 6 10 18 36
Sample 2 Output
4
3 998244351 3 998244349
Sample 3 Input
0
Sample 3 Output
0
5
0 0 0 0 1
5
0 0 0 0 0
HINT
相同题目：yosupo。