Modular multiplicative inverse

考察

AtCoder

組み合わせ

ABC110-D Factorization

概要

N,MN, Mが与えられ，a1∗a2∗⋯∗aN=Ma_1 * a_2 * \cdots * a_N = M を満たすaNa_Nの組み合わせを求める.

考察

MMはaNa_Nの積で与えられるので，素因数分解して因数をNN個に振り分ける方法を考える.

MMがLL種類の因数からなるとすると，MMは素数pip_i及びべき数kik_iを用いて以下のように表される. M=p1k1∗p2k2∗⋯∗pLkLM = p_1^{k_1} * p_2^{k_2} * \cdots * p_L^{k_L}

よってこれはMMのべき数をNN個に振り分ける重複組み合わせ問題になる.

素因数pikip_i^{k_i}を重複を許してNN個に振り分ける組み合わせはNHki=(N+ki)Cki_N H k_i = (_N+k_i) C k_i で求められる. 各素因数の振り分けは独立な事象であるから，各素因数の組み合わせの積(とMOD)をとればよい.

(本来は愚直にやっても通るっぽいけど)，モジュラ逆数を用いて除算を助けてもらうことにする.

Modular multiplicative inverse

この問題では愚直にnCrを求めても間に合うが，そもそも間に合わない問題もあるらしい.
modular multiplicative inverseを利用すると，前処理O(p)O(p) クエリO(1)O(1) でmod pにおける逆元を計算できる. 逆元を用いると，mod計算など有限体上での除算が行えるようになる. (逆元使わないでこの問題解けるっぽいけど割り算とMODの順番がどうも合わなくてWA)

逆元の求め方は1より.

struct Moduloで逆元の体を定義して，new()時に a!a! 及び a−1!a^{-1}! を計算し，combでnCrを計算する.

pub struct Modulo {
    fact: Vec<usize>,
    inv_fact: Vec<usize>,
    modulo: usize
}

impl Modulo {
    pub fn new(n: usize, modulo: usize) -> Self {
        let mut fact = vec![0; n + 1];
        let mut inv = vec![0; n + 1];
        let mut inv_fact = vec![0; n + 1];
        inv[1] = 1;
        for i in 2..n + 1 {
            inv[i] = inv[modulo % i] * (modulo - modulo / i) % modulo;
        }
        fact[0] = 1;
        inv_fact[0] = 1;
        for i in 0..n {
            fact[i + 1] = fact[i] * (i + 1) % modulo;
        }
        for i in 0..n {
            inv_fact[i + 1] = inv_fact[i] * inv[i + 1] % modulo;
        }
        Modulo { fact: fact, inv_fact: inv_fact, modulo: modulo }
    }

    pub fn comb(&self, n: usize, r: usize) -> usize {
        self.fact[n] * self.inv_fact[r] %
            self.modulo * self.inv_fact[n - r] % self.modulo
    }
}

Footnotes

  1. Qiita - drken ↩

Commits

2021-01-30 22:18:1735b550aecopy md
commit 35b550ae83af4efaeadf33471c8ca8a32c1079c8
Author: koka &&gt;
Date:   Sat Jan 30 22:18:17 2021 +0900

  copy md

diff --git a/_posts/2019-08-12-abc110-d.md b/_posts/2019-08-12-abc110-d.md
new file mode 100644
index 0000000..5a475ac
--- /dev/null
+++ b/_posts/2019-08-12-abc110-d.md
@@ -0,0 +1,71 @@
+---
+title: 'Modular multiplicative inverse'
+date: 2019-08-12
+categories:
+- Competitive Programming
+tags:
+  - AtCoder
+  - 組み合わせ
+description: 考察
+---
+
+## [ABC110-D Factorization](https://atcoder.jp/contests/abc110/tasks/abc110_d)
+### 概要
+$N, M$が与えられ，$a_1 * a_2 * \cdots * a_N = M$ を満たす$a_N$の組み合わせを求める.
+### 考察
+$M$は$a_N$の積で与えられるので，素因数分解して因数を$N$個に振り分ける方法を考える.
+
+$M$が$L$種類の因数からなるとすると，$M$は素数$p_i$及びべき数$k_i$を用いて以下のように表される.
+$M = p_1^{k_1} * p_2^{k_2} * \cdots * p_L^{k_L}$
+
+よってこれは$M$のべき数を$N$個に振り分ける重複組み合わせ問題になる.
+
+素因数$p_i^{k_i}$を重複を許して$N$個に振り分ける組み合わせは$_N H k_i = (_N+k_i) C k_i$ で求められる. 各素因数の振り分けは独立な事象であるから，各素因数の組み合わせの積(とMOD)をとればよい.
+
+(本来は愚直にやっても通るっぽいけど)，モジュラ逆数を用いて除算を助けてもらうことにする.
+
+## Modular multiplicative inverse
+この問題では愚直にnCrを求めても間に合うが，そもそも間に合わない問題もあるらしい.  
+**modular multiplicative inverse**を利用すると，前処理$O(p)$ クエリ$O(1)$ でmod pにおける逆元を計算できる. 逆元を用いると，mod計算など有限体上での除算が行えるようになる.
+(逆元使わないでこの問題解けるっぽいけど割り算とMODの順番がどうも合わなくてWA)
+
+逆元の求め方は[^modinv]より.
+
+`struct Modulo`で逆元の体を定義して，`new()`時に $a!$ 及び $a^{-1}!$ を計算し，`comb`でnCrを計算する.
+
+\```rust
+pub struct Modulo {
+    fact: Vec&lt;usize&gt;,
+    inv_fact: Vec&lt;usize&gt;,
+    modulo: usize
+}
+
+impl Modulo {
+    pub fn new(n: usize, modulo: usize) -&gt; Self {
+        let mut fact = vec![0; n + 1];
+        let mut inv = vec![0; n + 1];
+        let mut inv_fact = vec![0; n + 1];
+        inv[1] = 1;
+        for i in 2..n + 1 {
+            inv[i] = inv[modulo % i] * (modulo - modulo / i) % modulo;
+        }
+        fact[0] = 1;
+        inv_fact[0] = 1;
+        for i in 0..n {
+            fact[i + 1] = fact[i] * (i + 1) % modulo;
+        }
+        for i in 0..n {
+            inv_fact[i + 1] = inv_fact[i] * inv[i + 1] % modulo;
+        }
+        Modulo { fact: fact, inv_fact: inv_fact, modulo: modulo }
+    }
+
+    pub fn comb(&self, n: usize, r: usize) -&gt; usize {
+        self.fact[n] * self.inv_fact[r] %
+            self.modulo * self.inv_fact[n - r] % self.modulo
+    }
+}
+\```
+
+
+[^modinv]: [Qiita - drken](https://qiita.com/drken/items/3b4fdf0a78e7a138cd9a#3-3-逆元の求め方の概要)