#[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, ) -> i64 where F: Fn(&Vec>, &Vec) -> bool, { if cur_rest == 0 { return func(origin, &cur_array) as i64; } if cur_idx + cur_rest > origin.len() { return 0; } let mut ans = combinations(origin, cur_idx + 1, cur_rest, cur_array, func); if cur_rest > 0 { cur_array.push(cur_idx); ans += combinations(origin, cur_idx + 1, cur_rest - 1, cur_array, func); 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); }