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 **.
Python documentation. https://docs.python.org/ja/3/reference/datamodel.html
Modint is a ** structure that automatically takes too much **.
As an example, let's look at the case where $ (a \ times b + c --d) / e $ is divided by $ m $ to find the remainder.
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.
If you cast a to Modint type
a = Modint(a, mod=m)
(a * b + c - d) / e
Can be written in a natural way.
As a ** merit ** of using Modint
Such will be considered. On the other hand, as a ** disadvantage **
Such will be considered.
To make a Modint that can be used in contests, etc.
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.
Let's look at the calculation method in the mod world.
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}
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
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
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:
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.
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.
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.
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.
Think of the mod world as you would in the normal world.
In other words, "divide by $ b $ in the world legalized by $ m
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.
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
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 **.
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.
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.
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
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
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'>
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 |
|---|---|
The Modint created in this article is very slow.
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) **.
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