#[allow(unused_imports)] use proconio::{ fastout, input, marker::{Chars, Usize1}, }; #[allow(unused_imports)] use std::cmp::{max, min}; #[allow(unused_imports)] use std::collections::{HashMap, HashSet, VecDeque}; #[allow(unused_imports)] use std::fmt::Debug; #[allow(unused_imports)] use std::iter::{Flatten, FromIterator}; #[allow(unused_imports)] use std::ops::Index; #[allow(unused_imports)] use std::vec::IntoIter; trait DisplayVec { fn print(&self, sep: &str); } impl DisplayVec for Vec where T: ToString, { fn print(&self, sep: &str) { println!( "{}", self.iter() .map(std::string::ToString::to_string) .collect::>() .join(sep) ) } } #[allow(dead_code)] fn print_chars(input_: &[char]) { println!("{}", &input_.iter().collect::()) } #[allow(dead_code)] fn ctoi(c: &char) -> i32 { *c as i32 - 48 } #[allow(dead_code)] #[allow(non_snake_case)] fn YESNO(res: bool) { if res { println!("YES") } else { println!("NO") } } #[allow(dead_code)] #[allow(non_snake_case)] fn YesNo(res: bool) { if res { println!("Yes") } else { println!("No") } } #[allow(dead_code)] fn yesno(res: bool) { if res { println!("yes") } else { println!("no") } } #[allow(unused_macros)] macro_rules! input_arrays_with_len { ($e:expr, $t:ty) => { (0..$e) .map(|_| { input! { l: u32, nums: [$t; l] } nums }) .collect_vec() }; } fn mod_pow(num: i64, index_: i64, mod_: i64) -> i64 { if index_ == 0 { return 1; } if index_ % 2 == 0 { return mod_pow((num * num) % mod_, index_ / 2, mod_); } else { return num * mod_pow(num, index_ - 1, mod_) % mod_; } } fn combinations( origin: &Vec>, cur_idx: usize, cur_rest: usize, cur_array: &mut Vec, func: &F, ) -> Vec where F: Fn(&Vec>, &Vec) -> bool, { let mut ans = vec![]; if cur_rest == 0 { ans.push(func(origin, &cur_array)); return ans; } if cur_idx == origin.len() { return ans; } let mut ans_2 = combinations(origin, cur_idx + 1, cur_rest, cur_array, func); if ans_2.len() > ans.len() { ans_2.extend(ans); ans = ans_2; } else { ans.extend(ans_2); } if cur_rest > 0 { cur_array.push(cur_idx); let mut ans_3 = combinations(origin, cur_idx + 1, cur_rest - 1, cur_array, func); if ans_3.len() > ans.len() { ans_3.extend(ans); ans = ans_3; } else { ans.extend(ans_3); } cur_array.pop(); } ans } fn main() { input! { n: usize, p: i64, q: i64, a: [i64; n], } let divisors = [10, 9, 7, 5]; let a_mod = a .iter() .map(|&a_elm| { divisors .iter() .map(move |&div_| mod_pow(div_, a_elm, p)) .collect::>() }) .collect::>(); let mut cur = vec![]; let ctr = combinations(&a_mod, 0, 4, &mut cur, &|mods, array| { let v = array .iter() .enumerate() .map(|(idx, &elm)| mods[elm as usize][idx]) .fold(0, |sum, x| (sum + x) % p); v == q }); println!("{}", ctr.into_iter().filter(|&elm| elm).count()); }