#585875 (Rust) No.1303 Inconvenient Kingdom

提出ソース

結果

問題	No.1303 Inconvenient Kingdom
ユーザー	noshi91
提出日時	2020-11-27 23:07:45
言語	Rust (1.77.0)
結果	AC
実行時間	577 ms / 3,000 ms
コード長	13,925 bytes
コンパイル時間	2,167 ms
コンパイル使用メモリ	169,100 KB
実行使用メモリ	4,380 KB
最終ジャッジ日時	2023-10-09 21:03:17
合計ジャッジ時間	13,099 ms
ジャッジサーバーID （参考情報）	judge15 / judge13

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 4,376 KB
testcase_01	AC	1 ms 4,376 KB
testcase_02	AC	1 ms 4,376 KB
testcase_03	AC	1 ms 4,376 KB
testcase_04	AC	1 ms 4,376 KB
testcase_05	AC	1 ms 4,380 KB
testcase_06	AC	1 ms 4,380 KB
testcase_07	AC	2 ms 4,376 KB
testcase_08	AC	2 ms 4,380 KB
testcase_09	AC	576 ms 4,380 KB
testcase_10	AC	572 ms 4,376 KB
testcase_11	AC	572 ms 4,380 KB
testcase_12	AC	574 ms 4,376 KB
testcase_13	AC	573 ms 4,376 KB
testcase_14	AC	577 ms 4,380 KB
testcase_15	AC	573 ms 4,376 KB
testcase_16	AC	573 ms 4,380 KB
testcase_17	AC	572 ms 4,376 KB
testcase_18	AC	573 ms 4,380 KB
testcase_19	AC	573 ms 4,380 KB
testcase_20	AC	572 ms 4,380 KB
testcase_21	AC	574 ms 4,376 KB
testcase_22	AC	572 ms 4,380 KB
testcase_23	AC	571 ms 4,376 KB
testcase_24	AC	575 ms 4,376 KB
testcase_25	AC	573 ms 4,376 KB
testcase_26	AC	2 ms 4,376 KB
testcase_27	AC	1 ms 4,380 KB
testcase_28	AC	1 ms 4,376 KB
testcase_29	AC	2 ms 4,376 KB
testcase_30	AC	1 ms 4,380 KB
testcase_31	AC	1 ms 4,376 KB
testcase_32	AC	1 ms 4,380 KB
testcase_33	AC	1 ms 4,380 KB
testcase_34	AC	1 ms 4,376 KB
testcase_35	AC	1 ms 4,376 KB
testcase_36	AC	1 ms 4,380 KB
testcase_37	AC	1 ms 4,380 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

use std::io::{self, Read as _, Write as _};

struct Scanner<'a>(std::str::SplitWhitespace<'a>);

impl<'a> Scanner<'a> {
    fn new(s: &'a str) -> Self {
        Self(s.split_whitespace())
    }

    fn next<T>(&mut self) -> T
    where
        T: std::str::FromStr,
        T::Err: std::fmt::Debug,
    {
        let s = self.0.next().expect("found EOF");
        match s.parse() {
            Ok(v) => v,
            Err(msg) => {
                println!(
                    "parse error. T = {}, s = \"{}\": {:?}",
                    std::any::type_name::<T>(),
                    s,
                    msg
                );
                panic!()
            }
        }
    }
}

pub mod algorithm {
    /*

    Description

    T: 体
    a: T 上の n × n 行列

    a の行列式を計算する。

    時間計算量: Θ(n^3) 回の演算と Θ(n) 回の除算

    オーソドックスな掃き出し法。

    */

    use super::other::Field;
    use super::other::{one, zero};
    use std::clone::Clone;

    pub fn determinant<T>(mut a: Vec<Vec<T>>) -> T
    where
        T: Field + Clone,
    {
        let n = a.len();
        for a in &a {
            assert_eq!(a.len(), n);
        }

        let mut res: T = one();

        for col in 0..n {
            match (col..n).find(|&row| !a[row][col].is_zero()) {
                None => return zero(),
                Some(row) => {
                    if row != col {
                        a.swap(col, row);
                        res = -res;
                    }
                }
            }
            {
                let c = a[col][col].clone();
                let inv_c = T::one() / c.clone();
                for a in &mut a[col][col..] {
                    *a *= inv_c.clone();
                }
                res *= c;
            }
            let (p, r) = a.split_at_mut(col + 1);
            let p = p.last().unwrap();
            for r in r {
                let c = r[col].clone();
                for (p, r) in p[col..].iter().zip(&mut r[col..]) {
                    *r -= c.clone() * p.clone();
                }
            }
        }

        res
    }

    /*

    Reference

    [1] Rote, G. (2001). Division-free algorithms for the determinant and the pfaffian:
        algebraic and combinatorial approaches.
        In Computational discrete mathematics (pp. 119-135).Springer, Berlin, Heidelberg.


    Description

    T: 可換環
    a: T 上の n×n 行列

    a の行列式を計算する。

    時間計算量: Θ(n^4)

    行列式の定義自体は除算を用いずに行われる。
    したがって、除算を使わずに行列式を計算することも興味の対象となる。

    行列式自体は有向サイクルによるカバー全体の和として解釈できるが、
    適切に定義された closed walk の集合の和を取っても
    上手く重複が相殺することが示せる。
    頂点の重複が許されたことで記憶するべき状態が大幅に削減され、
    動的計画法で効率的に計算可能になる。

    より高速なアルゴリズムも存在するらしい。

    */

    use super::other::CommutativeRing;

    pub fn division_free_determinant<T>(a: &Vec<Vec<T>>) -> T
    where
        T: CommutativeRing + Clone,
    {
        let n = a.len();
        for v in a {
            assert_eq!(v.len(), n);
        }

        let mut dp: Vec<Vec<T>> = vec![vec![zero(); n + 1]; n + 1];
        for i in 0..n + 1 {
            dp[i][i] = one();
        }

        for _ in 0..n {
            let mut nx = vec![vec![zero(); n + 1]; n + 1];
            for h in 0..n {
                for c in h..n {
                    for v in h + 1..n {
                        nx[h][v] += dp[h][c].clone() * -a[c][v].clone();
                    }
                    let t = dp[h][c].clone() * a[c][h].clone();
                    for v in h + 1..n + 1 {
                        nx[v][v] += t.clone();
                    }
                }
            }
            dp = nx;
        }

        dp[n][n].clone()
    }
}

pub mod other {
    use std::marker::Sized;
    use std::ops::{Add, AddAssign, Div, DivAssign, Mul, MulAssign, Neg, Sub, SubAssign};

    macro_rules! trait_alias {
    ($name:ident = $($t:tt)*) => {
        pub trait $name: $($t)* {}
        impl<T: $($t)*> $name for T {}
    };
}

    trait_alias! {Semigroup = Add<Output = Self> + Sized}

    trait_alias! {Band = Semigroup}

    trait_alias! {Monoid = Semigroup + Zero}

    trait_alias! {CommutativeMonoid = Monoid + AddAssign}

    trait_alias! {Group = Monoid + Neg<Output = Self>}

    trait_alias! {Abelian = Group + CommutativeMonoid + Sub<Output = Self> + SubAssign}

    trait_alias! {Semiring = CommutativeMonoid + Mul<Output = Self> + Sized + One}

    trait_alias! {Ring = Semiring + Abelian}

    trait_alias! {CommutativeRing = Ring + MulAssign}

    trait_alias! {Field = CommutativeRing + Div<Output = Self> + DivAssign}

    pub trait Zero {
        fn zero() -> Self;
        fn is_zero(&self) -> bool;
    }
    pub trait One {
        fn one() -> Self;
    }

    pub fn zero<T: Zero>() -> T {
        T::zero()
    }

    pub fn one<T: One>() -> T {
        T::one()
    }

    use std::convert::From;
    use std::iter;
    use std::ops;

    pub const P: u32 = 998244353;

    #[derive(Copy, Clone, Debug, Eq, PartialEq)]
    pub struct Fp(pub u32);

    impl Fp {
        pub fn pow(mut self, mut exp: u32) -> Fp {
            let mut res = Fp(1);
            while exp != 0 {
                if exp % 2 != 0 {
                    res *= self;
                }
                self *= self;
                exp /= 2;
            }
            res
        }
    }

    impl Zero for Fp {
        fn zero() -> Fp {
            Fp(0)
        }

        fn is_zero(&self) -> bool {
            *self == Self::zero()
        }
    }

    impl One for Fp {
        fn one() -> Fp {
            Fp(1)
        }
    }

    macro_rules! impl_from_int {
    ($(($ty:ty: $via:ty)),*) => {
        $(
            impl From<$ty> for Fp {
                fn from(x: $ty) -> Fp {
                    Fp((x as $via).rem_euclid(P as $via) as u32)
                }
            }
        )*
    };
}

    impl_from_int!(
        (i8: i32),
        (i16: i32),
        (i32: i32),
        (i64: i64),
        (u8: u32),
        (u16: u32),
        (u32: u32),
        (u64: u64),
        (isize: i64),
        (usize: u64)
    );

    impl iter::Product for Fp {
        fn product<I>(iter: I) -> Fp
        where
            I: Iterator<Item = Fp>,
        {
            iter.fold(Fp(1), |b, i| b * i)
        }
    }

    impl iter::Sum for Fp {
        fn sum<I>(iter: I) -> Fp
        where
            I: Iterator<Item = Fp>,
        {
            iter.fold(Fp(0), |b, i| b + i)
        }
    }

    impl ops::Add<Fp> for Fp {
        type Output = Fp;
        fn add(mut self, rhs: Fp) -> Fp {
            self += rhs;
            self
        }
    }

    impl ops::AddAssign<Fp> for Fp {
        fn add_assign(&mut self, rhs: Fp) {
            self.0 += rhs.0;
            if self.0 >= P {
                self.0 -= P;
            }
        }
    }

    impl ops::Div for Fp {
        type Output = Fp;
        fn div(mut self, rhs: Fp) -> Fp {
            assert_ne!(rhs.0, 0);
            self /= rhs;
            self
        }
    }

    impl ops::DivAssign for Fp {
        fn div_assign(&mut self, rhs: Fp) {
            assert_ne!(rhs.0, 0);
            *self *= rhs.pow(P - 2);
        }
    }

    impl ops::Mul<Fp> for Fp {
        type Output = Fp;
        fn mul(self, rhs: Fp) -> Fp {
            Fp((self.0 as u64 * rhs.0 as u64 % P as u64) as u32)
        }
    }

    impl ops::Mul<usize> for Fp {
        type Output = Fp;
        fn mul(self, rhs: usize) -> Fp {
            self * Fp::from(rhs)
        }
    }

    impl ops::MulAssign<Fp> for Fp {
        fn mul_assign(&mut self, rhs: Fp) {
            *self = *self * rhs;
        }
    }

    impl ops::Neg for Fp {
        type Output = Fp;
        fn neg(self) -> Fp {
            Fp(match self.0 {
                0 => 0,
                s => P - s,
            })
        }
    }

    impl ops::Sub<Fp> for Fp {
        type Output = Fp;
        fn sub(mut self, rhs: Fp) -> Fp {
            self -= rhs;
            self
        }
    }

    impl ops::SubAssign<Fp> for Fp {
        fn sub_assign(&mut self, rhs: Fp) {
            if self.0 < rhs.0 {
                self.0 += P;
            }
            self.0 -= rhs.0;
        }
    }

    #[derive(Clone, Debug, Eq, PartialEq)]
    pub struct Deg2(pub [Fp; 3]);

    impl ops::Add<Deg2> for Deg2 {
        type Output = Deg2;
        fn add(mut self, rhs: Deg2) -> Deg2 {
            self += rhs;
            self
        }
    }

    impl ops::AddAssign<Deg2> for Deg2 {
        fn add_assign(&mut self, rhs: Deg2) {
            for i in 0..3 {
                self.0[i] += rhs.0[i];
            }
        }
    }

    impl ops::Mul<Deg2> for Deg2 {
        type Output = Deg2;
        fn mul(self, rhs: Deg2) -> Deg2 {
            let mut ret = [Fp(0), Fp(0), Fp(0)];
            for i in 0..3 {
                for j in 0..3 - i {
                    ret[i + j] += self.0[i] * rhs.0[j];
                }
            }
            Deg2(ret)
        }
    }

    impl ops::MulAssign<Deg2> for Deg2 {
        fn mul_assign(&mut self, rhs: Deg2) {
            let mut ret = [Fp(0), Fp(0), Fp(0)];
            for i in 0..3 {
                for j in 0..3 - i {
                    ret[i + j] += self.0[i] * rhs.0[j];
                }
            }
            self.0 = ret;
        }
    }

    impl ops::Neg for Deg2 {
        type Output = Deg2;
        fn neg(mut self) -> Deg2 {
            for i in 0..3 {
                self.0[i] = -self.0[i];
            }
            self
        }
    }

    impl ops::Sub<Deg2> for Deg2 {
        type Output = Deg2;
        fn sub(mut self, rhs: Deg2) -> Deg2 {
            self -= rhs;
            self
        }
    }

    impl ops::SubAssign<Deg2> for Deg2 {
        fn sub_assign(&mut self, rhs: Deg2) {
            for i in 0..3 {
                self.0[i] -= rhs.0[i];
            }
        }
    }

    impl Zero for Deg2 {
        fn zero() -> Self {
            Self([Fp(0), Fp(0), Fp(0)])
        }

        fn is_zero(&self) -> bool {
            self == &zero()
        }
    }

    impl One for Deg2 {
        fn one() -> Self {
            Self([Fp(1), Fp(0), Fp(0)])
        }
    }
}

use other::Deg2;
use other::Fp;

fn main() {
    let mut stdin = String::new();
    std::io::stdin().read_to_string(&mut stdin).unwrap();
    let mut sc = Scanner::new(&stdin);
    let stdout = io::stdout();
    let mut stdout = io::BufWriter::new(stdout.lock());
    // writeln!(stdout, "");

    let n: usize = sc.next();
    let m: usize = sc.next();

    let mut g = vec![vec![false; n]; n];
    let mut deg = vec![0usize; n];

    for _ in 0..m {
        let u: usize = sc.next::<usize>() - 1;
        let v: usize = sc.next::<usize>() - 1;
        g[u][v] = true;
        g[v][u] = true;
        deg[u] += 1;
        deg[v] += 1;
    }

    let mut used = vec![false; n];
    let mut size_list = vec![];
    let mut part_prod = Fp(1);

    let mut is_connected = false;

    for root in 0..n {
        if used[root] {
            continue;
        }
        let mut v_list = vec![];
        let mut stack = vec![root];
        while let Some(v) = stack.pop() {
            if used[v] {
                continue;
            }
            used[v] = true;
            v_list.push(v);
            for (u, &f) in g[v].iter().enumerate() {
                if f {
                    stack.push(u);
                }
            }
        }
        let len = v_list.len();
        size_list.push(len);
        let mut mat = vec![vec![Fp(0); len - 1]; len - 1];
        for (i, &u) in v_list[1..].iter().enumerate() {
            for (j, &v) in v_list[1..].iter().enumerate() {
                if i == j {
                    mat[i][j] = Fp(deg[u] as u32);
                } else if g[u][v] {
                    mat[i][j] = -Fp(1);
                }
            }
        }
        part_prod *= algorithm::determinant(mat);
        if len == n {
            is_connected = true;
            break;
        }
    }

    if !is_connected {
        use std::cmp::Reverse;
        let mut ans = (n as u64).pow(2);
        for &s in &size_list {
            ans -= (s as u64).pow(2);
        }
        size_list.sort_unstable_by_key(|&k| Reverse(k));
        ans -= (size_list[0] as u64) * (size_list[1] as u64) * 2;

        let max = size_list[0];
        let max_count = size_list.iter().filter(|&&s| s == max).count();
        let max = Fp(max as u32);
        if max_count >= 2 {
            let max_count = Fp(max_count as u32);
            part_prod *= (max * max_count).pow(2) - max.pow(2) * max_count;
            part_prod /= Fp(2);
        } else {
            let second = size_list[1];
            let sec_count = size_list.iter().filter(|&&s| s == second).count();
            let sec_count = Fp(sec_count as u32);
            part_prod *= max * Fp(second as u32) * sec_count;
        }
        writeln!(stdout, "{}\n{}", ans, part_prod.0).unwrap();
        stdout.flush().unwrap();
        return;
    }

    let mut mat = vec![vec![Deg2([Fp(0), Fp(0), Fp(0)]); n]; n];
    for u in 0..n {
        for v in 0..n {
            if u == v {
                mat[u][v].0[0] = Fp(deg[u] as u32);
                mat[u][v].0[1] = Fp(1);
            } else if g[u][v] {
                mat[u][v].0[0] = -Fp(1);
            }
        }
    }

    let temp = algorithm::division_free_determinant(&mat).0[2];
    let part_prod = part_prod + temp - part_prod * Fp(n as u32 - 1);
    writeln!(stdout, "0\n{}", part_prod.0).unwrap();

    stdout.flush().unwrap();
}

yukicoder

結果

テストケース

ソースコード