competitive::math

Function berlekamp_massey

Source 
pub fn berlekamp_massey<T>(a: &[T]) -> Vec<T>
where
    T: Zero + One + Clone + PartialEq + Add<Output = T> + Sub<Output = T> + Mul<Output = T> + Div<Output = T>,
Examples found in repository?
crates/competitive/src/math/formal_power_series/formal_power_series_impls.rs (line 486)
482    pub fn kth_term(a: Vec<T>, k: usize) -> T {
483        if let Some(x) = a.get(k) {
484            return x.clone();
485        }
486        Self::from_vec(berlekamp_massey(&a)).kth_term_of_linearly_recurrence(a, k)
487    }
More examples
Hide additional examples
crates/library_checker/src/math/find_linear_recurrence.rs (line 10)
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}