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 637)
630    pub fn kth_term(a: Vec<T>, k: usize) -> T
631    where
632        C: NttReuse<T = Vec<T>>,
633    {
634        if let Some(x) = a.get(k) {
635            return x.clone();
636        }
637        Self::from_vec(berlekamp_massey(&a)).kth_term_of_linearly_recurrence(a, k)
638    }
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 230)
214    fn minimal_polynomial(&self) -> Vec<MInt<M>>
215    where
216        M: MIntConvert<u64>,
217    {
218        assert_eq!(self.shape().0, self.shape().1);
219        let n = self.shape().0;
220        let mut rng = Xorshift::new();
221        let b: Vec<MInt<M>> = (0..n).map(|_| MInt::from(rng.rand64())).collect();
222        let u: Vec<MInt<M>> = (0..n).map(|_| MInt::from(rng.rand64())).collect();
223        let a: Vec<MInt<M>> = (0..2 * n)
224            .scan(b, |b, _| {
225                let a = b.iter().zip(&u).fold(MInt::zero(), |s, (x, y)| s + x * y);
226                *b = self.apply(b);
227                Some(a)
228            })
229            .collect();
230        let mut p = berlekamp_massey(&a);
231        p.reverse();
232        p
233    }