haar_lib/linalg/mod_p/
adjugate.rs

1//! $\mathbb{Z} / p \mathbb{Z}$($p$は素数)上の余因子行列
2//!
3//! # Problems
4//! - <https://judge.yosupo.jp/problem/adjugate_matrix>
5use crate::{
6    linalg::mod_p::{determinant::determinant, inverse::inverse, lineq::lineq},
7    num::ff::*,
8};
9
10/// $\mathbb{Z} / p \mathbb{Z}$($p$は素数)上で余因子行列を求める。
11///
12/// **Time complexity** $O(n^3)$
13pub fn adjugate<F>(a: Vec<Vec<F::Element>>, modulo: &F) -> Vec<Vec<F::Element>>
14where
15    F: FF,
16    F::Element: FFElem,
17{
18    let n = a.len();
19    assert!(
20        a.iter().all(|r| r.len() == n),
21        "正方行列でなければならない。"
22    );
23
24    if let Some(inv) = inverse(a.clone(), modulo) {
25        let det = determinant(a, modulo);
26        inv.into_iter()
27            .map(|r| r.into_iter().map(|x| x * det).collect())
28            .collect()
29    } else {
30        let (_, s) = lineq(a.clone(), vec![modulo.zero(); n], modulo).unwrap();
31
32        if s.len() >= 2 {
33            return vec![vec![modulo.zero(); n]; n];
34        }
35
36        let b = (0..n).map(|i| (0..n).map(|j| a[j][i]).collect()).collect();
37        let (_, t) = lineq(b, vec![modulo.zero(); n], modulo).unwrap();
38
39        let i = (0..n).find(|&k| s[0][k].value() != 0).unwrap();
40        let j = (0..n).find(|&k| t[0][k].value() != 0).unwrap();
41
42        let m = {
43            let mut b = a.clone();
44            b.remove(j);
45            for r in &mut b {
46                r.remove(i);
47            }
48
49            let mut d = determinant(b, modulo);
50            if (i + j) % 2 == 1 {
51                d = -d;
52            }
53            d
54        };
55
56        let k = m / (s[0][i] * t[0][j]);
57
58        (0..n)
59            .map(|i| (0..n).map(|j| s[0][i] * t[0][j] * k).collect())
60            .collect()
61    }
62}
63
64#[cfg(test)]
65mod tests {
66    use crate::num::modint::ModIntBuilder;
67
68    use super::*;
69
70    fn check(a: Vec<Vec<i64>>, m: u32, ans: Vec<Vec<i64>>) {
71        let m = ModIntBuilder::new(m);
72        let a = a
73            .into_iter()
74            .map(|b| b.into_iter().map(|x| m.from_i64(x)).collect())
75            .collect();
76        let ans = ans
77            .into_iter()
78            .map(|b| b.into_iter().map(|x| m.from_i64(x)).collect::<Vec<_>>())
79            .collect::<Vec<_>>();
80        assert_eq!(adjugate(a, &m), ans);
81    }
82
83    #[test]
84    fn test() {
85        check(
86            vec![vec![3, 1, 4], vec![1, 5, 9], vec![2, 6, 5]],
87            998244353,
88            vec![vec![-29, 19, -11], vec![13, 7, -23], vec![-4, -16, 14]],
89        );
90    }
91}
haar_lib/linalg/mod_p/adjugate.rs

haar_lib/linalg/mod_p/
adjugate.rs
