結果

問題 No.2255 Determinant Sum
ユーザー akakimidoriakakimidori
提出日時 2023-03-24 23:56:08
言語 Rust
(1.77.0 + proconio)
結果
AC  
実行時間 75 ms / 2,000 ms
コード長 3,907 bytes
コンパイル時間 13,196 ms
コンパイル使用メモリ 383,740 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-09-18 17:45:25
合計ジャッジ時間 14,698 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 1 ms
5,376 KB
testcase_02 AC 1 ms
5,376 KB
testcase_03 AC 1 ms
5,376 KB
testcase_04 AC 1 ms
5,376 KB
testcase_05 AC 1 ms
5,376 KB
testcase_06 AC 75 ms
5,376 KB
testcase_07 AC 14 ms
5,376 KB
testcase_08 AC 12 ms
5,376 KB
testcase_09 AC 13 ms
5,376 KB
testcase_10 AC 27 ms
5,376 KB
testcase_11 AC 3 ms
5,376 KB
testcase_12 AC 5 ms
5,376 KB
testcase_13 AC 4 ms
5,376 KB
testcase_14 AC 17 ms
5,376 KB
testcase_15 AC 12 ms
5,376 KB
testcase_16 AC 20 ms
5,376 KB
testcase_17 AC 18 ms
5,376 KB
testcase_18 AC 4 ms
5,376 KB
testcase_19 AC 4 ms
5,376 KB
testcase_20 AC 10 ms
5,376 KB
testcase_21 AC 6 ms
5,376 KB
testcase_22 AC 5 ms
5,376 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: type alias `Map` is never used
  --> src/main.rs:82:6
   |
82 | type Map<K, V> = BTreeMap<K, V>;
   |      ^^^
   |
   = note: `#[warn(dead_code)]` on by default

warning: type alias `Set` is never used
  --> src/main.rs:83:6
   |
83 | type Set<T> = BTreeSet<T>;
   |      ^^^

warning: type alias `Deque` is never used
  --> src/main.rs:84:6
   |
84 | type Deque<T> = VecDeque<T>;
   |      ^^^^^

ソースコード

diff # 

fn determinant(mut mat: Vec<Vec<u64>>, m: u64) -> u64 {
    let n = mat.len();
    assert!(mat.iter().all(|mat| mat.len() == n));
    let mut det = 1;
    let mut op = vec![];
    enum Operation {
        Swap(usize),
        Sub(usize, u64),
    }
    for i in (0..n).rev() {
        if let Some(x) = mat.iter().position(|mat| mat[i] != 0) {
            if i != x {
                mat.swap(i, x);
                det = m - det;
            }
            let mut a = mat.pop().unwrap();
            let mut key = a[i];
            for (j, mat) in mat.iter().enumerate() {
                let mut val = mat[i];
                while val > 0 {
                    if val < key {
                        op.push(Operation::Swap(j));
                        std::mem::swap(&mut val, &mut key);
                    }
                    let q = val / key;
                    val -= q * key;
                    op.push(Operation::Sub(j, q));
                }
            }
            for op in op.drain(..) {
                match op {
                    Operation::Swap(i) => {
                        std::mem::swap(&mut a, &mut mat[i]);
                        det = m - det;
                    },
                    Operation::Sub(k, q) => {
                        for (mat, a) in mat[k].iter_mut().zip(a.iter()).take(i + 1) {
                            *mat = (*mat + (m - q) * *a) % m;
                        }
                    },
                }
            }
            det = det * a[i] % m;
        } else {
            return 0;
        }
    }
    det % m
}
// ---------- begin scannner ----------
#[allow(dead_code)]
mod scanner {
    use std::str::FromStr;
    pub struct Scanner<'a> {
        it: std::str::SplitWhitespace<'a>,
    }
    impl<'a> Scanner<'a> {
        pub fn new(s: &'a String) -> Scanner<'a> {
            Scanner {
                it: s.split_whitespace(),
            }
        }
        pub fn next<T: FromStr>(&mut self) -> T {
            self.it.next().unwrap().parse::<T>().ok().unwrap()
        }
        pub fn next_bytes(&mut self) -> Vec<u8> {
            self.it.next().unwrap().bytes().collect()
        }
        pub fn next_chars(&mut self) -> Vec<char> {
            self.it.next().unwrap().chars().collect()
        }
        pub fn next_vec<T: FromStr>(&mut self, len: usize) -> Vec<T> {
            (0..len).map(|_| self.next()).collect()
        }
    }
}
// ---------- end scannner ----------

use std::io::Write;
use std::collections::*;

type Map<K, V> = BTreeMap<K, V>;
type Set<T> = BTreeSet<T>;
type Deque<T> = VecDeque<T>;

fn main() {
    use std::io::Read;
    let mut s = String::new();
    std::io::stdin().read_to_string(&mut s).unwrap();
    let mut sc = scanner::Scanner::new(&s);
    let out = std::io::stdout();
    let mut out = std::io::BufWriter::new(out.lock());
    run(&mut sc, &mut out);
}

fn run<W: Write>(sc: &mut scanner::Scanner, out: &mut std::io::BufWriter<W>) {
    let t: u32 = sc.next();
    for _ in 0..t {
        let mut n: usize = sc.next();
        let p: i64 = sc.next();
        let mut a = (0..n).map(|_| sc.next_vec::<i64>(n)).collect::<Vec<_>>();
        let mut mul = 1;
        while let Some(x) = (0..(n * n)).find(|x| a[x / n][x % n] == -1) {
            let (i, j) = (x / n, x % n);
            let c = (0..n).filter(|k| a[i][*k] == -1).count();
            let d = (0..n).filter(|k| a[*k][j] == -1).count();
            for a in a.iter_mut() {
                a.remove(j);
            }
            a.remove(i);
            if c + d > 2 {
                mul = 0;
            } else {
                mul = p * (p - 1) / 2 % p * mul % p;
            }
            n -= 1;
        }
        let a = a.iter().map(|a| a.iter().map(|a| *a as u64).collect()).collect::<Vec<Vec<_>>>();
        let ans = mul as u64 * determinant(a, p as u64) % p as u64;
        writeln!(out, "{}", ans).ok();
    }
}
0