library_checker/math/
find_linear_recurrence.rs

1use competitive::prelude::*;
2#[doc(no_inline)]
3pub use competitive::{math::berlekamp_massey, num::montgomery::MInt998244353};
4
5#[verify::library_checker("find_linear_recurrence")]
6pub fn find_linear_recurrence(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, a: [MInt998244353; n]);
10    let c = berlekamp_massey(&a);
11    iter_print!(writer, c.len() - 1; @it c.iter().skip(1).map(|x| -x));
12}