結果

問題 No.1659 Product of Divisors
ユーザー phsplsphspls
提出日時 2023-01-09 15:35:19
言語 Rust
(1.77.0)
結果
WA  
実行時間 -
コード長 2,257 bytes
コンパイル時間 6,047 ms
コンパイル使用メモリ 155,704 KB
実行使用メモリ 13,288 KB
最終ジャッジ日時 2023-08-22 18:23:40
合計ジャッジ時間 7,541 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
4,716 KB
testcase_01 AC 4 ms
4,664 KB
testcase_02 WA -
testcase_03 AC 3 ms
4,576 KB
testcase_04 AC 13 ms
4,724 KB
testcase_05 AC 243 ms
5,524 KB
testcase_06 AC 4 ms
4,748 KB
testcase_07 AC 5 ms
4,596 KB
testcase_08 AC 14 ms
4,596 KB
testcase_09 WA -
testcase_10 WA -
testcase_11 AC 24 ms
4,744 KB
testcase_12 TLE -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

use std::collections::HashMap;

const MOD: usize = 1e9 as usize + 7;

fn fact_inv(size: usize) -> (Vec<usize>, Vec<usize>) {
    let mut facts = vec![0usize; size+1];
    let mut fact_invs = vec![0usize; size+1];
    let mut invs = vec![0usize; size+1];
    facts[0] = 1;
    facts[1] = 1;
    fact_invs[0] = 1;
    fact_invs[1] = 1;
    invs[1] = 1;
    for i in 2..=size {
        facts[i] = facts[i-1] * i % MOD;
        invs[i] = MOD - invs[MOD % i] * (MOD / i) % MOD;
        fact_invs[i] = fact_invs[i - 1] * invs[i] % MOD;
    }
    (facts, fact_invs)
}

fn comb(n: usize, r: usize, facts: &Vec<usize>, fact_invs: &Vec<usize>) -> usize {
    facts[n] * fact_invs[r] % MOD * fact_invs[n-r] % MOD
}

fn main() {
    let mut nk = String::new();
    std::io::stdin().read_line(&mut nk).ok();
    let nk: Vec<usize> = nk.trim().split_whitespace().map(|s| s.parse().unwrap()).collect();
    let n = nk[0];
    let k = nk[1];

    let mut cands = vec![];
    for i in 2..=(n as f64).sqrt().floor() as usize {
        if n % i == 0 {
            cands.push(i);
            if i*i != n {
                cands.push(n / i);
            }
        }
    }
    cands.push(n);
    let mut dp = HashMap::new();
    dp.insert((n, 0usize), 1usize);
    let (facts, fact_invs) = fact_inv(1e5 as usize);
    for &v in cands.iter() {
        let mut next_dp = dp.clone().to_owned();
        for (&(val, used_cnt), &cnt) in dp.iter() {
            let mut target = val;
            let mut add_cnt = 0usize;
            while target % v == 0 && used_cnt+add_cnt+1 <= k {
                add_cnt += 1;
                target /= v;
                *next_dp.entry((target, used_cnt+add_cnt)).or_insert(0usize) += comb(used_cnt+add_cnt, add_cnt, &facts, &fact_invs) * cnt % MOD;
                *next_dp.entry((target, used_cnt+add_cnt)).or_insert(0usize) %= MOD;
            }
        }
        dp = next_dp;
    }
    let mut result = 0usize;
    let limit = k.min(1e5 as usize);
    let mut nums = vec![1usize; 1+limit];
    for i in 0..limit {
        nums[i+1] = nums[i] * (k-i) % MOD;
    }
    for (&(_, used_cnt), &cnt) in dp.iter() {
        result += cnt * nums[used_cnt] % MOD * fact_invs[used_cnt] % MOD;
        result %= MOD;
    }
    println!("{}", result);
}
0