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 / 制約

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

Forum


Timelimit: 5 secs