【Math編】ac-Library-pythonを軽くまとめる

# はじめに
本記事はac-Library-pythonを使用するにあたり、引数やメソッド・計算量など最低限の情報をまとめたもののデータ構造編になります。
「ドキュメントが小難しく読んでいられない・結局どういうこと？」といった人を対象としています。


## Math
数論的アルゴリズム達
```python
from atcoder.math import {function}
```
* inv_mod(x: int, m: int) → int
$xy \equiv 1(mod\ m) $となり、$0 \leqq y < m$を満たす$y$を返す
`x`と`m`が互いに素でない場合`AssertionError`となる
計算量：$O(\log m)$

* crt(r: List[int], m: List[int]) → Tuple[int, int]
中国剰余定理
未知数`x`を`m[i]`で割った余り$r[i]$の配列を引数にとり、(`x`,`lcm(m)`)を返す
答えがない場合は(0,0)、配列の長さが0のときは(0,1)を返す
計算量：$O(n\log lcm (m))$

* floor_sum(n: int, m: int, a: int, b: int) → int
$\sum_{n=0}^{n-1} \begin{bmatrix}a\times i+b\over m\end{bmatrix}$ を計算する
計算量：$O(\log (n+m+a+b))$
:::note info
本家ac-Libraryには`pow_mod`が実装されているが、ac-Library-pythonにはない。
標準の`pow(base: int, exp: int, mod: int) -> int`が利用できる。
:::

## Convolution
[畳み込み](https://ja.wikipedia.org/wiki/%E7%95%B3%E3%81%BF%E8%BE%BC%E3%81%BF)を行う。

<details><summary>簡単な説明</summary><div>

数列$a_n=a_0,a_1,..a_{N-1},b_m=b_1,b_2,...b_{M-1}$に対し$0\leqq i \leqq (N-1)+(M-1)$で
```math
c_i = \sum_{j=0}^ia_jb_{i-j}
```
を計算する。
つまり、$a_n$と$b_n$を逆向きに並べ、$a_n$に対し$b_n$並行移動して行った時、数列の各項は重なる部分同士の値をかけ、それらを足し合わせたものである。
定義式では数列に存在しない項が指定されることもある。この部分では実際には二つの数列は重なっていないため、存在しない項の値は０として扱われる。
例えば$N=3,M=2$の時を考えると、$0 \leqq i \leqq (2-1)+(3-1)=3$である。
$i=0$の時$c_0 = \sum_{j=0}^0a_jb_{0-j}=a_0b_0$
$i=1$の時$c_1 = \sum_{j=0}^1a_jb_{1-j}=a_0b_1+a_1b_0$
$i=2$の時$c_2 = \sum_{j=0}^2a_jb_{2-j}=a_0b_2+a_1b_1+a_2b_0=a_1b_1+a_2b_0$
$i=2$の時$c_3 = \sum_{j=0}^3a_jb_{3-j}=a_0b_3+a_1b_2+a_2b_1+a_3b_0=a_2b_1$
| $i$ |     |$a_0$|$a_1$|$a_2$|     |
| :-: | :-: | :-: | :-: | :-: | :-: |
| $0$ |$b_1$|$b_0$|
| $1$ |     |$b_1$|$b_0$|
| $2$ |     |     |$b_1$|$b_0$|
| $3$ |     |     |     |$b_1$|$b_0$|

</div></details>

```python
from atcoder.convolution import {function}
```
* convolution(mod: int, a: List[Any], b: List[Any]) → List[Any]
畳み込みをmodで計算する。`a`,`b`の少なくとも一方が空配列の時はから配列を返す。
$c_i = \sum_{j=0}^ia_jb_{i-j}\mod mod$
計算量:$O(n\log n+\log mod)$
* convolution_int(a: List[int], b: List[int]) → List[int]
畳み込みを計算する。`a`,`b`の少なくとも一方が空配列の時はから配列を返す。
$c_i = \sum_{j=0}^ia_jb_{i-j}$
計算量:$O(n\log n)$
# Modint
数値計算が`context`で指定した`mod`の値をとって行われる。
```python 
from atcoder.modint import ModContext,Modint	
```
### ModContext
合同式を簡単に扱えるます。前提の合同式を理解していないと思わぬところで躓くかも。
* __init__(self, mod: int) -> None
`mod`:使用する値を指定する
### Modint
* __init__(v: int = 0) → None
`int`:数値
* inv() → atcoder.modint.Modint
$xy \equiv 1$となる$y$(Modint)を返す
* mod() → int
`ModContext`で指定されている`mod`の値を返す
* val() → int
現在の数値を返す

<details><summary>使用例</summary><div>

```python
from atcoder.modint import ModContext,Modint
#contextでのmodを指定
with ModContext(5):
    #インスタンス化
    x=Modint(13)
    
    print(x.mod())
#>>5
    
    print(x.val())
#>>3
    
    x+=3
    print(x.val())
#>>1(3+3=6=1)
    
    x-=3
    print(x.val())
#>>3(1-3=-2=3)
    
    x*=3
    print(x.val())
#>>4(3x3=9=4)
    
    inv = x.inv()
    print(inv)
#>><atcoder.modint.Modint object at 0x10268aeb0>
    
    print(inv.val())
#>>4(4x4=16)
```

</div></details>

# 参考 
以下を参照し記事を書きました。より詳しいことが知りたい場合も参考になると思います。

https://github.com/not522/ac-library-python/tree/master

https://atcoder.github.io/ac-library/production/document_ja/

https://ac-library-python.readthedocs.io/en/latest/index.html