#586286 (Rust) No.1303 Inconvenient Kingdom

提出ソース

結果

問題	No.1303 Inconvenient Kingdom
ユーザー	noshi91
提出日時	2020-11-28 11:32:45
言語	Rust (1.77.0 + proconio)
結果	AC
実行時間	13 ms / 3,000 ms
コード長	14,103 bytes
コンパイル時間	15,199 ms
コンパイル使用メモリ	401,064 KB
実行使用メモリ	6,948 KB
最終ジャッジ日時	2024-09-12 22:17:16
合計ジャッジ時間	14,590 ms
ジャッジサーバーID （参考情報）	judge2 / judge5

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 6,812 KB
testcase_01	AC	1 ms 6,812 KB
testcase_02	AC	1 ms 6,940 KB
testcase_03	AC	1 ms 6,944 KB
testcase_04	AC	1 ms 6,940 KB
testcase_05	AC	1 ms 6,940 KB
testcase_06	AC	1 ms 6,948 KB
testcase_07	AC	1 ms 6,944 KB
testcase_08	AC	1 ms 6,944 KB
testcase_09	AC	12 ms 6,940 KB
testcase_10	AC	13 ms 6,944 KB
testcase_11	AC	12 ms 6,944 KB
testcase_12	AC	12 ms 6,940 KB
testcase_13	AC	12 ms 6,944 KB
testcase_14	AC	12 ms 6,940 KB
testcase_15	AC	12 ms 6,940 KB
testcase_16	AC	13 ms 6,940 KB
testcase_17	AC	12 ms 6,940 KB
testcase_18	AC	11 ms 6,944 KB
testcase_19	AC	10 ms 6,940 KB
testcase_20	AC	10 ms 6,944 KB
testcase_21	AC	12 ms 6,940 KB
testcase_22	AC	12 ms 6,944 KB
testcase_23	AC	12 ms 6,940 KB
testcase_24	AC	12 ms 6,940 KB
testcase_25	AC	13 ms 6,944 KB
testcase_26	AC	1 ms 6,940 KB
testcase_27	AC	1 ms 6,940 KB
testcase_28	AC	1 ms 6,940 KB
testcase_29	AC	1 ms 6,944 KB
testcase_30	AC	1 ms 6,944 KB
testcase_31	AC	1 ms 6,940 KB
testcase_32	AC	1 ms 6,944 KB
testcase_33	AC	1 ms 6,944 KB
testcase_34	AC	1 ms 6,940 KB
testcase_35	AC	1 ms 6,944 KB
testcase_36	AC	1 ms 6,944 KB
testcase_37	AC	1 ms 6,940 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};

    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
    }

    /*

    Description

    T: 半環
    a: T 上の n × n 行列
    f: 消去時の係数行列

    a をガウスの消去法の手続きに従って上三角行列に変換する

    時間計算量: Θ(n^3) 回の演算と Θ(n^2) 回の f の呼び出し

    */

    use super::other::Semiring;

    pub fn manually_gaussian_elimination<T, F>(a: &mut Vec<Vec<T>>, mut f: F)
    where
        T: Semiring + Clone,
        F: FnMut([&T; 2]) -> [[T; 2]; 2],
    {
        let n = a.len();
        for a in &*a {
            assert_eq!(a.len(), n);
        }

        for col in 0..n {
            let (x, y) = a.split_at_mut(col + 1);
            let x = x.last_mut().unwrap();
            for y in y {
                let c = f([&x[col], &y[col]]);
                for (x, y) in x.iter_mut().zip(&mut *y) {
                    let new_x = c[0][0].clone() * x.clone() + c[0][1].clone() * y.clone();
                    *y = c[1][0].clone() * x.clone() + c[1][1].clone() * y.clone();
                    *x = new_x;
                }
                assert!(y[col].is_zero());
            }
        }
    }

    use super::other::Ring;
    use std::ops::Div;

    pub fn ext_gcd<T>(x: [&T; 2]) -> [[T; 2]; 2]
    where
        T: Ring + Div<Output = T> + Clone + Eq,
    {
        use std::mem::swap;

        let mut mat = [[x[0].clone(), one(), zero()], [x[1].clone(), zero(), one()]];

        let mut neg = false;
        while !mat[1][0].is_zero() {
            let q = mat[0][0].clone() / mat[1][0].clone();
            for i in 0..3 {
                mat[0][i] -= q.clone() * mat[1][i].clone();
            }
            let (x, y) = mat.split_at_mut(1);
            swap(x.last_mut().unwrap(), y.first_mut().unwrap());
            neg ^= true;
        }

        if neg {
            for i in 1..3 {
                mat[1][i] = -mat[1][i].clone();
            }
        }

        let c = [
            [mat[0][1].clone(), mat[0][2].clone()],
            [mat[1][1].clone(), mat[1][2].clone()],
        ];

        assert!((c[0][0].clone() * c[1][1].clone() - c[0][1].clone() * c[1][0].clone()) == one());

        c
    }
}

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 Linear(pub Fp, pub Fp);

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

    impl ops::AddAssign<Linear> for Linear {
        fn add_assign(&mut self, rhs: Linear) {
            self.0 += rhs.0;
            self.1 += rhs.1;
        }
    }

    impl ops::Mul<Linear> for Linear {
        type Output = Linear;
        fn mul(self, rhs: Linear) -> Linear {
            Linear(self.0 * rhs.0, self.1 * rhs.0 + self.0 * rhs.1)
        }
    }

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

    impl ops::Neg for Linear {
        type Output = Linear;
        fn neg(self) -> Linear {
            Linear(-self.0, -self.1)
        }
    }

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

    impl ops::SubAssign<Linear> for Linear {
        fn sub_assign(&mut self, rhs: Linear) {
            self.0 -= rhs.0;
            self.1 -= rhs.1;
        }
    }

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

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

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

    impl std::ops::Div for Linear {
        type Output = Self;
        fn div(self, rhs: Self) -> Self {
            if rhs.1.is_zero() {
                Linear(self.0 / rhs.0, self.1 / rhs.0)
            } else {
                Linear(self.1 / rhs.1, zero())
            }
        }
    }
}

use other::Fp;
use other::Linear;
use other::{One, Zero};

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![Linear::zero(); n - 1]; n - 1];
    for u in 0..n - 1 {
        for v in 0..n - 1 {
            if u == v {
                mat[u][v] = Linear(deg[u].into(), (n - 1 - deg[u]).into());
            } else if g[u][v] {
                mat[u][v].0 = (-1).into();
            } else {
                mat[u][v].1 = (-1).into();
            }
        }
    }

    algorithm::manually_gaussian_elimination(&mut mat, algorithm::ext_gcd);
    let mut prod = Linear::one();
    for i in 0..n - 1 {
        prod *= mat[i][i].clone();
    }
    writeln!(stdout, "0\n{}", (prod.0 + prod.1).0).unwrap();

    stdout.flush().unwrap();
}

yukicoder

結果

テストケース

ソースコード