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

はじめに

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

Math

数論的アルゴリズム達

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))$

本家ac-Libraryにはpow_modが実装されているが、ac-Library-pythonにはない。
標準のpow(base: int, exp: int, mod: int) -> intが利用できる。

Convolution

畳み込みを行う。

簡単な説明

数列$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)$で

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$

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の値をとって行われる。

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
  現在の数値を返す

使用例

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)

参考

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