Find Linear Recurrence

AC一覧

Problem Statement問題文

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 < 998{,}244{,}353$ for $1 \le j \le d$ and $$a_i \equiv \sum_{j=1}^d c_j a_{i-j} \pmod{998{,}244{,}353} \quad \text{for} \quad d \le i < N.$$

Constraints制約

• $0 \le N \le 10{,}000$
• $0 \le a_i < 998{,}244{,}353$

Input入力

$N$
$a_0$ $\ldots$ $a_{N-1}$


Output出力

$d$
$c_1$ $\ldots$ $c_d$


If there are multiple answers minimizing $d$, output any of them.

Sampleサンプル

# 1

6
3 4 6 10 18 34

2
3 998244351


# 2

6
3 4 6 10 18 36

4
3 998244351 3 998244349


# 3

0


0



# 4

5
0 0 0 0 1

5
0 0 0 0 0


Timelimit: 5 secs

Before submitting, please confirm terms and conditions