1. IT分享知识网首页

逆元_单位元的逆元是其本身[通俗易懂]

老牧童 • • 未分类 • 阅读 205

逆元_单位元的逆元是其本身[通俗易懂]逆元逆元在题目中的作用为了避免大整数计算，常常要求输出答案对一个数（通常为质数）取模但对于除法运算，由于取整在大部分情况下$\big\lfloor\dfrac{a}{d}\big\rfloor\ne\big\lfloor\dfrac{b}{d}\big\rfloor(mod\m)$如果能

大家好，欢迎来到IT知识分享网。

逆元

逆元在题目中的作用

为了避免大整数计算，常常要求输出答案对一个数（通常为质数）取模

但对于除法运算，由于取整在大部分情况下 \(\big\lfloor\dfrac{a}{d}\big\rfloor\ne\big\lfloor\dfrac{b}{d}\big\rfloor(mod\ m)\)

如果能让其它满足模性质的运算代替除法运算，就能解决这个问题

因此，引入乘法逆元

定义

单位元

单位元：在一个集合中，对于某种运算，如果对于任何集合的元素 \(a\)，与元素 \(e\) 运算，得到的是集合元素 \(a\) 本身，则乘元素 \(e\) 为这个运算下的单位元

  • 在加法运算中，对任意实数 \(a\)，有 \(a+e=e+a=a\)，则 单位元 \(e=0\)；
  • 在乘法运算中，对任意实数 \(a\)，有 \(a\times e=e\times a=a\)，则 单位元 \(e=1\)；

逆元

逆元：在一个集合中，对于某种运算，如果任意两个元素的运算结果等于单位元，则称这两个元素互为逆元。

  • 在加法运算中，任意实数 \(a\) 的逆元为 \(-a\)；
  • 在乘法运算中，任意非零实数 \(a\) 的逆元为 \(a^{-1}\) 或 \(\dfrac{1}{a}\)；

模意义下的单位元

前置知识：

  1. 取余运算可以转化为加法及乘法，即 \(a(mod\ m)=k\cdot m+a\)，其中 \(k\in Z\)
  2. 若运算 \(*\) （这不是乘法）的单位元为 \(e\)，则对于任意实数 \(a\) 满足 \(a*e=a\)

模意义下，在加法运算中，任意实数的单位元为 \(0\)；

证明：

令模 \(m\) 意义下的单位元为 \(e(mod\ m)\)，对于任意实数 \(a\)

\[\begin{aligned} a(mod\ m)+e(mod\ m)&=k_1\cdot m+a+k_2\cdot m +e\\ a(mod\ m)&=(k_1+k_2)\cdot m+a+e\\ k_1\cdot m+a&=(k_1+k_2)\cdot m+a+e\\ k_1\cdot m&=(k_1+k_2)\cdot m+e \end{aligned} \]

因此

\[\left\{\begin{array}{ll} k_1 & =k_{1} + k_{2} \\ e & =1 \end{array}\right. \]

模意义下，在乘法运算中，任意非零实数的单位元为 \(1\)；

证明：

令模 \(m\) 意义下的单位元为 \(e(mod\ m)\)，对于任意非零实数 \(a\)

\[\begin{aligned} a(mod\ m)\times e(mod\ m)&=(k_1\cdot m+a)\times (k_2\cdot m +e)\\ a(mod\ m)&=(k_1+k_2)\cdot m+a+e\\ k_1\cdot m+a&=(k_1k_2m+k_1e+k_2a)\cdot m+a\times e \end{aligned} \]

因此

\[\left\{\begin{array}{ll} k_1 & =k_{1} k_{2} n+k_{1} e+k_{2} a \\ e & =1 \end{array}\right. \]

模意义下的逆元

在模 \(m\) 意义下

在加法运算中，对任意实数 \(a\)，逆元为 \((-a)(mod\ m)\)

在乘法运算中，对任意非零实数 \(a\)，逆元为 \(a^{-1}(mod\ m)\)

乘法逆元满足等式 \(a\cdot a^{-1}\equiv 1(mod\ m)\)

当且仅当，乘法逆元只有在 \(gcd(a,m)=1\) 即互质的情况下存在。

证明：

令 \(x\) 是正整数 \(a\) 在模正整数 \(b\) 意义下的乘法逆元，则 \(ax\equiv 1(mod\ m)\)

同余号转等号： \(ax=by^{\prime}+1\)，其中，\(y^{\prime}\in Z\)

由于 \(y^{\prime}\) 是一个随 \(x\) 变化的值，令 \(y=-y^{\prime}\)，则：\(ax+by=1\)

令 \(g=gcd(a,b)\)，则：\(g(\dfrac{a}{g}x+\dfrac{b}{g}y)=1\)

两个整数相乘等于 \(1\)，则这两个整数一定都等于 \(1\) 或 \(-1\)

由于 \(g\) 是 \(gcd(a,b)\) 是一个正整数，则 \(gcd(a,b)=1\)

乘法逆元的求解

求解单个数的逆元- 洛谷

扩展欧几里得算法

欧几里得算法及其扩展 – Cattle_Horse

求解逆元 \(a^{-1}\) 即是求解线性同余方程 \(ax\equiv1(mod\ m)\) 的一个整数解

或者说是求解二元一次不定方程 \(ax+by=1\) 的一个整数解，其中 \(b=m,\ y\in Z\)

时间复杂度 \(O(log\ m)\)

递归

static int x = 0, y = 0;
static int exgcd(int a, int b) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int gcd = exgcd(b, a % b), t = x;
    x = y;
    y = t - a / b * y;
    return gcd;
}
static int inv(int a, int b) {
    int gcd = exgcd(a, b);
    if (gcd == 1) return (x % b + b) % b;
    System.out.println(String.format("gcd(%d, %d)!=1，无逆元", a, b));
    return -1;
}

迭代

static int x = 0, y = 0;
static int exgcd(int a, int b) {
    x = 1;
    y = 0;
    int nx = 0, ny = 1, q, t;
    while (b != 0) {
        q = a / b;
        x -= q * nx;
        t = x; x = nx; nx = t;
        y -= q * ny;
        t = y; y = ny; ny = t;
        a -= q * b;
        t = b; b = a; a = t;
    }
    // 结束后
    // a 是 gcd(a,b)
    // 如果 gcd(a,b)!=1 则 无整数解
    // 否则 x,y 是 ax+by=gcd(a,b) 的一组整数解
    return a;
}
static int inv(int a, int b) {
    int gcd = exgcd(a, b);
    if (gcd == 1) return (x % b + b) % b;
    System.out.println(String.format("gcd(%d, %d)!=1，无逆元", a, b));
    return -1;
}

欧拉定理求乘法逆元

欧拉定理：若 \(gcd(a,b)=1\)，则 \(a^{\varphi(b)}\equiv 1(mod\ b)\)

所以乘法逆元式子变为：\(ax\equiv a^{\varphi(b)}(mod\ b)\)

由于 \(a\) 是非零实数，两边同时除以 \(a\) 得：\(x\equiv a^{{\varphi(b)}-1}(mod\ b)\)

欧拉函数的计算公式为 \(\varphi(n)=n\times \prod_{i=1}^{s}(1-\dfrac{1}{p_i})\)

推导过程及计算方式见 积性函数及其筛法 – Cattle_Horse

通过分解质因子（\(O(\sqrt{b})\)）求出欧拉函数值，再通过快速幂（\(O(log\varphi(b))\)） 即可求得逆元 \(a^{-1}\)

时间复杂度为 \(O(\sqrt b+log\ \varphi(b))\)

static int getPhi(int n) {
    int ans = n;
    for (int i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
            ans = ans / i * (i - 1);
            do n /= i; while (n % i == 0);
        }
    }
    if (n > 1) ans = ans / n * (n - 1);
    return ans;
}
static long powMod(long a, int b, final long mod) {
    long ret = 1;
    while (b != 0) {
        if ((b & 1) == 1) ret = ret * a % mod;
        b >>= 1;
        a = a * a % mod;
    }
    return ret;
}
static long inv(int a, int b) {
    return powMod(a, getPhi(b) - 1, b);
}

费马小定理求乘法逆元

只能在模数为质数时才能用

费马小定理：若 \(p\) 为质数，且 \(gcd(a,p)=1\)，则有 \(a^{p-1}\equiv 1(mod\ p)\)

在模质数 \(p\) 意义下，求 非零整数 \(a\) 的乘法逆元 \(x\)

当 \(gcd(a,p)!=1\) 时，无乘法逆元

当 \(gcd(a,p)=1\) 时：

由费马小定理得：\(a^{p-1}\equiv1(mod\ p)\)

则乘法逆元式子变为：\(ax\equiv a^{p-1}(mod\ p)\)

由于 \(a\) 为非零整数，两边同时除以 \(a\)，则 \(x\equiv a^{p-2}(mod\ p)\)

使用快速幂求解

时间复杂度为 \(O(log\ p)\)

static long powMod(long a, int b, final long mod) {
    long ret = 1;
    while (b != 0) {
        if ((b & 1) == 1) ret = ret * a % mod;
        b >>= 1;
        a = a * a % mod;
    }
    return ret;
}
static long inv(int a, int b) {
    // 要求b是质数，且 gcd(a,b)=1
    return powMod(a, b - 2, b);
}

递推求乘法逆元

P3811 【模板】乘法逆元 – 洛谷

只能在模数为质数时才能用

因为在递推过程中，若模数 \(p\) 不为质数可能会出现 \(gcd(i,p)!=1\) 的情况，导致逆元无意义。

在模 \(p\)（\(p>1\)） 正整数下，\(1\) 的逆元为其本身

对于求 \(i\) 的乘法逆元 \(i^{-1}\)，令 \(k=\big\lfloor\dfrac{p}{i}\big\rfloor\)，\(r=p\%i\)，即 \(k\times i+r=p\)

则 \(k\times i+r\equiv 0(mod\ p)\)

两边同时乘以 \(i^{-1},r^{-1}\)，则 \(k\times r^{-1}+i^{-1}\equiv 0(mod\ p)\)

移项，得 \(i^{-1}\equiv -k\times r^{-1}(mod\ p)\)

即 \(i^{-1}\equiv -\big\lfloor\dfrac{p}{i}\big\rfloor\times (p\%i)^{-1}(mod\ p)\)

由于 \(p\%i<i\)，即 在求解 \(i\) 的逆元 \(i^{-1}\) 时，\(p\%i\) 的逆元 \((p\%i)^{-1}\) 已经获得。

由于 \(-\big\lfloor\dfrac{p}{i}\big\rfloor\) 导致计算的逆元会为负数，在模 \(p\) 意义下 \(-\big\lfloor\dfrac{p}{i}\big\rfloor=p-\big\lfloor\dfrac{p}{i}\big\rfloor\)

因此

当 \(i=1\) 时，\(i^{-1}=1\)

当 \(1<i<p\) 时，\(i^{-1}=(p-\big\lfloor\dfrac{p}{i}\big\rfloor)\times (p\%i)^{-1}(mod\ p)\)

// 求 [1,n] 的逆元
// 要求 n<p，且 p 是质数
static int[] invs(int n, final int p) {
    int[] inv = new int[n + 1];
    inv[1] = 1;
    for (int i = 2; i <= n; ++i) {
        inv[i] = (int) ((long) (p - p / i) * inv[p % i] % p);
    }
    return inv;
}

AC P3811 【模板】乘法逆元 – 洛谷需要高效的输入输出

阶乘与逆元

阶乘（或者叫前缀积）常用于求组合数和排列数

阶乘的逆元就是逆元的阶乘（即逆元是完全积性的）

证明见：【洛谷日报205】乘法逆元 – 知乎

在模 \(p\) 意义下，若 \(fact_i\) 表示 \(i!\) ，\(fact_i^{-1}\) 表示 \(i!\) 的乘法逆元，则

\[\begin{aligned} fact_i^{-1}&=(i+1)\times fact_{i+1}^{-1} &(1\le i<n)\\ i^{-1}&=fact_{i-1}\times fact_i^{-1}&(1\le j \le n) \end{aligned} \]

其中， \(fact_n^{-1}\) 需要手动求出，\(fact_0=1\)

时间复杂度为 \(O(n+log\ p)\)

import java.io.*;
import java.util.Scanner;

public class Main {
    static int powMod(long a, int b, final int mod) {
        long ret = 1;
        while (b != 0) {
            if ((b & 1) == 1) ret = ret * a % mod;
            b >>= 1;
            a = a * a % mod;
        }
        return (int) ret;
    }

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), p = 1000000007;
        int[] fact = new int[n + 1];
        int[] factInv = new int[n + 1];
        fact[0] = factInv[0] = 1;
        for (int i = 1; i <= n; ++i) {
            fact[i] = (int) ((long) i * fact[i - 1] % p);
        }
        factInv[n] = powMod(fact[n], p - 2, p);
        for (int i = n; i > 0; --i) {
            factInv[i - 1] = (int) ((long) factInv[i] * i % p);
        }
        for (int i = 0; i <= n; ++i) {
            System.out.println(String.format("%d, %d", fact[i], factInv[i]));
        }
    }
}

应用

下面是一个Java带模数的计算排列数和组合数的类

class Fact {
    int[] fact, factInv;
    int n;
    int MOD;

    // a 在模 b 意义下的乘法逆元
    public int inverse(int a, int b) throws IOException {
        if (a == 0) throw new IOException("0没有乘法逆元");
        int x = 1, y = 0, nx = 0, ny = 1, q, t;
        while (b != 0) {
            q = a / b;
            x -= q * nx;
            t = x; x = nx; nx = t;
            y -= q * ny;
            t = y; y = ny; ny = t;
            a -= q * b;
            t = b; b = a; a = t;
        }
        if (a == 1) return x < 0 ? x + MOD : x;
        throw new IOException("两数不互质，不存在乘法逆元");
    }

    public Fact(int n, int MOD) throws IOException {
        this.n = n;
        this.MOD = MOD;
        fact = new int[n + 1];
        factInv = new int[n + 1];
        fact[0] = factInv[0] = 1;
        for (int i = 1; i <= n; ++i) fact[i] = (int) ((long) fact[i - 1] * i % MOD);
        factInv[n] = inverse(fact[n], MOD);
        for (int i = n; i > 0; --i) factInv[i - 1] = (int) ((long) factInv[i] * i % MOD);
    }

    // n 中选 k
    public int combination(int n, int k) {
        if (n < 0 || k < 0 || n < k) return 0;
        return (int) ((long) fact[n] * factInv[k] % MOD * factInv[n - k] % MOD);
    }

    public int arrangement(int n, int k) {
        if (n < 0 || k < 0 || n < k) return 0;
        return (int) ((long) fact[n] * factInv[n - k] % MOD);
    }
}

自动取模类

下面给出两个C++版本带排列组合数的自动取模类

C++ 在与非 $modint$ 类型进行运算时，需要 $modint$ 类型在前，否则需要强制类型转换 
#include <bits/stdc++.h>
using namespace std;
template <int MOD>
struct modint {
    int val;
    static int normalize(const int& x) { return x < 0 ? x + MOD : x; }
    static constexpr int get_mod() { return MOD; }
    modint inv() const {
        assert(val);
        int a = val, b = MOD, u = 1, v = 0, t;
        while (b > 0) t = a / b, swap(a -= t * b, b), swap(u -= t * v, v);
        assert(b == 1);
        return modint(u);
    }
    modint() : val(0) {}
    modint(const int& m) : val(normalize(m)) {}
    modint(const long long& m) : val(normalize(m % MOD)) {}
    const modint& operator()() const { return val; }
    modint operator-() const { return modint(normalize(-val)); }
    bool operator==(const modint& o) { return val == o.val; }
    bool operator!=(const modint& o) const { return val != o.val; }
    bool operator<(const modint& o) { return val < o.val; }
    bool operator<=(const modint& o) const { return val <= o.val; }
    bool operator>(const modint& o) const { return val > o.val; }
    bool operator>=(const modint& o) const { return val >= o.val; }
    modint& operator+=(const modint& o) { return val = (1ll * val + o.val) % MOD, *this; }
    modint& operator-=(const modint& o) { return val = normalize(1ll * val - o.val), *this; }
    modint& operator*=(const modint& o) { return val = static_cast<int>(1ll * val * o.val % MOD), *this; }
    modint& operator/=(const modint& o) { return *this *= o.inv(); }
    modint& operator^=(const modint& o) { return val ^= o.val, *this; }
    modint& operator>>=(const modint& o) { return val >>= o.val, *this; }
    modint& operator<<=(const modint& o) { return val <<= o.val, *this; }
    modint operator-(const modint& o) const { return modint(*this) -= o; }
    modint operator+(const modint& o) const { return modint(*this) += o; }
    modint operator*(const modint& o) const { return modint(*this) *= o; }
    modint operator/(const modint& o) const { return modint(*this) /= o; }
    modint operator^(const modint& o) const { return modint(*this) ^= o; }
    modint operator>>(const modint& o) const { return modint(*this) >>= o; }
    modint operator<<(const modint& o) const { return modint(*this) <<= o; }

    friend std::istream& operator>>(std::istream& is, modint& a) {
        long long v;
        return is >> v, a.val = normalize(v % MOD), is;
    }
    friend std::ostream& operator<<(std::ostream& os, const modint& a) { return os << a.val; }
    friend std::string tostring(const modint& a) { return std::to_string(a.val); }
    friend modint qpow(const modint& a, const int& b) {
        assert(b >= 0);
        modint x = a, res = 1;
        for (int p = b; p; x *= x, p >>= 1)
            if (p & 1) res *= x;
        return res;
    }
};
using M107 = modint<1000000007>;
using M998 = modint<998244353>;

using Mint = M107;
// constexpr int mod = ...;
// using Mint = modint<mod>;
struct Fact {
    std::vector<Mint> fact, factinv;
    const int n;
    Fact(const int& _n) : n(_n), fact(_n + 1, Mint(1)), factinv(_n + 1) {
        for (int i = 1; i <= n; ++i) fact[i] = fact[i - 1] * i;
        factinv[n] = fact[n].inv();
        for (int i = n; i; --i) factinv[i - 1] = factinv[i] * i;
    }
    Mint C(const int& n, const int& k) {
        if (n < 0 || k < 0 || n < k) return 0;
        return fact[n] * factinv[k] * factinv[n - k];
    }
    Mint A(const int& n, const int& k) {
        if (n < 0 || k < 0 || n < k) return 0;
        return fact[n] * factinv[n - k];
    }
};
int main() {
    std::ios_base::sync_with_stdio(false), std::cin.tie(nullptr), std::cout.tie(nullptr);
    int n;
    cin >> n;
    Fact fact(n);
    for (int i = 0; i <= n; ++i) {
        cout << fact.fact[i] << ", " << fact.factinv[i] << endl;
    }
}
C++ By Tourist 
#include <bits/stdc++.h>
using namespace std;

template <typename T>
T inv(const T& x, const T& y) {
    assert(x != 0);
    T u = 0, v = 1, a = x, m = y, t;
    while (a != 0) {
        t = m / a;
        swap(a, m -= t * a);
        swap(u -= t * v, v);
    }
    assert(m == 1);
    if (u < 0) u += y;
    return u;
}

template <typename T>
class Modular {
public:
    using Type = typename decay<decltype(T::value)>::type;

    constexpr Modular() : value() {}
    template <typename U>
    Modular(const U& x) { value = normalize(x); }

    template <typename U>
    static Type normalize(const U& x) {
        Type v = static_cast<Type>((-mod() <= x && x < mod()) ? x : x % mod());
        if (v < 0) v += mod();
        return v;
    }

    const Type& operator()() const { return value; }
    template <typename U>
    explicit operator U() const { return static_cast<U>(value); }
    constexpr static Type mod() { return T::value; }

    Modular& operator+=(const Modular& other) {
        if ((value += other.value) >= mod()) value -= mod();
        return *this;
    }
    Modular& operator-=(const Modular& other) {
        if ((value -= other.value) < 0) value += mod();
        return *this;
    }
    template <typename U>
    Modular& operator+=(const U& other) { return *this += Modular(other); }
    template <typename U>
    Modular& operator-=(const U& other) { return *this -= Modular(other); }
    Modular& operator++() { return *this += 1; }
    Modular& operator--() { return *this -= 1; }
    Modular operator++(int) {
        Modular result(*this);
        *this += 1;
        return result;
    }
    Modular operator--(int) {
        Modular result(*this);
        *this -= 1;
        return result;
    }
    Modular operator-() const { return Modular(-value); }

    template <typename U = T>
    typename enable_if<is_same<typename Modular<U>::Type, int>::value, Modular>::type& operator*=(const Modular& rhs) {
#ifdef _WIN32
        uint64_t x = static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value);
        uint32_t xh = static_cast<uint32_t>(x >> 32), xl = static_cast<uint32_t>(x), d, m;
        asm(
            "divl %4; \n\t"
            : "=a"(d), "=d"(m)
            : "d"(xh), "a"(xl), "r"(mod()));
        value = m;
#else
        value = normalize(static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value));
#endif
        return *this;
    }
    template <typename U = T>
    typename enable_if<is_same<typename Modular<U>::Type, long long>::value, Modular>::type& operator*=(const Modular& rhs) {
        long long q = static_cast<long long>(static_cast<long double>(value) * rhs.value / mod());
        value = normalize(value * rhs.value - q * mod());
        return *this;
    }
    template <typename U = T>
    typename enable_if<!is_integral<typename Modular<U>::Type>::value, Modular>::type& operator*=(const Modular& rhs) {
        value = normalize(value * rhs.value);
        return *this;
    }

    Modular& operator/=(const Modular& other) { return *this *= Modular(inv(other.value, mod())); }

    friend const Type& abs(const Modular& x) { return x.value; }
    template <typename U>
    friend bool operator==(const Modular<U>& lhs, const Modular<U>& rhs);
    template <typename U>
    friend bool operator<(const Modular<U>& lhs, const Modular<U>& rhs);
    template <typename V, typename U>
    friend V& operator>>(V& stream, Modular<U>& number);

private:
    Type value;
};

template <typename T>
bool operator==(const Modular<T>& lhs, const Modular<T>& rhs) { return lhs.value == rhs.value; }
template <typename T, typename U>
bool operator==(const Modular<T>& lhs, U rhs) { return lhs == Modular<T>(rhs); }
template <typename T, typename U>
bool operator==(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) == rhs; }

template <typename T>
bool operator!=(const Modular<T>& lhs, const Modular<T>& rhs) { return !(lhs == rhs); }
template <typename T, typename U>
bool operator!=(const Modular<T>& lhs, U rhs) { return !(lhs == rhs); }
template <typename T, typename U>
bool operator!=(U lhs, const Modular<T>& rhs) { return !(lhs == rhs); }

template <typename T>
bool operator<(const Modular<T>& lhs, const Modular<T>& rhs) { return lhs.value < rhs.value; }

template <typename T>
Modular<T> operator+(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; }
template <typename T, typename U>
Modular<T> operator+(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) += rhs; }
template <typename T, typename U>
Modular<T> operator+(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; }

template <typename T>
Modular<T> operator-(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; }
template <typename T, typename U>
Modular<T> operator-(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) -= rhs; }
template <typename T, typename U>
Modular<T> operator-(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; }

template <typename T>
Modular<T> operator*(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; }
template <typename T, typename U>
Modular<T> operator*(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) *= rhs; }
template <typename T, typename U>
Modular<T> operator*(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; }

template <typename T>
Modular<T> operator/(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) /= rhs; }
template <typename T, typename U>
Modular<T> operator/(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) /= rhs; }
template <typename T, typename U>
Modular<T> operator/(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) /= rhs; }

template <typename T, typename U>
Modular<T> qpow(const Modular<T>& a, const U& b) {
    assert(b >= 0);
    Modular<T> x = a, res = 1;
    for (T p = b; p; x *= x, p >>= 1)
        if (p & 1) res *= x;
    return res;
}

template <typename T>
bool IsZero(const Modular<T>& number) { return number() == 0; }
template <typename T>
string to_string(const Modular<T>& number) { return to_string(number()); }

// U == std::ostream? but done this way because of fastoutput
template <typename U, typename T>
U& operator<<(U& stream, const Modular<T>& number) { return stream << number(); }

// U == std::istream? but done this way because of fastinput
template <typename U, typename T>
U& operator>>(U& stream, Modular<T>& number) {
    typename common_type<typename Modular<T>::Type, long long>::type x;
    stream >> x;
    number.value = Modular<T>::normalize(x);
    return stream;
}

// using ModType = int;
// struct VarMod { static ModType value; };
// ModType VarMod::value;
// ModType& md = VarMod::value;// for mod can change
// using Mint = Modular<VarMod>;

constexpr int md = (int)1e9 + 7;
using Mint = Modular<std::integral_constant<decay<decltype(md)>::type, md>>;

struct Fact {
    vector<Mint> fact, factinv;
    const int n;
    Fact(const int& _n) : n(_n), fact(_n + 1, Mint(1)), factinv(_n + 1) {
        for (int i = 1; i <= n; ++i) fact[i] = fact[i - 1] * i;
        factinv[n] = inv(fact[n](), md);
        for (int i = n; i; --i) factinv[i - 1] = factinv[i] * i;
    }
    Mint C(const int& n, const int& k) {
        if (n < 0 || k < 0 || n < k) return 0;
        return fact[n] * factinv[k] * factinv[n - k];
    }
    Mint A(const int& n, const int& k) {
        if (n < 0 || k < 0 || n < k) return 0;
        return fact[n] * factinv[n - k];
    }
};

int main() {
    std::ios_base::sync_with_stdio(false), std::cin.tie(nullptr), std::cout.tie(nullptr);
    int n;
    cin >> n;
    Fact fact(n);
    for (int i = 0; i <= n; ++i) {
        cout << fact.fact[i] << ", " << fact.factinv[i] << endl;
    }
}

参考资料

逆元 —— 广义化的倒数 – 知乎

【洛谷日报205】乘法逆元 – 知乎

乘法逆元 – OI Wiki

免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://yundeesoft.com/29696.html

赞 (0)
老牧童老牧童
0

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

关注微信