結果

問題 No.2313 Product of Subsequence (hard)
ユーザー LyricalMaestro
提出日時 2026-04-26 03:11:41
言語 Rust
(1.94.0 + proconio + num + itertools)
コンパイル:
/usr/bin/rustc_custom
実行:
./target/release/main
結果
TLE  
実行時間 -
コード長 3,118 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,393 ms
コンパイル使用メモリ 204,456 KB
実行使用メモリ 93,544 KB
最終ジャッジ日時 2026-04-26 03:12:24
合計ジャッジ時間 9,291 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge3_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;

// DFSで状態生成
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,
        mut k: i64,
        a_vec: [i64; n],
    }

    if k == 1 {
        let mut res = 1;
        for _ in 0..n {
            res = res * 2 % MOD;
        }
        println!("{}", (res - 1 + MOD) % MOD);
        return;
    }

    let base_k = k;

    // 素因数分解
    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,
    );

    // 遷移テーブル
    let mut transition: HashMap<(i64, i64), i64> = HashMap::new();

    for (&from_p, from_list) in p_to_list_map.iter() {
        for (&trans_p, trans_list) in p_to_list_map.iter() {
            let mut q = 1;
            for j in 0..k_primes_array.len() {
                let (p, max_v) = k_primes_array[j];
                let exp = std::cmp::min(max_v, from_list[j] + trans_list[j]);
                q *= p.pow(exp as u32);
            }
            transition.insert((from_p, trans_p), q);
        }
    }

    // Aを圧縮（qに変換）
    let mut a_array: Vec<i64> = Vec::new();

    for mut a in a_vec {
        let mut q = 1;
        for &(p, value) in &k_primes_array {
            let mut x = 0;
            while a % p == 0 {
                a /= p;
                x += 1;
            }
            x = std::cmp::min(value, x);
            q *= p.pow(x as u32);
        }
        a_array.push(q);
    }

    // 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 new_key = transition[&(key_p, a)];
            *new_dp.entry(new_key).or_insert(0) += value;
            *new_dp.get_mut(&new_key).unwrap() %= MOD;
        }

        dp = new_dp;
    }

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