Python で Modint (N番煎じ)

## はじめに

AtCoder Library の`Modint`が個人的に使いづらいので自作しました。

https://github.com/not522/ac-library-python/blob/master/atcoder/modint.py

## 方針

- 基本的には AtCoder Library とインターフェースを合わせるが、一部で Python 標準の演算子を用いる。`x.val()`は`int(x)`で、`x.inv()`は`x ** -1`で、`raw(x)`は`Modint(x)`で代用する
- mod の指定は大域変数で行う。たいてい 1 つしか使わないので、AtCoder Library のように`ModContext`で指定するのは面倒
- (元のC++の) AtCoder Library と同様に、加減乗除の片方が`int`でも動作可能とする
- イミュータブルなオブジェクトにする
- 呼び出される回数が多いはずなので、分岐は避ける

## コード

```python
MOD = 1000000007

class Modint:
    def __init__(self, v = 0):
        self._v = v % MOD
    def __add__(self, rhs):
        return Modint(self._v + int(rhs))
    def __sub__(self, rhs):
        return Modint(self._v - int(rhs))
    def __mul__(self, rhs):
        return Modint(self._v * int(rhs))
    def __floordiv__(self, rhs):
        return Modint(self._v * pow(int(rhs), -1, MOD))
    def __pow__(self, n):
        return Modint(pow(self._v, n, MOD))
    def __radd__(self, rhs):
        return Modint(rhs + self._v)
    def __rsub__(self, rhs):
        return Modint(rhs - self._v)
    def __rmul__(self, rhs):
        return Modint(rhs * self._v)
    def __rfloordiv__(self, rhs):
        return Modint(rhs * pow(self._v, -1, MOD))
    def __eq__(self, rhs):
        return rhs == self._v
    def __neg__(self):
        return Modint(-self._v)
    def __pos__(self):
        return self
    def __str__(self):
        return str(self._v)
    def __repr__(self):
        return f'Modint({self._v!r})'
    def __int__(self):
        return self._v
    def __hash__(self):
        return hash(self._v)
    def __bool__(self):
        return bool(self._v)
```
## 実装について

末尾の参考記事とかぶらない内容のみ説明します。

### \_\_iadd\_\_ など

イミュータブルなオブジェクトにしたいなら、実装してはいけません。定義しなくても`+=`などは動作しますし、定義してしまうと意図しない値の共有が起こって混乱することになります。
新規のオブジェクトを返すように実装すればイミュータブルにはなりますが、[公式の説明](https://docs.python.org/ja/3/reference/datamodel.html#object.__iadd__)に「 These methods should attempt to do the operation in-place (modifying self)」とある通り、実装するなら自身の値を上書きすべきです。

### \_\_eq\_\_

`__add__`などと異なり`int(rhs)`を使用していないのは、無関係のオブジェクトと比較してもエラーにならないようにするためです。
相手が`int`の場合に剰余をとらないのは、上記エラー対策に加えて、比較を推移的([公式の説明](https://docs.python.org/ja/3/reference/expressions.html#value-comparisons)も参照)にするという意味もあります。もし剰余を取ってから比較する仕様にすると、`MOD=11`の場合に`2 == Modint(2) == 13`となり、推移的だとすると`2 == 13`という誤った結果が導かれてしまいます。
`!=`については、`__ne__`が定義されていなければ`__eq__`の否定として定義されるので、明示的に定義する必要はありません。

### \_\_neg\_\_, \_\_pos\_\_

それぞれ、[単項マイナス](https://docs.python.org/ja/3/reference/datamodel.html#object.__neg__)、[単項プラス](https://docs.python.org/ja/3/reference/datamodel.html#object.__pos__)の実装となります。AtCoder Library で実装されていたので追加しましたが、不要なら削除しても構いません。

### \_\_repr\_\_

[公式の説明](https://docs.python.org/ja/3/reference/datamodel.html#object.__repr__)に従い「 (適切な環境が与えられれば) 同じ値のオブジェクトを再生成するのに使える、有効な Python 式のようなもの」を返すようにしています。

### \_\_hash\_\_

`Modint`を`dict`のキーにしたいなら実装が必要です。そのようなケースは少ないと思われるので、不要なら削除しても構いません。

### \_\_bool\_\_

こちらを定義しないと、`Modint(0)`が`True`扱いとなってしまいます。それで困るケースは少ないと思われるので、不要なら削除しても構いません。

## 余談(こちらのコードを書いた動機)

競プロ典型90問の008について、

https://atcoder.jp/contests/typical90/tasks/typical90_h

AtCoder Library の Modint を使って以下のようなコードを作成したところ(コードが拙いのは無視してください)、入力例2にて`16`という誤った値が出力されました。

```python
from collections import defaultdict
from atcoder.modint import ModContext, raw
from itertools import pairwise
n = int(input())
s = defaultdict(list)
with ModContext(1_000_000_007):
    for i, c in enumerate(input()):
        s[c].append([i, 0])
    for c in s:
        s[c] = s[c][::-1]
    for v in s['r']:
        v[1] = raw(1)
    for c, d in pairwise('atcoder'[::-1]):
        i, o = 0, raw(0)
        for v in s[d]:
            while i < len(s[c]) and v[0] <= s[c][i][0]:
                o += s[c][i][1]
                i += 1
            v[1] = o
    print(sum((i[1] for i in s['a']), start=raw(0)).val())
```

調べたところ、17行目の`o += s[c][i][1]`で意図せず値が共有されてしまい、関係ない値まで更新されていたことが原因でした。`o = o + s[c][i][1]`に変更することで正答となりました。

既にこの世には Python 用の Modint 実装があふれているのは重々承知していますが、 ~~この怒りをぶつけるため~~ ミュータブルになっていたり、実装が複雑だったりで、自分の望むものが見つからなかったため、あえて自作することとしました。

最終的に、先頭の`Modint`の実装 + 以下のコードで正答となりました。めでたしめでたし。

```python
from collections import defaultdict
from itertools import pairwise
n = int(input())
s = defaultdict(list)
for i, c in enumerate(input()):
    s[c].append([i, 0])
for c in s:
    s[c] = s[c][::-1]
for v in s['r']:
    v[1] = Modint(1)
for c, d in pairwise('atcoder'[::-1]):
    i = o = 0
    for v in s[d]:
        while i < len(s[c]) and v[0] <= s[c][i][0]:
            o += s[c][i][1]
            i += 1
        v[1] = o
print(sum(i[1] for i in s['a']))
```

## 参考

Python で Modint を使いたい場合、AtCoder なら公式ライブラリがありますし、それで不足する場合でも Qiita 上にいくらでも記事があるので、気に入ったものを選べばよいかと思います。

https://qiita.com/wotsushi/items/c936838df992b706084c

https://qiita.com/AkariLuminous/items/dc5c81fa9d945440afa0

https://qiita.com/hyouchun/items/4024845d6783c8dacc77

https://qiita.com/takumasa/items/12b9aeaf4a21737bd019