Submission #2173089


Source Code Expand

use std::io::BufRead;

const MOD: u64 = 1_000_000_007;

fn main() {
    let stdin = std::io::stdin();
    let line = stdin.lock().lines().next().unwrap().unwrap();
    let mut split = line.split(' ').map(|x| x.parse::<i32>().unwrap());
    let (n, m) = (split.next().unwrap(), split.next().unwrap() as u32);

    let factors = factorize(n.wrapping_abs() as u32);
    let mut bcmax = m;
    for &(_, count) in &factors {
        bcmax = std::cmp::max(bcmax, count + m - 1);
    }
    let bc = BinomialCoefModP::new(bcmax as u64, MOD);

    // The normative problem statement does not mention the order of
    // the factors, but the examples imply that it is significant.
    let mut ans = 0;
    let parity = if n > 0 { 0 } else { 1 };
    for i in (0..(m + 1)).filter(|i| i % 2 == parity) {
        ans = (ans + bc.get(m as u64, i as u64)) % MOD;
    }
    for (_, count) in factors {
        ans = ans * bc.get((count + m - 1) as u64, count as u64) % MOD;
    }
    println!("{}", ans);
}

fn factorize(mut n: u32) -> Vec<(u32, u32)> {
    let mut factors = Vec::new();
    let stop = (n as f64).sqrt() as u32;
    for d in std::iter::once(2).chain((1..).map(|x| x * 2 + 1)) {
        if d > stop {
            break;
        }
        let mut count = 0;
        while n % d == 0 {
            n = n / d;
            count += 1;
        }
        if count > 0 {
            factors.push((d, count));
        }
    }
    if n > 1 {
        factors.push((n, 1));
    }
    factors
}

struct BinomialCoefModP {
    num: Vec<u64>,
    denom: Vec<u64>,
    p: u64,
}

impl BinomialCoefModP {
    fn new(max_n: u64, p: u64) -> BinomialCoefModP {
        let mut num = Vec::with_capacity(max_n as usize + 1);
        num.push(1);
        for i in 0..max_n {
            let tmp = num[i as usize] * (i + 1) % p;
            num.push(tmp);
        }
        let denom = num.iter().map(|&x| Self::inv(x, p)).collect();
        BinomialCoefModP { num: num, denom: denom, p: p }
    }

    fn get(&self, n: u64, k: u64) -> u64 {
        let (n, k) = (n as usize, k as usize);
        self.num[n] * self.denom[n - k] % self.p * self.denom[k] % self.p
    }

    // Division in mod p.
    //
    // Fermat's little theorem states that
    // a^(p - 1) === 1 (mod p) if p is a prime number and
    // a is not divisible by p.
    //
    // n^(p - 2) * n === 1 (mod p)
    // This means that n^(p - 2) is the inverse of n in mod p.
    fn inv(mut n: u64, p: u64) -> u64 {
        let mut x = p - 2;
        let mut inv = 1;
        while x != 0 {
            if x & 1 != 0 {
                inv = inv * n % p;
            }
            x >>= 1;
            n = n * n % p;
        }
        inv
    }
}

Submission Info

Submission Time
Task D - 表現の自由 ( Freedom of expression )
User autocodism
Language Rust (1.15.1)
Score 100
Code Size 2784 Byte
Status AC
Exec Time 15 ms
Memory 6396 KB

Judge Result

Set Name All
Score / Max Score 100 / 100
Status
AC × 40
Set Name Test Cases
All 00_max.txt, 00_max2.txt, 00_max3.txt, 00_min.txt, 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt, 00_sample_04.txt, 01_rnd_00.txt, 01_rnd_01.txt, 01_rnd_02.txt, 01_rnd_03.txt, 01_rnd_04.txt, 01_rnd_05.txt, 01_rnd_06.txt, 01_rnd_07.txt, 01_rnd_08.txt, 01_rnd_09.txt, 01_rnd_10.txt, 01_rnd_11.txt, 01_rnd_12.txt, 01_rnd_13.txt, 01_rnd_14.txt, 01_rnd_15.txt, 01_rnd_16.txt, 01_rnd_17.txt, 01_rnd_18.txt, 01_rnd_19.txt, 01_rnd_20.txt, 01_rnd_21.txt, 01_rnd_22.txt, 01_rnd_23.txt, 01_rnd_24.txt, 01_rnd_25.txt, 01_rnd_26.txt, 01_rnd_27.txt, 01_rnd_28.txt, 01_rnd_29.txt, 04_primes_01.txt, 04_primes_02.txt
Case Name Status Exec Time Memory
00_max.txt AC 15 ms 6396 KB
00_max2.txt AC 15 ms 6396 KB
00_max3.txt AC 15 ms 6396 KB
00_min.txt AC 2 ms 4352 KB
00_sample_01.txt AC 2 ms 4352 KB
00_sample_02.txt AC 2 ms 4352 KB
00_sample_03.txt AC 2 ms 4352 KB
00_sample_04.txt AC 2 ms 4352 KB
01_rnd_00.txt AC 7 ms 4352 KB
01_rnd_01.txt AC 3 ms 4352 KB
01_rnd_02.txt AC 2 ms 4352 KB
01_rnd_03.txt AC 7 ms 4352 KB
01_rnd_04.txt AC 6 ms 4352 KB
01_rnd_05.txt AC 7 ms 4352 KB
01_rnd_06.txt AC 4 ms 4352 KB
01_rnd_07.txt AC 4 ms 4352 KB
01_rnd_08.txt AC 14 ms 4352 KB
01_rnd_09.txt AC 9 ms 4352 KB
01_rnd_10.txt AC 9 ms 4352 KB
01_rnd_11.txt AC 11 ms 4352 KB
01_rnd_12.txt AC 13 ms 4352 KB
01_rnd_13.txt AC 8 ms 4352 KB
01_rnd_14.txt AC 9 ms 4352 KB
01_rnd_15.txt AC 4 ms 4352 KB
01_rnd_16.txt AC 11 ms 4352 KB
01_rnd_17.txt AC 15 ms 6396 KB
01_rnd_18.txt AC 12 ms 4352 KB
01_rnd_19.txt AC 3 ms 4352 KB
01_rnd_20.txt AC 8 ms 4352 KB
01_rnd_21.txt AC 8 ms 4352 KB
01_rnd_22.txt AC 5 ms 4352 KB
01_rnd_23.txt AC 10 ms 4352 KB
01_rnd_24.txt AC 12 ms 4352 KB
01_rnd_25.txt AC 14 ms 4352 KB
01_rnd_26.txt AC 9 ms 4352 KB
01_rnd_27.txt AC 7 ms 4352 KB
01_rnd_28.txt AC 8 ms 4352 KB
01_rnd_29.txt AC 14 ms 4352 KB
04_primes_01.txt AC 15 ms 6396 KB
04_primes_02.txt AC 15 ms 6396 KB