結果
問題 | No.890 移調の限られた旋法 |
ユーザー |
![]() |
提出日時 | 2019-09-20 22:01:33 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 22 ms / 2,000 ms |
コード長 | 4,482 bytes |
コンパイル時間 | 19,111 ms |
コンパイル使用メモリ | 378,548 KB |
実行使用メモリ | 13,628 KB |
最終ジャッジ日時 | 2024-09-14 17:33:16 |
合計ジャッジ時間 | 17,372 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 32 |
ソースコード
// ---------- begin ModInt ----------const MOD: u32 = 1_000_000_007;#[derive(Clone, Copy)]struct ModInt(u32);impl std::ops::Add for ModInt {type Output = ModInt;fn add(self, rhs: ModInt) -> Self::Output {let mut d = self.0 + rhs.0;if d >= MOD {d -= MOD;}ModInt(d)}}impl std::ops::AddAssign for ModInt {fn add_assign(&mut self, rhs: ModInt) {*self = *self + rhs;}}impl std::ops::Sub for ModInt {type Output = ModInt;fn sub(self, rhs: ModInt) -> Self::Output {let mut d = self.0 + MOD - rhs.0;if d >= MOD {d -= MOD;}ModInt(d)}}impl std::ops::SubAssign for ModInt {fn sub_assign(&mut self, rhs: ModInt) {*self = *self - rhs;}}impl std::ops::Mul for ModInt {type Output = ModInt;fn mul(self, rhs: ModInt) -> Self::Output {ModInt((self.0 as u64 * rhs.0 as u64 % MOD as u64) as u32)}}impl std::ops::MulAssign for ModInt {fn mul_assign(&mut self, rhs: ModInt) {*self = *self * rhs;}}impl std::ops::Neg for ModInt {type Output = ModInt;fn neg(self) -> Self::Output {ModInt(if self.0 == 0 {0} else {MOD - self.0})}}impl std::fmt::Display for ModInt {fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {write!(f, "{}", self.0)}}#[allow(dead_code)]impl ModInt {pub fn new(n: u32) -> ModInt {ModInt(n % MOD)}pub fn zero() -> ModInt {ModInt(0)}pub fn one() -> ModInt {ModInt(1)}pub fn pow(self, mut n: u32) -> ModInt {let mut t = ModInt::one();let mut s = self;while n > 0 {if n & 1 == 1 {t *= s;}s *= s;n >>= 1;}t}pub fn inv(self) -> ModInt {self.pow(MOD - 2)}pub fn comb(n: u32, k: u32) -> ModInt {if k > n {return ModInt::zero();}let k = std::cmp::min(k, n - k);let mut nu = ModInt::one();let mut de = ModInt::one();for i in 0..k {nu *= ModInt(n - i);de *= ModInt(i + 1);}nu * de.inv()}}#[allow(dead_code)]struct Precalc {inv: Vec<ModInt>,fact: Vec<ModInt>,ifact: Vec<ModInt>,}#[allow(dead_code)]impl Precalc {pub fn new(n: usize) -> Precalc {let mut inv = vec![ModInt::one(); n + 1];let mut fact = vec![ModInt::one(); n + 1];let mut ifact = vec![ModInt::one(); n + 1];for i in 2..(n + 1) {inv[i] = -inv[MOD as usize % i] * ModInt(MOD / i as u32);fact[i] = fact[i - 1] * ModInt(i as u32);ifact[i] = ifact[i - 1] * inv[i];}Precalc {inv: inv,fact: fact,ifact: ifact,}}pub fn inv(&self, n: usize) -> ModInt {self.inv[n]}pub fn fact(&self, n: usize) -> ModInt {self.fact[n]}pub fn ifact(&self, n: usize) -> ModInt {self.ifact[n]}pub fn comb(&self, n: usize, k: usize) -> ModInt {if k > n {return ModInt::zero();}self.fact[n] * self.ifact[k] * self.ifact[n - k]}}// ---------- end ModInt ----------fn gcd(a: usize, b: usize) -> usize {if b == 0 {a} else {gcd(b, a % b)}}fn run() {let mut s = String::new();std::io::stdin().read_line(&mut s).unwrap();let mut it = s.trim().split_whitespace();let n: usize = it.next().unwrap().parse().unwrap();let k: usize = it.next().unwrap().parse().unwrap();let mut g = gcd(n, k);if g == 1 {println!("0");return;}let mut d = 2;let mut p = vec![];while d * d <= g {if g % d == 0 {p.push(d);while g % d == 0 {g /= d;}}d += 1;}if g > 1 {p.push(g);}let pc = Precalc::new(n);let mut ans = ModInt::zero();let len = p.len();for i in 1..(1 << len) {let mut f = 1;let mut sign = -ModInt::one();for j in 0..len {if (i >> j) & 1 == 1 {f *= p[j];sign = -sign;}}ans += sign * pc.comb(n / f, k / f);}println!("{}", ans);}fn main() {run();}