[Modint] Decoding the AtCoder Library ~ Implementation in Python ~

0. Introduction

The official AtCoder algorithm collection AtCoder Library (** ACL **) was released on September 7, 2020. I thought it was a good opportunity because most of the algorithms included in ACL were new to me, so I did everything from studying algorithms to implementing them in Python.

In this article we will look at ** Modint **.

Target readers

Referenced

Python documentation. https://docs.python.org/ja/3/reference/datamodel.html

1. What is Modint?

Modint is a ** structure that automatically takes too much **.

1.1. It's so beautiful with Modint

As an example, let's look at the case where $ (a \ times b + c --d) / e $ is divided by $ m $ to find the remainder.

Normal case

In general, be careful of overflows and negative remainders

(((((a * b) % m + c) % m - d + m) % m) * modular_inverse(e, m) % m
# modular_inverse(e, m)Is the inverse element of e modulo m

Write like this.

When using Modint

If you cast a to Modint type

a = Modint(a, mod=m)
(a * b + c - d) / e

Can be written in a natural way.

1.2. Advantages and disadvantages

As a ** merit ** of using Modint

Such will be considered. On the other hand, as a ** disadvantage **

Such will be considered.

1.3. Knowledge required for completion

To make a Modint that can be used in contests, etc.

  1. Knowledge of ** mathematics ** about "operations in the mod world"
  2. Make a minimum working Modint ** Programming ** knowledge
  3. Knowledge of ** language ** to make a practical Modint

Is required. The third knowledge to make a practical Modint is

These are things that are strongly language-dependent, and at the same time, I think that each individual is particular about it, so ** I will not cover it in this article. ** **

In this article, we aim to "** create a modint that works at a minimum **", and explain the first and second knowledge required for that purpose. And finally, I will post an implementation example in Python.

2. Arithmetic in the mod world

Let's look at the calculation method in the mod world.

2.1. Confirmation of basic matters

When the integers $ a, b $ divided by the natural number $ m $ are equal, it is said that "$ a $ and $ b $ are congruent, modulo $ m $".

a \equiv b \pmod{m}

Write. For example, when 3 is the law

\begin{aligned}
4 &= 1 \cdot 3 + 1\\
13 &= 4 \cdot 3 + 1
\end{aligned}

So

4 \equiv 13 \pmod{3}

is. Also, in this article, "too much $ a $ divided by $ m $"

a \% m

I will write. In other words

\begin{aligned}
5 \% 3 = 2\\
13 \% 3 = 1
\end{aligned}

It will be. More specifically, using the ** floor function ** ($ \ lfloor x \ rfloor $), which is ** rounding to negative infinity **

a \% m := a - m \left\lfloor \frac{a}{m} \right\rfloor

I will decide. This ensures that the remainder of dividing by the natural number $ m $ is always $ 0 \ leq a % m <m $, even if the integer $ a $ is negative.

Example)

\begin{aligned}
-4 \% 3 &= (-4) - 3 \left\lfloor \frac{-4}{3} \right\rfloor\\[2ex]
&= (-4) - 3(-2)\\
&= 2
\end{aligned}

2.2. Addition

It shows that the following relationship holds for addition (addition).


(a + b) \% m = ((a \% m) + (b \% m)) \% m

(Proof)

The operation that takes too much is calculated according to the definition of "%".

(Left side) = (a + b) - m \left\lfloor \frac{a + b}{m} \right\rfloor

on the other hand,

\begin{aligned}
(right side) &= \left(a - m \left\lfloor\frac{a}{m} \right\rfloor + b - m \left\lfloor \frac{b}{m} \right\rfloor\right) \% m\\[3ex]
&= \left\{a + b - m \left(\left\lfloor \frac{a}{m} \right\rfloor +  \left\lfloor \frac{b}{m} \right\rfloor\right)\right\} \% m\\[3ex]
&= a + b - m \left(\left\lfloor \frac{a}{m} \right\rfloor +  \left\lfloor \frac{b}{m} \right\rfloor\right) - m \left\lfloor \frac{a + b - m \left(\left\lfloor \frac{a}{m} \right\rfloor +  \left\lfloor \frac{b}{m} \right\rfloor\right)}{m}\right\rfloor
\end{aligned}

here,

\frac{m \left(\left\lfloor \frac{a}{m} \right\rfloor +  \left\lfloor \frac{b}{m} \right\rfloor\right)}{m}

Is an integer

\begin{aligned}
(right side) &= a + b - m \left(\left\lfloor \frac{a}{m} \right\rfloor +  \left\lfloor \frac{b}{m} \right\rfloor\right) \\[3ex]
&\;\;\;\;- m \left\lfloor \frac{a + b}{m} \right\rfloor + m \left(\left\lfloor \frac{a}{m} \right\rfloor +  \left\lfloor \frac{b}{m} \right\rfloor\right)\\[3ex]
&= (a + b) - m \left\lfloor \frac{a + b}{m} \right\rfloor
\end{aligned}

It will be. Therefore

(a + b) \% m = ((a \% m) + (b \% m)) \% m

Is established.

(End of proof)

What does this relational expression mean? The left side is

  1. Calculate $ a + b $
  2. Divide the result by $ m $ and make it too much

It is the order. This is a natural calculation to find "too much $ a + b $ divided by $ m $".

On the other hand, the right side is

  1. Divide $ a and b $ by $ m $, respectively.
  2. Add them together
  3. Divide the result by $ m $ and make it too much

It has become. The right side seems to take extra effort, but it has practical implications. Now, $ a % m $ and $ b % m $ are numbers less than $ m $, so ** the calculation process on the right side is only about $ 2m $ **. In other words, if $ 2m $ does not exceed the "maximum value of integers that can be handled", it can be calculated without overflow.

As a concrete example, let's look at the case of calculation using a signed 1-byte integer type (maximum value 127). When $ a = 99, b = 88, m = 55 $, if you add up like the left side and then take too much

a + b = 187 > 127

So it will overflow. However, by calculating like the right side

\begin{aligned}
(a \% m + b \% m) \% m &= (44 + 33) \% 55\\
&= 77 \% 55\\
&= 22
\end{aligned}

Can always be calculated within the range of signed 1-byte integer type.

$ M = 1000000007 $, which often appears in contests, is a number that does not exceed the maximum value of $ 2147483647 $ for a signed 4-byte integer even if it is doubled.

Also,

\begin{aligned}
(a + b) \% m = ((a \% m) + b) \% m\\
(a + b) \% m = (a + (b \% m)) \% m
\end{aligned}

Etc. can also be shown by the same procedure as the proof shown earlier. This means that in the case of addition, as long as you take too much at the end, you can take too much at any time along the way.

In summary, we found the following about addition in the mod world:

2.3. Subtraction

As with addition, the following relationship holds for subtraction.


(a - b) \% m = ((a \% m) - (b \% m)) \% m

The proof is the same as addition, so I will omit it.

From the same consideration as addition, we can see the following about subtraction in the mod world.

2.4. Multiplication

The following relationship holds for multiplication.


(ab) \% m = ((a \% m) \cdot (b \% m))\% m

(Proof)

From the definition of "%"

(Left side) = ab - m\left\lfloor\frac{ab}{m}\right\rfloor

on the other hand,

\begin{aligned}
(right side) &= \left\{\left(a - m\left\lfloor\frac{a}{m}\right\rfloor\right)\cdot\left(b - m\left\lfloor\frac{b}{m}\right\rfloor\right)\right\}\% m\\[3ex]
&= \left\{ab - m\left(a\left\lfloor\frac{b}{m}\right\rfloor + b\left\lfloor\frac{a}{m}\right\rfloor\right) + m^2\left\lfloor\frac{a}{m}\right\rfloor\cdot\left\lfloor\frac{b}{m}\right\rfloor\right\}\% m\\[3ex]
&= ab - m\left(a\left\lfloor\frac{b}{m}\right\rfloor + b\left\lfloor\frac{a}{m}\right\rfloor\right) + m^2\left\lfloor\frac{a}{m}\right\rfloor\cdot\left\lfloor\frac{b}{m}\right\rfloor\\[3ex]
&\;\;\;\;-m\left\lfloor\frac{ab - m\left(a\left\lfloor\frac{b}{m}\right\rfloor + b\left\lfloor\frac{a}{m}\right\rfloor\right) + m^2\left\lfloor\frac{a}{m}\right\rfloor\cdot\left\lfloor\frac{b}{m}\right\rfloor}{m}\right\rfloor
\end{aligned}

here,

\frac{- m\left(a\left\lfloor\frac{b}{m}\right\rfloor + b\left\lfloor\frac{a}{m}\right\rfloor\right) + m^2\left\lfloor\frac{a}{m}\right\rfloor\cdot\left\lfloor\frac{b}{m}\right\rfloor}{m}

Is an integer, so it can be taken out of the floor function,

\begin{aligned}
(right side) = ab - m\left\lfloor\frac{ab}{m}\right\rfloor
\end{aligned}

It will be. Therefore,

(ab) \% m = ((a \% m) \cdot (b \% m))\% m

Is established.

(End of proof)

It was found that multiplication has the same relationship as addition and subtraction. Also, in the case of addition, the maximum value of the calculation process was $ 2m $, but in the case of multiplication, it is $ m ^ 2 $. For example, when $ m = 1000000007 $, it can be handled as a signed 8-byte integer by calculating as shown on the right side.

From the above, we learned the following about multiplication in the mod world.

2.5. Division

Division is a little different than before. Up to this point, addition, subtraction, and multiplication could be calculated naturally in the same way as operations in the ** normal world ** without considering mods. For example, in the case of addition, in the normal world

4 + 7 = 11

In the mod world as well as

4 + 7 \equiv 11 \pmod{3} 

It was made like this. But what about division?

4 \div 7 \equiv ? \pmod{3}

Thinking like the normal world

4 \div 7 = 0.5714\dots

So I'm not sure because it says "$ 0.5714 \ dots $ divided by $ 3 $".

In fact, when you think about "what is division", you can see that division in the mod world can be considered in the same way as in the normal world.

2.5.1 Division in the normal world

Now let $ a $ be an integer and $ b $ be a non-$ 0 $ integer. Then you can divide $ a $ by $ b $. Division can be converted to fractions and multiplication

a \div b = a \times \frac{1}{b}

was. In other words, if you write in words

& emsp; & emsp; & emsp; & emsp; & emsp; & emsp; & emsp; & emsp; & emsp; & emsp; & emsp; & emsp; ** "divide by $ b $" is equivalent to "multiply by $ \ frac {1} {b} $" ** **

about it. So what is $ \ frac {1} {b} $? Of course, it is "the number of $ 1 $ divided by $ b $", but here we see it as follows.

& emsp; & emsp; & emsp; & emsp; & emsp; & emsp; & emsp; & emsp; & emsp; & emsp; & emsp; & emsp; & emsp; & emsp; ** $ \ frac {1} {b} $ is "$ 1 $ when multiplied by $ b $" Number to be "**

Such numbers are called the reciprocal of ** $ b $ (in terms of multiplication), the reciprocal of $ b $ **, and so on. In this article, I'll omit "about multiplication" and just call it "the inverse element of $ b $ **" and write it as $ b ^ {-1} $. If you write it in a mathematical formula, $ b ^ {-1} $ is

 b\cdot b^{-1} = 1

It is a number that satisfies. From the above,

& emsp; & emsp; & emsp; & emsp; & emsp; & emsp; & emsp; & emsp; & emsp; & emsp; ** "divide by $ b $" means "multiply the inverse element of $ b $ ($ b ^ {-1} $)" Is equal to **

I found out that. Summary

It will be.

2.5.2. Division in the mod world

Think of the mod world as you would in the normal world. In other words, "divide by $ b $ in the world legalized by $ m " means "multiply by the inverse element ( b ^ {-1} $) of $ b $ in the world legalized by $ m $". It means that · · · And this inverse element

b \cdot b^{-1} \equiv 1 \pmod{m}

It is a number that satisfies. In this way, the inverse element is called the inverse element ** of $ b $ modulo ** $ m $.

Let's look at a concrete example. When $ a = 4, b = 7, m = 3 $

a \div b \pmod{m}

Think about.

7 \cdot 4 \equiv 28 \equiv 1 \pmod{3}

So the inverse element of $ 7 $ modulo $ 3 $ is $ 4 $. Therefore

\begin{aligned}
a \div b &\equiv a \cdot b^{-1}\\
&\equiv 4 \cdot 4\\
&\equiv 16 \\
&\equiv 1 \pmod{3}
\end{aligned}

It will be.

2.5.3. Existence condition of inverse element and how to find it

Just as there is no $ 0 $ inverse element in the normal world, there is not always an inverse element in the mod world. For example, the inverse element $ x $ of $ 6 $ modulo $ 3 $

6x \equiv 1 \pmod{3}

There is no $ x $ that satisfies this expression because $ 6x $ is always congruent with $ 0 $ by the law of $ 3 $. The inverse element of $ b $ modulo $ m $ exists only when ** $ m $ and $ b $ are relatively prime **.

And as a way to find the inverse element

  1. Fermat's Little Theorem
  2. Extended Euclidean algorithm

There are two. ** Fermat's Little Theorem ** is as follows.


When $ p $ is a prime number and $ a $ is an integer that is not a multiple of $ p $ ($ a $ and $ p $ are relatively prime)

a^{p-1} \equiv 1 \pmod{p}

Is established.


Multiply both sides of this congruence by the inverse element $ a ^ {-1} $ of $ a $ modulo $ p $.

a^{p-2} \equiv a^{-1} \pmod{p}

It will be. That is, the inverse element is given by $ a ^ {p-2} $. For example, the inverse element of $ 6 $ modulo $ p = 1000000007 $

6^{1000000005} \pmod{p}

You just have to calculate. This can be calculated quickly using the ** iterative squares ** method. However, keep in mind that this method can only be used ** if the method is prime. (Of course, Fermat's little theorem is a theorem about prime numbers.) However, in many cases, such as $ 1000000007 $ and $ 998244353 $, I think the given method is a prime number.

On the other hand, ** Extended Euclidean algorithm ** is a linear indeterminate equation.

ax + by = \gcd(a, b)

It is an algorithm to solve. ($ A, b $ is an integer other than $ 0 $, $ \ gcd (a, b) $ is the greatest common divisor of $ a $ and $ b $) The inverse element $ x $ of $ a $ modulo $ m $ is

a x \equiv 1 \pmod{m}

It was a number that met. This congruence formula uses the integer $ y $

ax + my = 1

It can be rewritten as a linear indeterminate equation. This equation is because $ a $ and $ m $ are relatively prime when the inverse element exists.

ax + my = \gcd(a, m)

It will be. Therefore, the inverse element can be obtained by solving this with the extended Euclidean algorithm.

Please refer to internal_math edition ① for the ** iterative square method ** and ** extended Euclidean algorithm **.

3. Programming elements required for Modint

3.1. Class

Modint

It is an object with functions such as. Many languages ​​introduce ** classes ** to create objects with some function or attribute like this. Therefore, all you have to do is create a class called Modint and pack the necessary elements into it. This can be said to be the work of creating a new type called Modint type in addition to various types such as integer type, floating point type, and character string type.

3.2. Operator overload

Even if you incorporate operations in the mod world into the Modint type, for example, to do $ a + b $ or $ a \ times b $

a.add(b), a.mul(b)

There is not much benefit of Modint if you have to write such as. also

a + b, a * b

I want to be able to write. To do this, we need to rewrite the meaning of the operator. This is called ** operator overload **. (Some languages ​​do not provide operator overloads to users)

For example, the operator "+" usually means adding numbers, but in the string type it means concatenating strings, and operator overloading is already widely used.

As an extreme example, let's say you have created a type called Amanojaku as follows. (The code is an image and does not follow the grammar of a particular language)

class Amanojaku{
    def constructor(int: x){
        int _x = x
    }

    //Operator overload
    op{+}(lhs, rhs) := lhs._x - rhs._x
    op{-}(lhs, rhs) := lhs._x + rhs._x

    //On the right side+Or-Is lhs._x and rhs._Because x is an int type
    //In int type operation+,- (In other words, as normal addition and subtraction+,-)It means.
}

Then, the operation between the numbers $ a and b $ cast in the Amanojaku type is

a = Amanojaku(5)
b = Amanojaku(3)

print(a + b)   --> 2
print(a - b)   --> 8

It looks like.

In this way, Modint can be created by changing the meaning of the operator from "operation in the normal world" to "operation in the mod world" by overloading the operator.

4. Implementation in Python

Let's implement it. First, create the Modint class. Since it is necessary to share mods as a whole in Modint calculation, we will have a variable called mod as a class variable. Class variables can be accessed with class name.variable name. Also, since this value should not be changed during the calculation, we will have the flag has_been_set.

The value is stored in an instance variable called _v, and if it is negative or more than mod, it is divided by mod and replaced.

class Modint:
    mod = 0
    has_been_set = False

    def __init__(self, v=0, m=None):
        if m != None: 
            assert m >= 1
            assert not Modint.has_been_set
            Modint.mod = m
            Modint.has_been_set = True
        assert Modint.has_been_set
        self._v = v if 0 <= v < Modint.mod else v % Modint.mod      

In Python, operator overloads are provided in the form of Special Methods (https://docs.python.org/ja/3/reference/datamodel.html#special-method-names). The special method has two underscores (_) before and after it, and the constructor is also one of the special methods.

The table below summarizes the operators and corresponding special methods for number operations.

operator Special method
+ __add__
- __sub__
* __mul__
/ __truediv__
// __floordiv__
** __pow__

We will define these so that they will be operations in the mod world.

For example, when there is a code that says a + b,a.__ add__ (b)is called. So you need to check the type of b. If b is a Modint type, the value of b._v is fetched and calculated, and if b is an int type, the calculation is performed as it is. It then returns the resulting value as a new Modint type.

In the mod world, division uses // because integers are obtained as a result of operations between integers. The inverse element can be found with the built-in function pow (). In Python 3.8 or later, if the second argument is -1, the extended Euclidean algorithm is used, and if mod-2 is used, Fermat's little theorem is used. For other versions, use mod-2 or implement the extended Euclidean algorithm. The implementation method is in internal_math edition ①.

    def __add__(self, other):
        if isinstance(other, Modint):
            res = self._v + other._v
            if res > Modint.mod: res -= Modint.mod
        else:
            res = self._v + other
        return Modint(res)
    
    def __sub__(self, other):
        if isinstance(other, Modint):
            res = self._v - other._v
            if res < 0: res += Modint.mod
        else:
            res = self._v - other
        return Modint(res)
    
    def __mul__(self, other):
        if isinstance(other, Modint):
            return Modint(self._v * other._v)
        else:
            return Modint(self._v * other)
    
    def __floordiv__(self, other):
        if isinstance(other, Modint): other = other._v
        inv = pow(other, -1, Modint.mod)
        return Modint(self._v * inv)
    
    def __pow__(self, other):
        assert isinstance(other, int) and other >= 0
        return Modint(pow(self._v, other, Modint.mod))

It is also convenient to use the assignment operator, so this is also overloaded.

Assignment operators are such as + =, * =, and the corresponding special methods are the special methods of regular operators with the prefix i (such as __iadd__). The return value is self itself, because the assignment operation does not create a new one as a result of the operations of self and other, but changes self by other.

    def __iadd__(self, other):
        if isinstance(other, Modint):
            self._v += other._v
            if self._v >= Modint.mod: self._v -= Modint.mod
        else:
            self._v += other
            if self._v < 0 or self._v >= Modint.mod: self._v %= Modint.mod
        return self

    def __isub__(self, other):
        if isinstance(other, Modint):
            self._v -= other._v
            if self._v < 0: self._v += Modint.mod
        else:
            self._v -= other
            if self._v < 0 or self._v >= Modint.mod: self._v %= Modint.mod
        return self
    
    def __imul__(self, other):
        if isinstance(other, Modint):
            self._v *= other._v
        else:
            self._v *= other
        if self._v < 0 or self._v >= Modint.mod: self._v %= Modint.mod
        return self

    def __ifloordiv__(self, other):
        if isinstance(other, Modint): other = other._v
        inv = pow(other, -1, Modint.mod)
        self._v *= inv       
        if self._v > Modint.mod: self._v %= Modint.mod
        return self
    
    def __ipow__(self, other):
        assert isinstance(other, int) and other >= 0
        self._v = pow(self._v, other, Modint.mod)
        return self

Up to this point, if the left side of the operator is a Modint type, it can be calculated. However, it cannot be calculated when the left side is an int type and the right side is a Modint type. For example, the addition a + b of the int type variable a and the Modint type variable b is calleda.__ add__ (b), but the int type __add__ method is of the Modint type. An error will occur because the "+" operation with the variable is not defined. However, instead of throwing an error immediately, I think that the operation may be defined in the variable (Modint type) on the right side of the operator, and refer to the contents of the type on the right side. At this time, each special method with the prefix r is referenced (such as __radd__). By defining this, you can do (int) + (Modint).

Attention should be paid to the implementation of non-commutative operations in this method. For example, consider the subtraction a-b of an int type variable a and a Modint type variable b. At this time, (int)-(Modint) is not defined for int type, so b.__ rsub__ (a) is referenced. Therefore, you need to make other --self, noting that self = b, other = a in the definition of __rsub__.

Also, __rpow__ is not implemented because I don't think there is a situation of(int) ** (Modint).

    def __radd__(self, other):
        return Modint(self._v + other)
    
    def __rsub__(self, other):
        return Modint(other - self._v)  

    def __rmul__(self, other):
        return Modint(self._v * other)
    
    def __rfloordiv__(self, other):
        inv = pow(self._v, -1, Modint.mod)
        return Modint(other * inv)

Now that the definition of the arithmetic operator is complete, let's define the comparison operator. It is defined as ==,! = With mod as the method.

\begin{aligned}
a &\equiv b\\
a &\not \equiv b
\end{aligned}

Suppose that These will work even if you have a mix of int and Modint types.

    def __eq__(self, other):
        if isinstance(other, Modint):
            return self._v == other._v
        else:
            if other < 0 or other >= Modint.mod:
                other %= Modint.mod
            return self._v == other
    
    def __ne__(self, other):
        if isinstance(other, Modint):
            return self._v != other._v
        else:
            if other < 0 or other >= Modint.mod:
                other %= Modint.mod
            return self._v != other

Finally, define other special methods. __str__ is called when printing byprint (). Without it, it would look like <Modint object at 0x10aa43310>. __repr__ returns the official string representing the object. In the case of the numeric type, the character string of the numerical value itself is returned, so I implemented it following that. __int __ is called byint (). This allows you to cast to an int type.

    def __str__(self):
        return str(self._v)
    
    def __repr__(self):
        return str(self._v)
    
    def __int__(self):
        return self._v

5. Summary

I will post a summary of everything.

class Modint:
    mod = 0
    has_been_set = False

    def __init__(self, v=0, m=None):
        if m != None: 
            assert m >= 1
            assert not Modint.has_been_set
            Modint.mod = m
            Modint.has_been_set = True
        assert Modint.has_been_set
        self._v = v if 0 <= v < Modint.mod else v % Modint.mod
        

    def __add__(self, other):
        if isinstance(other, Modint):
            res = self._v + other._v
            if res > Modint.mod: res -= Modint.mod
        else:
            res = self._v + other
        return Modint(res)
    
    def __sub__(self, other):
        if isinstance(other, Modint):
            res = self._v - other._v
            if res < 0: res += Modint.mod
        else:
            res = self._v - other
        return Modint(res)
    
    def __mul__(self, other):
        if isinstance(other, Modint):
            return Modint(self._v * other._v)
        else:
            return Modint(self._v * other)
    
    def __floordiv__(self, other):
        if isinstance(other, Modint): other = other._v
        inv = pow(other, -1, Modint.mod)
        return Modint(self._v * inv)
    
    def __pow__(self, other):
        assert isinstance(other, int) and other >= 0
        return Modint(pow(self._v, other, Modint.mod))
    
    def __radd__(self, other):
        return Modint(self._v + other)
    
    def __rsub__(self, other):
        return Modint(other - self._v)  

    def __rmul__(self, other):
        return Modint(self._v * other)
    
    def __rfloordiv__(self, other):
        inv = pow(self._v, -1, Modint.mod)
        return Modint(other * inv)
    
    def __iadd__(self, other):
        if isinstance(other, Modint):
            self._v += other._v
            if self._v >= Modint.mod: self._v -= Modint.mod
        else:
            self._v += other
            if self._v < 0 or self._v >= Modint.mod: self._v %= Modint.mod
        return self

    def __isub__(self, other):
        if isinstance(other, Modint):
            self._v -= other._v
            if self._v < 0: self._v += Modint.mod
        else:
            self._v -= other
            if self._v < 0 or self._v >= Modint.mod: self._v %= Modint.mod
        return self
    
    def __imul__(self, other):
        if isinstance(other, Modint):
            self._v *= other._v
        else:
            self._v *= other
        if self._v < 0 or self._v >= Modint.mod: self._v %= Modint.mod
        return self

    def __ifloordiv__(self, other):
        if isinstance(other, Modint): other = other._v
        inv = pow(other, -1, Modint.mod)
        self._v *= inv       
        if self._v > Modint.mod: self._v %= Modint.mod
        return self
    
    def __ipow__(self, other):
        assert isinstance(other, int) and other >= 0
        self._v = pow(self._v, other, Modint.mod)
        return self

    def __eq__(self, other):
        if isinstance(other, Modint):
            return self._v == other._v
        else:
            if other < 0 or other >= Modint.mod:
                other %= Modint.mod
            return self._v == other
    
    def __ne__(self, other):
        if isinstance(other, Modint):
            return self._v != other._v
        else:
            if other < 0 or other >= Modint.mod:
                other %= Modint.mod
            return self._v != other

    def __str__(self):
        return str(self._v)
    
    def __repr__(self):
        return str(self._v)
    
    def __int__(self):
        return self._v

6. Usage example

As $ a = 16, b = 7, c = 12, d = 8, e = 9 $ at $ mod = 13 $

(a + b - c) * d \div e    

Let's calculate.

First, you need to set the mod. This can be set when casting the first calculated variable to a Modint type, or just the mod can be given first.

mod = 13
a = 16
b = 7
c = 12
d = 8
e = 9

#mod settings
Modint(m=mod)

#Cast the part to be calculated first to Modint type
a = Modint(a)
#a = Modint(a, m=mod)  #You may set the mod here
result = (a + b - c) * d // e
print(result)  # 4
print(type(result))  # <class '__main__.Modint'>

7. About speed

I tried to solve the problem that Modint can actually be used. The problem I used was Educational DP Contest H-Grid 1. This problem prints the enumeration using DP divided by 1000000007.

With Modint, it looks like this:


"""
Paste Modint(Omitted because it is long)
"""

def main():    
    mod = 1000000007
    h, w = map(int, input().split())
    wall = [[i == '#' for i in input()] for _ in range(h)]
    dp = [[0] * w for _ in range(h)]
    dp[0][0] = Modint(1, mod)  #Cast to Modint type
    # dp[0][0] = 1  #When not using Modint
    for i in range(h):
        for j in range(w):
            if wall[i][j]: continue
            if i > 0: dp[i][j] += dp[i-1][j]
            if j > 0: dp[i][j] += dp[i][j-1]
            # dp[i][j] %= mod  #When not using Modint
    print(dp[h-1][w-1])
    
if __name__ == '__main__':
    main()

As a result of submitting with and without Modint, the execution time is as follows.

use do not use
1870\rm{ms} 524\rm{ms}

The Modint created in this article is very slow.

8. What are the benefits of implementing Modint in Python ...?

In my opinion, Python has a fairly low priority for maintaining Modint. This is because I think Python has a small advantage and a large disadvantage. Among the merits of Modint mentioned in Chapter 1, about overflow and negative remainder

Intrinsic functions using the extended Euclidean algorithm and high-speed exponentiation using the iterative square method are also implemented in the built-in functions.

On the other hand, as mentioned in the previous chapter (in the implementation of this article), the execution speed is very slow. For Python, which is a slow language by nature, this disadvantage feels huge.

Of course, the code is cleaner so you can focus on the essence of the problem and it will be easier to debug. Also, I think that it will be useful for problems that do not have to worry about execution time, such as problems that can be solved with $ O (1) $.


(Added on 2020.12.28) The solution with multiple-precision integers is worries about undefined behavior due to overflow. The operation of huge numbers is very time consuming and causes TLE. To avoid this, it is necessary to take too much ** in the calculation process ** with some frequency (every $ \ fallingdotseq $ operation) **.

9. Conclusion

I created a structure Modint that takes too much automatically. It's very convenient, but it seems difficult to make something practical in Python.

Please let us know if you have any mistakes, bugs, or advice.

Recommended Posts

[Modint] Decoding the AtCoder Library ~ Implementation in Python ~
[Internal_math version (2)] Decoding the AtCoder Library ~ Implementation in Python ~
[Internal_math (1)] Read with Green Coder AtCoder Library ~ Implementation in Python ~
Daily AtCoder # 36 in Python
Daily AtCoder # 32 in Python
Daily AtCoder # 6 in Python
Daily AtCoder # 18 in Python
How to use the C library in Python
Daily AtCoder # 53 in Python
Daily AtCoder # 7 in Python
Daily AtCoder # 24 in Python
Daily AtCoder # 37 in Python
RNN implementation in python
Daily AtCoder # 8 in Python
Daily AtCoder # 42 in Python
ValueObject implementation in Python
Daily AtCoder # 21 in Python
Daily AtCoder # 17 in Python
Daily AtCoder # 38 in Python
Daily AtCoder # 54 in Python
Daily AtCoder # 11 in Python
Daily AtCoder # 15 in Python
Daily AtCoder # 13 in Python
Daily AtCoder # 45 in Python
Daily AtCoder # 30 in Python
Daily AtCoder # 40 in Python
Daily AtCoder # 10 in Python
Daily AtCoder # 5 in Python
Daily AtCoder # 28 in Python
Daily AtCoder # 39 in Python
Daily AtCoder # 20 in Python
Daily AtCoder # 19 in Python
Daily AtCoder # 52 in Python
Daily AtCoder # 3 in Python
Daily AtCoder # 14 in Python
[DSU Edition] AtCoder Library reading with a green coder ~ Implementation in Python ~
Daily AtCoder # 50 in Python
Daily AtCoder # 26 in Python
Daily AtCoder # 4 in Python
Daily AtCoder # 43 in Python
Daily AtCoder # 29 in Python
Daily AtCoder # 22 in Python
Daily AtCoder # 49 in Python
Daily AtCoder # 27 in Python
Daily AtCoder # 1 in Python
Daily AtCoder # 25 in Python
Daily AtCoder # 16 in Python
Daily AtCoder # 12 in Python
Daily AtCoder # 48 in Python
Daily AtCoder # 34 in Python
Daily AtCoder # 31 in Python
Daily AtCoder # 46 in Python
Daily AtCoder # 35 in Python
Use the LibreOffice app in Python (3) Add library
SVM implementation in python
Daily AtCoder # 9 in Python
Daily AtCoder # 44 in Python
Daily AtCoder # 41 in Python
Using the National Diet Library Search API in Python
A reminder about the implementation of recommendations in Python
Download the file in Python