結果

問題 No.2255 Determinant Sum
コンテスト
ユーザー akakimidori
提出日時 2023-03-24 23:50:05
言語 Rust
(1.83.0 + proconio)
結果
WA  
実行時間 -
コード長 3,907 bytes
コンパイル時間 13,526 ms
コンパイル使用メモリ 378,504 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-09-18 17:43:59
合計ジャッジ時間 14,930 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 17 WA * 6
権限があれば一括ダウンロードができます
コンパイルメッセージ
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][i] == -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