berlekamp_massey

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 516)
512    pub fn kth_term(a: Vec<T>, k: usize) -> T {
513        if let Some(x) = a.get(k) {
514            return x.clone();
515        }
516        Self::from_vec(berlekamp_massey(&a)).kth_term_of_linearly_recurrence(a, k)
517    }
More examples
Hide additional examples
crates/library_checker/src/other/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}
crates/competitive/src/math/black_box_matrix.rs (line 232)
216    fn minimal_polynomial(&self) -> Vec<MInt<M>>
217    where
218        M: MIntConvert<u64>,
219    {
220        assert_eq!(self.shape().0, self.shape().1);
221        let n = self.shape().0;
222        let mut rng = Xorshift::new();
223        let b: Vec<MInt<M>> = (0..n).map(|_| MInt::from(rng.rand64())).collect();
224        let u: Vec<MInt<M>> = (0..n).map(|_| MInt::from(rng.rand64())).collect();
225        let a: Vec<MInt<M>> = (0..2 * n)
226            .scan(b, |b, _| {
227                let a = b.iter().zip(&u).fold(MInt::zero(), |s, (x, y)| s + x * y);
228                *b = self.apply(b);
229                Some(a)
230            })
231            .collect();
232        let mut p = berlekamp_massey(&a);
233        p.reverse();
234        p
235    }