結果

問題 No.1645 AB's abs
ユーザー Rheo TommyRheo Tommy
提出日時 2021-08-13 21:37:52
言語 Rust
(1.77.0)
結果
AC  
実行時間 69 ms / 2,000 ms
コード長 9,733 bytes
コンパイル時間 1,594 ms
コンパイル使用メモリ 188,804 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-04-14 17:08:06
合計ジャッジ時間 4,283 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 13 ms
6,940 KB
testcase_03 AC 1 ms
6,940 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 2 ms
6,944 KB
testcase_06 AC 4 ms
6,944 KB
testcase_07 AC 2 ms
6,944 KB
testcase_08 AC 18 ms
6,944 KB
testcase_09 AC 18 ms
6,944 KB
testcase_10 AC 15 ms
6,940 KB
testcase_11 AC 16 ms
6,940 KB
testcase_12 AC 16 ms
6,940 KB
testcase_13 AC 53 ms
6,944 KB
testcase_14 AC 46 ms
6,944 KB
testcase_15 AC 54 ms
6,944 KB
testcase_16 AC 52 ms
6,940 KB
testcase_17 AC 52 ms
6,944 KB
testcase_18 AC 49 ms
6,940 KB
testcase_19 AC 54 ms
6,940 KB
testcase_20 AC 46 ms
6,940 KB
testcase_21 AC 51 ms
6,944 KB
testcase_22 AC 53 ms
6,940 KB
testcase_23 AC 53 ms
6,940 KB
testcase_24 AC 54 ms
6,944 KB
testcase_25 AC 54 ms
6,940 KB
testcase_26 AC 54 ms
6,944 KB
testcase_27 AC 54 ms
6,944 KB
testcase_28 AC 54 ms
6,944 KB
testcase_29 AC 54 ms
6,940 KB
testcase_30 AC 55 ms
6,948 KB
testcase_31 AC 55 ms
6,940 KB
testcase_32 AC 56 ms
6,944 KB
testcase_33 AC 66 ms
6,940 KB
testcase_34 AC 69 ms
6,940 KB
testcase_35 AC 68 ms
6,940 KB
testcase_36 AC 67 ms
6,944 KB
testcase_37 AC 68 ms
6,944 KB
testcase_38 AC 35 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#![allow(unused_macros)]
#![allow(dead_code)]
#![allow(unused_imports)]

// # ファイル構成
// - use 宣言
// - lib モジュール
// - main 関数
// - basic モジュール
//
// 常に使うテンプレートライブラリは basic モジュール内にあります。
// 問題に応じて使うライブラリ lib モジュール内にコピペしています。
// ライブラリのコードはこちら → https://github.com/RheoTommy/at_coder
// Twitter はこちら → https://twitter.com/RheoTommy

use std::collections::*;
use std::io::{stdout, BufWriter, Write};

use crate::basic::*;
use crate::lib::*;

pub mod lib {
    pub type ModInt = StaticModInt;

    pub const MOD: i32 = MOD998244353;
    pub const MOD1000000007: i32 = 1000000007;
    pub const MOD998244353: i32 = 998244353;

    #[derive(Copy, Clone, Eq, PartialEq, Ord, PartialOrd)]
    pub struct StaticModInt(i32);

    impl std::fmt::Display for StaticModInt {
        fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
            write!(f, "{}", self.0)
        }
    }

    impl std::fmt::Debug for StaticModInt {
        fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
            write!(f, "{}", self)
        }
    }

    impl StaticModInt {
        pub fn new<T: Into<StaticModInt>>(n: T) -> Self {
            n.into()
        }
        fn new_inner(n: i32) -> Self {
            Self(n)
        }
        pub fn pow<T: Into<Int>>(self, n: T) -> Self {
            let n: Int = n.into();
            let mut n = n.0;
            assert!(n >= 0);
            let mut res = StaticModInt::new(1);
            let mut x = self;
            while n != 0 {
                if n & 1 == 1 {
                    res *= x;
                }
                n /= 2;
                x *= x;
            }
            res
        }
        pub fn inv(self) -> Self {
            self.pow((MOD - 2) as u64)
        }
    }

    impl<T: Into<Int>> From<T> for StaticModInt {
        fn from(t: T) -> Self {
            let n: Int = t.into();
            let n = (n.0 % MOD as i64) as i32;
            if n < 0 {
                Self::new_inner(n + MOD)
            } else {
                Self::new_inner(n)
            }
        }
    }

    impl<T: Into<StaticModInt>> std::ops::Add<T> for StaticModInt {
        type Output = Self;
        fn add(self, rhs: T) -> Self::Output {
            let mut tmp = self.0;
            let t: StaticModInt = rhs.into();
            tmp += t.0;
            if tmp >= MOD {
                tmp -= MOD;
            }
            debug_assert!((0..MOD).contains(&tmp));
            Self(tmp)
        }
    }

    impl<T: Into<StaticModInt>> std::ops::AddAssign<T> for StaticModInt {
        fn add_assign(&mut self, rhs: T) {
            *self = *self + rhs.into()
        }
    }

    impl<T: Into<StaticModInt>> std::ops::Sub<T> for StaticModInt {
        type Output = Self;
        fn sub(self, rhs: T) -> Self::Output {
            let mut tmp = self.0;
            let t: StaticModInt = rhs.into();
            tmp -= t.0;
            if tmp < 0 {
                tmp += MOD;
            }
            debug_assert!((0..MOD).contains(&tmp));
            Self(tmp)
        }
    }

    impl<T: Into<StaticModInt>> std::ops::SubAssign<T> for StaticModInt {
        fn sub_assign(&mut self, rhs: T) {
            *self = *self - rhs.into();
        }
    }

    impl<T: Into<StaticModInt>> std::ops::Mul<T> for StaticModInt {
        type Output = Self;
        fn mul(self, rhs: T) -> Self::Output {
            let mut tmp = self.0 as i64;
            let t: StaticModInt = rhs.into();
            tmp *= t.0 as i64;
            if tmp >= MOD as i64 {
                tmp %= MOD as i64;
            }
            let tmp = tmp as i32;
            debug_assert!((0..MOD).contains(&tmp));
            Self(tmp)
        }
    }

    impl<T: Into<StaticModInt>> std::ops::MulAssign<T> for StaticModInt {
        fn mul_assign(&mut self, rhs: T) {
            *self = *self * rhs.into();
        }
    }

    impl<T: Into<StaticModInt>> std::ops::Div<T> for StaticModInt {
        type Output = Self;
        fn div(self, rhs: T) -> Self::Output {
            let t: StaticModInt = rhs.into();
            self * t.inv()
        }
    }

    impl<T: Into<StaticModInt>> std::ops::DivAssign<T> for StaticModInt {
        fn div_assign(&mut self, rhs: T) {
            *self = *self / rhs.into();
        }
    }

    /// 二項係数を高速に計算するテーブルを作成する
    /// 構築 O(N)
    /// クエリ O(1)
    /// メモリ O(N)
    pub struct CombTable {
        fac: Vec<ModInt>,
        f_inv: Vec<ModInt>,
    }

    impl CombTable {
        /// O(N)で構築
        pub fn new<T: Into<Int>>(n: T) -> Self {
            let n: Int = n.into();
            assert!(n.0 >= 0);
            let n = n.0 as usize;
            let mut fac = vec![ModInt::new(1); n + 1];
            let mut f_inv = vec![ModInt::new(1); n + 1];
            let mut inv = vec![ModInt::new(1); n + 1];
            inv[0] = ModInt::new(0);
            for i in 2..=n {
                fac[i] = fac[i - 1] * i;
                inv[i] =
                    ModInt::new(MOD) - inv[(MOD % i as i32) as usize] * ModInt::new(MOD / i as i32);
                f_inv[i] = f_inv[i - 1] * inv[i];
            }
            Self { fac, f_inv }
        }
        /// nCkをO(1)で計算
        pub fn comb<T1: Into<Int>, T2: Into<Int>>(&self, n: T1, k: T2) -> ModInt {
            let n: Int = n.into();
            let k: Int = k.into();
            assert!(n.0 >= 0);
            assert!(k.0 >= 0);
            let n = n.0 as usize;
            let k = k.0 as usize;
            if n < k {
                return ModInt::new(0);
            }
            self.fac[n] * (self.f_inv[k] * self.f_inv[n - k])
        }
    }

    #[derive(Copy, Clone, Ord, PartialOrd, Eq, PartialEq, Debug)]
    pub struct Int(pub i64);
    macro_rules! impl_int_from {($ ($ t : ty ) ,* ) => {$ (impl From < Int > for $ t {fn from (t : Int ) -> $ t {t . 0 as $ t } } ) * } ; }
    impl_int_from!(i8, i16, i32, i64, u8, u16, u32, u64, isize, usize);
    macro_rules! impl_int_into {($ ($ t : ty ) ,* ) => {$ (impl Into < Int > for $ t {fn into (self ) -> Int {Int (self as i64 ) } } ) * } ; }
    impl_int_into!(i8, i16, i32, i64, u8, u16, u32, u64, isize, usize);
}

fn main() {
    let mut io = IO::new();
    let n = io.next_usize();
    let a = io.next_vec::<i64>(n);
    let mut dp = HashMap::new();
    *dp.entry(0).or_insert(ModInt::new(0)) += 1;

    for i in 0..n {
        let mut next = HashMap::new();
        for j in -10000..=10000 {
            let tmp = *dp.get(&j).unwrap_or(&ModInt::new(0));
            if tmp == ModInt::new(0) { continue; }
            *next.entry(j + a[i]).or_insert(ModInt::new(0)) += tmp;
            *next.entry(j - a[i]).or_insert(ModInt::new(0)) += tmp;
        }
        dp = next;
        // eprintln!("{:?}", dp);
    }

    let mut ans = ModInt::new(0);
    for j in -10000..=10000 {
        ans += *dp.get(&j).unwrap_or(&ModInt::new(0)) * j.abs();
    }
    io.println(ans);
}

pub mod basic {
    pub const U_INF: u64 = (1 << 60) + (1 << 30);
    pub const I_INF: i64 = (1 << 60) + (1 << 30);

    pub struct IO {
        iter: std::str::SplitAsciiWhitespace<'static>,
        buf: std::io::BufWriter<std::io::StdoutLock<'static>>,
    }

    impl Default for IO {
        fn default() -> Self {
            Self::new()
        }
    }

    impl IO {
        pub fn new() -> Self {
            use std::io::*;
            let mut input = String::new();
            std::io::stdin().read_to_string(&mut input).unwrap();
            let input = Box::leak(input.into_boxed_str());
            let out = Box::new(stdout());
            IO {
                iter: input.split_ascii_whitespace(),
                buf: BufWriter::new(Box::leak(out).lock()),
            }
        }
        pub fn next_str(&mut self) -> &str {
            self.iter.next().unwrap()
        }
        pub fn read<T: std::str::FromStr>(&mut self) -> T
            where
                <T as std::str::FromStr>::Err: std::fmt::Debug,
        {
            self.iter.next().unwrap().parse().unwrap()
        }
        pub fn next_usize(&mut self) -> usize {
            self.read()
        }
        pub fn next_uint(&mut self) -> u64 {
            self.read()
        }
        pub fn next_int(&mut self) -> i64 {
            self.read()
        }
        pub fn next_float(&mut self) -> f64 {
            self.read()
        }
        pub fn next_chars(&mut self) -> std::str::Chars {
            self.next_str().chars()
        }
        pub fn next_vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T>
            where
                <T as std::str::FromStr>::Err: std::fmt::Debug,
        {
            (0..n).map(|_| self.read()).collect::<Vec<_>>()
        }
        pub fn print<T: std::fmt::Display>(&mut self, t: T) {
            use std::io::Write;
            write!(self.buf, "{}", t).unwrap();
        }
        pub fn println<T: std::fmt::Display>(&mut self, t: T) {
            self.print(t);
            self.print("\n");
        }
        pub fn print_iter<T: std::fmt::Display, I: Iterator<Item=T>>(
            &mut self,
            mut iter: I,
            sep: &str,
        ) {
            if let Some(v) = iter.next() {
                self.print(v);
                for vi in iter {
                    self.print(sep);
                    self.print(vi);
                }
            }
            self.print("\n");
        }
        pub fn flush(&mut self) {
            use std::io::Write;
            self.buf.flush().unwrap();
        }
    }
}
0