fn frobenius_decomposition<M>(
a: &Matrix<AddMulOperation<MInt<M>>>,
rng: &mut Xorshift,
) -> Option<FrobeniusDecomposition<M>>Examples found in repository?
crates/competitive/src/math/mint_matrix.rs (line 49)
41 fn pow_frobenius(self, k: usize) -> Self
42 where
43 M: MIntConvert<u64>,
44 {
45 assert_eq!(self.shape.0, self.shape.1);
46 let a = self.transpose();
47 let mut rng = Xorshift::new();
48 let f = loop {
49 if let Some(f) = frobenius_decomposition(&a, &mut rng) {
50 break f;
51 }
52 };
53 let fk = f.pow(k);
54 let n = f.t.shape.0;
55 if f.blocks
56 .iter()
57 .map(|p| (p.0.len() - 1).pow(2))
58 .sum::<usize>()
59 * 4
60 <= n * n
61 {
62 let mut ft = Matrix::zeros((n, n));
63 let mut first = 0;
64 for p in &f.blocks {
65 let d = p.0.len() - 1;
66 for i in first..first + d {
67 for j in first..first + d {
68 MInt::add_scaled_assign(&mut ft[i], &f.t[j], &fk[i][j]);
69 }
70 }
71 first += d;
72 }
73 &f.t_inv * &ft
74 } else {
75 &(&f.t_inv * &fk) * &f.t
76 }
77 }