#![allow(dead_code)] #![allow(unused_imports)] #![allow(unused_mut)] #![allow(unused_macros)] #![allow(unused_variables)] #![allow(non_upper_case_globals)] #![allow(non_snake_case)] // use itertools::Itertools; // use proconio::{fastout, input, marker::*}; use proconio::{input, marker::*}; use std::cmp::*; use std::collections::*; use std::num::*; use std::process::exit; const dydx: [(i64, i64); 4] = [(-1, 0), (0, 1), (1, 0), (0, -1)]; const INF: usize = usize::max_value(); const IINF: i64 = i64::max_value(); const MOD1: usize = 1_000_000_007; const MOD2: usize = 998_244_353; /// Algebra - ModInt (Zp) #[derive(Debug, PartialEq, Eq, Clone, Copy)] pub struct ModInt(pub i64, pub i64); // (residual, modulo) pub const MOD_1000000007: i64 = 1_000_000_007; pub const MOD_998244353: i64 = 998_244_353; impl ModInt { pub fn new(residual: i64, modulo: i64) -> ModInt { if residual >= modulo { ModInt(residual % modulo, modulo) } else if residual < 0 { ModInt((residual % modulo) + modulo, modulo) } else { ModInt(residual, modulo) } } pub fn unwrap(self) -> i64 { self.0 } pub fn inv(self) -> Self { fn exgcd(r0: i64, a0: i64, b0: i64, r: i64, a: i64, b: i64) -> (i64, i64, i64) { if r > 0 { exgcd(r, a, b, r0 % r, a0 - r0 / r * a, b0 - r0 / r * b) } else { (a0, b0, r0) } } let (a, _, r) = exgcd(self.0, 1, 0, self.1, 0, 1); if r != 1 { panic!("{:?} has no inverse!", self); } ModInt(((a % self.1) + self.1) % self.1, self.1) } pub fn pow(self, n: i64) -> Self { if n < 0 { self.pow(-n).inv() } else if n == 0 { ModInt(1, self.1) } else if n == 1 { self } else { let mut x = (self * self).pow(n / 2); if n % 2 == 1 { x *= self } x } } } impl std::fmt::Display for ModInt { fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result { write!(f, "{}", self.0) } } impl std::ops::Neg for ModInt { type Output = Self; fn neg(self) -> Self { if self.0 == 0 { return self; } ModInt(self.1 - self.0, self.1) } } impl std::ops::Add for ModInt { type Output = Self; fn add(self, other: i64) -> Self { ModInt::new(self.0 + other, self.1) } } impl std::ops::Add for ModInt { type Output = Self; fn add(self, other: ModInt) -> Self { self + other.0 } } impl std::ops::Add for i64 { type Output = ModInt; fn add(self, other: ModInt) -> ModInt { other + self } } impl std::ops::AddAssign for ModInt { fn add_assign(&mut self, other: i64) { self.0 = ModInt::new(self.0 + other, self.1).0; } } impl std::ops::AddAssign for ModInt { fn add_assign(&mut self, other: ModInt) { *self += other.0; } } impl std::ops::Sub for ModInt { type Output = Self; fn sub(self, other: i64) -> Self { ModInt::new(self.0 - other, self.1) } } impl std::ops::Sub for ModInt { type Output = Self; fn sub(self, other: ModInt) -> Self { self - other.0 } } impl std::ops::Sub for i64 { type Output = ModInt; fn sub(self, other: ModInt) -> ModInt { ModInt::new(self - other.0, other.1) } } impl std::ops::SubAssign for ModInt { fn sub_assign(&mut self, other: i64) { self.0 = ModInt::new(self.0 - other, self.1).0; } } impl std::ops::SubAssign for ModInt { fn sub_assign(&mut self, other: ModInt) { *self -= other.0; } } impl std::ops::Mul for ModInt { type Output = Self; fn mul(self, other: i64) -> Self { ModInt::new(self.0 * other, self.1) } } impl std::ops::Mul for ModInt { type Output = Self; fn mul(self, other: ModInt) -> Self { self * other.0 } } impl std::ops::Mul for i64 { type Output = ModInt; fn mul(self, other: ModInt) -> ModInt { other * self } } impl std::ops::MulAssign for ModInt { fn mul_assign(&mut self, other: i64) { self.0 = ModInt::new(self.0 * other, self.1).0; } } impl std::ops::MulAssign for ModInt { fn mul_assign(&mut self, other: ModInt) { *self *= other.0; } } impl std::ops::Div for ModInt { type Output = Self; fn div(self, other: ModInt) -> Self { self * other.inv() } } impl std::ops::Div for ModInt { type Output = Self; fn div(self, other: i64) -> Self { self / ModInt::new(other, self.1) } } impl std::ops::Div for i64 { type Output = ModInt; fn div(self, other: ModInt) -> ModInt { other.inv() * self } } impl std::ops::DivAssign for ModInt { fn div_assign(&mut self, other: ModInt) { self.0 = (*self / other).0; } } impl std::ops::DivAssign for ModInt { fn div_assign(&mut self, other: i64) { *self /= ModInt(other, self.1); } } #[macro_export] macro_rules! mint { ($x:expr) => { ModInt::new($x, MOD_1000000007) }; } impl std::iter::Sum for ModInt { fn sum(iter: I) -> Self where I: Iterator, { let mut r = mint!(0); for x in iter { r = r + x } r } } /// Implement (union by size) + (path compression) /// Reference: /// Zvi Galil and Giuseppe F. Italiano, /// Data structures and algorithms for disjoint set union problems pub struct Dsu { n: usize, // root node: -1 * component size // otherwise: parent parent_or_size: Vec, } impl Dsu { // 0 <= size <= 10^8 is constrained. pub fn new(size: usize) -> Self { Self { n: size, parent_or_size: vec![-1; size], } } pub fn merge(&mut self, a: usize, b: usize) -> usize { assert!(a < self.n); assert!(b < self.n); let (mut x, mut y) = (self.leader(a), self.leader(b)); if x == y { return x; } if -self.parent_or_size[x] < -self.parent_or_size[y] { std::mem::swap(&mut x, &mut y); } self.parent_or_size[x] += self.parent_or_size[y]; self.parent_or_size[y] = x as i32; x } pub fn same(&mut self, a: usize, b: usize) -> bool { assert!(a < self.n); assert!(b < self.n); self.leader(a) == self.leader(b) } pub fn leader(&mut self, a: usize) -> usize { assert!(a < self.n); if self.parent_or_size[a] < 0 { return a; } self.parent_or_size[a] = self.leader(self.parent_or_size[a] as usize) as i32; self.parent_or_size[a] as usize } pub fn size(&mut self, a: usize) -> usize { assert!(a < self.n); let x = self.leader(a); -self.parent_or_size[x] as usize } pub fn groups(&mut self) -> Vec> { let mut leader_buf = vec![0; self.n]; let mut group_size = vec![0; self.n]; for i in 0..self.n { leader_buf[i] = self.leader(i); group_size[leader_buf[i]] += 1; } let mut result = vec![Vec::new(); self.n]; for i in 0..self.n { result[i].reserve(group_size[i]); } for i in 0..self.n { result[leader_buf[i]].push(i); } result .into_iter() .filter(|x| !x.is_empty()) .collect::>>() } } fn lcm(a: usize, b: usize) -> usize { a / gcd(a, b) * b } fn gcd(a: usize, b: usize) -> usize { if b == 0 { a } else { gcd(b, a % b) } } fn nck(n: usize, k: usize) -> usize { let mut x = 1; for i in 0..k { x *= n - i; x /= 1 + i; } return x; } fn make_divisors(n: usize) -> Vec { let mut lower_divisors = vec![]; let mut upper_divisors = vec![]; let mut i = 1; while (i * i) <= n { if n % i == 0 { lower_divisors.push(i); if i != n / i { upper_divisors.push(n / i); } } i += 1; } lower_divisors.append(&mut upper_divisors); return lower_divisors; } fn prime_factorize(mut n: usize) -> Vec { let mut v = vec![]; while n % 2 == 0 { v.push(2); n /= 2; } let mut f = 3; while f * f <= n { if n % f == 0 { v.push(f); n /= f; } else { f += 2; } } if n != 1 { v.push(n); } return v; } fn is_prime(x: usize) -> bool { if x < 2 { return false; } if x == 2 || x == 3 || x == 5 { return true; } if x % 2 == 0 || x % 3 == 0 || x % 5 == 0 { return false; } let mut prime = 7.; let mut step = 4.; while prime <= (x as f64).sqrt() { if x as f64 % prime == 0. { return false; } prime += step; step = 6. - step; } return true; } fn prime_factorize_count(n: usize) -> HashMap { let mut prime_facts = prime_factorize(n); let mut facts = HashMap::::new(); for &j in &prime_facts { *facts.entry(j).or_insert(0) += 1; } return facts; } pub trait BinarySearch { fn lower_bound(&self, x: &T) -> usize; fn upper_bound(&self, x: &T) -> usize; } impl BinarySearch for [T] { fn lower_bound(&self, x: &T) -> usize { let mut low = 0; let mut high = self.len(); while low != high { let mid = (low + high) / 2; match self[mid].cmp(x) { Ordering::Less => { low = mid + 1; } Ordering::Equal | Ordering::Greater => { high = mid; } } } low } fn upper_bound(&self, x: &T) -> usize { let mut low = 0; let mut high = self.len(); while low != high { let mid = (low + high) / 2; match self[mid].cmp(x) { Ordering::Less | Ordering::Equal => { low = mid + 1; } Ordering::Greater => { high = mid; } } } low } } macro_rules! chmin { ($base:expr, $($cmps:expr),+ $(,)*) => {{ let cmp_min = min!($($cmps),+); if $base > cmp_min { $base = cmp_min; true } else { false } }}; } macro_rules! chmax { ($base:expr, $($cmps:expr),+ $(,)*) => {{ let cmp_max = max!($($cmps),+); if $base < cmp_max { $base = cmp_max; true } else { false } }}; } macro_rules! min { ($a:expr $(,)*) => {{ $a }}; ($a:expr, $b:expr $(,)*) => {{ std::cmp::min($a, $b) }}; ($a:expr, $($rest:expr),+ $(,)*) => {{ std::cmp::min($a, min!($($rest),+)) }}; } macro_rules! max { ($a:expr $(,)*) => {{ $a }}; ($a:expr, $b:expr $(,)*) => {{ std::cmp::max($a, $b) }}; ($a:expr, $($rest:expr),+ $(,)*) => {{ std::cmp::max($a, max!($($rest),+)) }}; } // nck mod p // const MAX: usize = 1000000; // const MOD: usize = MOD1; // let mut fac: Vec = vec![0; MAX + 1]; // let mut finv: Vec = vec![0; MAX + 1]; // let mut inv: Vec = vec![0; MAX + 1]; // let cominit = { // for i in 0..=1 { // fac[i] = 1; // finv[i] = 1; // } // inv[1] = 1; // for i in 2..MAX { // fac[i] = fac[i - 1] * i % MOD; // inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD; // finv[i] = finv[i - 1] * inv[i] % MOD; // } // }; // let com = |n: usize, k: usize| -> usize { // return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD; // }; macro_rules! dd { ($($a:expr),* $(,)*) => { #[cfg(debug_assertions)] eprintln!(concat!($("| ", stringify!($a), " = {:?} "),*, "|"), $(&$a),*); }; } macro_rules! p { ($x:expr) => { println!("{}", $x); }; } macro_rules! pp { ($x:expr) => { println!("{:?}", $x); }; } ////////////////////////////////////////////////////////////// // ////////////////////////////////////////////////////////////// struct Env {} impl Env { fn solve(&mut self) {} } // #[fastout] fn main() { input! { n: usize, e: [usize; n], }; let mut idx = vec![0; 15]; for mask in 0..(3_i32.pow(n as u32)) { let mut tmp = mask; for i in 0..n { idx[i] = tmp as usize % 3; tmp /= 3; } let mut a = vec![0, 0, 0]; for i in 0..n { a[idx[i]] += e[i]; } let mut set = HashSet::new(); for i in a { set.insert(i); } if set.len() == 1 { p!("Yes"); return; } } p!("No"); }