求线性递推（Find Linear Recurrence）

问题描述

给定一个整数序列 $a_0, a_1, \dots, a_{N-1}$，求一个长度最小的整数系数线性递推关系

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

其中 $0 \le c_j < 998244353$，且 $d \ge 0$ 最小。

输出该最小长度 $d$，以及系数序列 $c_1, c_2, \dots, c_d$。

约束条件

• $0 \leq N \leq 10\,000$
• $0 \leq a_i < 998244353$

输入

$N$
$a_0\ a_1\ \cdots\ a_{N-1}$

输出

$d$
$c_1\ c_2\ \cdots\ c_d$

若存在多个最小 $d$ 的解，输出任意一种。

6
3 4 6 10 18 34

2
3 998244351

6
3 4 6 10 18 36

4
3 998244351 3 998244349

0

0

5
0 0 0 0 1

5
0 0 0 0 0