結果

問題 No.2709 1975 Powers
ユーザー Theta
提出日時 2025-05-29 15:24:03
言語 Rust
(1.83.0 + proconio)
結果
TLE  
実行時間 -
コード長 3,603 bytes
コンパイル時間 12,964 ms
コンパイル使用メモリ 384,152 KB
実行使用メモリ 49,476 KB
最終ジャッジ日時 2025-05-29 15:24:36
合計ジャッジ時間 19,537 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 1 TLE * 2 -- * 22
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: trait `DisplayVec` is never used
  --> src/main.rs:19:7
   |
19 | trait DisplayVec<T> {
   |       ^^^^^^^^^^
   |
   = note: `#[warn(dead_code)]` on by default

ソースコード

diff # 

#[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<T> {
    fn print(&self, sep: &str);
}

impl<T> DisplayVec<T> for Vec<T>
where
    T: ToString,
{
    fn print(&self, sep: &str) {
        println!(
            "{}",
            self.iter()
                .map(std::string::ToString::to_string)
                .collect::<Vec<_>>()
                .join(sep)
        )
    }
}
#[allow(dead_code)]
fn print_chars(input_: &[char]) {
    println!("{}", &input_.iter().collect::<String>())
}
#[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<T, F>(
    origin: &Vec<Vec<T>>,
    cur_idx: usize,
    cur_rest: usize,
    cur_array: &mut Vec<usize>,
    func: &F,
) -> Vec<bool>
where
    F: Fn(&Vec<Vec<T>>, &Vec<usize>) -> bool,
{
    let mut ans = vec![];
    if cur_rest == 0 {
        ans.push(func(origin, &cur_array));
        return ans;
    }
    if cur_idx + cur_rest > 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::<Vec<i64>>()
        })
        .collect::<Vec<_>>();

    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());
}
0