library_checker/other/find_linear_recurrence.rs
1use competitive::prelude::*;
2use competitive::{math::Fps998244353, num::montgomery::MInt998244353 as M};
3
4#[verify::library_checker("find_linear_recurrence")]
5pub fn find_linear_recurrence(reader: impl Read, writer: impl Write) {
6 prepare_io!(reader, writer);
7 sc!(n, a: [M; n]);
8 let c = Fps998244353::berlekamp_massey(&a);
9 pp!(c.length() - 1; @it c.iter().skip(1).map(|x| -x));
10}