結果

問題 No.2313 Product of Subsequence (hard)
ユーザー LyricalMaestro
提出日時 2026-04-26 02:51:41
言語 Rust
(1.94.0 + proconio + num + itertools)
コンパイル:
/usr/bin/rustc_custom
実行:
./target/release/main
結果
TLE  
実行時間 -
コード長 3,020 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,365 ms
コンパイル使用メモリ 203,304 KB
実行使用メモリ 46,848 KB
最終ジャッジ日時 2026-04-26 02:52:23
合計ジャッジ時間 9,057 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 10 TLE * 1 -- * 16
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

use std::collections::HashMap;
use proconio::input;

const MOD: i64 = 998244353;

fn mod_pow(mut base: i64, mut exp: i64, m: i64) -> i64 {
    let mut result = 1;
    base %= m;
    while exp > 0 {
        if exp % 2 == 1 {
            result = result * base % m;
        }
        base = base * base % m;
        exp /= 2;
    }
    result
}

fn dfs(
    k_primes_array: &Vec<(i64, usize)>,
    index: usize,
    p: i64,
    p_list: &mut Vec<usize>,
    p_to_list_map: &mut HashMap<i64, Vec<usize>>,
) {
    if index == k_primes_array.len() {
        p_to_list_map.insert(p, p_list.clone());
        return;
    }

    let (p0, value) = k_primes_array[index];
    let mut q = 1;

    for v in 0..=value {
        p_list.push(v);
        dfs(k_primes_array, index + 1, p * q, p_list, p_to_list_map);
        p_list.pop();
        q *= p0;
    }
}

fn main() {
    input! {
        n: usize,
        k_input: i64,
        a_vec: [i64; n],
    }

    let mut k = k_input;
    let base_k = k;

    if k == 1 {
        println!("{}", (mod_pow(2, n as i64, MOD) - 1 + MOD) % MOD);
        return;
    }

    // 素因数分解
    let mut k_primes: HashMap<i64, usize> = HashMap::new();
    let mut p = 2;
    while p * p <= k {
        if k % p == 0 {
            let mut cnt = 0;
            while k % p == 0 {
                k /= p;
                cnt += 1;
            }
            k_primes.insert(p, cnt);
        }
        p += 1;
    }
    if k > 1 {
        k_primes.insert(k, 1);
    }

    // 配列化 & ソート
    let mut k_primes_array: Vec<(i64, usize)> =
        k_primes.into_iter().collect();
    k_primes_array.sort_by_key(|x| x.0);

    // 状態生成
    let mut p_to_list_map: HashMap<i64, Vec<usize>> = HashMap::new();
    dfs(
        &k_primes_array,
        0,
        1,
        &mut Vec::new(),
        &mut p_to_list_map,
    );

    // Aを指数ベクトル化
    let mut a_array: Vec<Vec<usize>> = Vec::new();

    for mut a in a_vec {
        let mut vec = Vec::new();
        for &(p, value) in &k_primes_array {
            let mut x = 0;
            while a % p == 0 {
                a /= p;
                x += 1;
            }
            vec.push(std::cmp::min(value, x));
        }
        a_array.push(vec);
    }

    // DP
    let mut dp: HashMap<i64, i64> = HashMap::new();
    dp.insert(1, 1);

    for a in a_array {
        let mut new_dp = dp.clone();

        for (&key_p, &value) in dp.iter() {
            let key_list = &p_to_list_map[&key_p];

            let mut q = 1;

            for j in 0..k_primes_array.len() {
                let (p, v) = k_primes_array[j];
                let exp = std::cmp::min(v, key_list[j] + a[j]);
                q *= p.pow(exp as u32); // ← ここ高速化
            }

            *new_dp.entry(q).or_insert(0) += value;
            *new_dp.get_mut(&q).unwrap() %= MOD;
        }

        dp = new_dp;
    }

    if let Some(&ans) = dp.get(&base_k) {
        println!("{}", ans);
    } else {
        println!("0");
    }
}
0