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 |
|
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 |