ACL_数学
数学
Math 数論的アルゴリズムmath
任意mod逆数math.inv_mod(x, m)$ O(\log m)
$ xy \equiv 1 \pmod m となる$ 0 \le y \lt m を得る
制約:$ \gcd(x,m) = 1
中国剰余定理 CRTmath.crt(r, m)$ O(n \log \text{lcm}(m_i))
$ x \equiv r_i \pmod {m_i} の解$ x \equiv y \pmod z の$ (y, z) を得る
制約:len(r) == len(m), m[i] > 1
floor summath.floor_sum(n, m, a, b)$ O(\log m)
$ \sum_{i=0}^{n-1} \left\lfloor \frac{ai+b}{m} \right\rfloor を得る
使い時がわからん
from atcoder import mathとすると標準のmathと衝突するので、as atmath等で回避して使うのが良さそう
本家にあるpow_modは標準のpowでできるので省略されている。
Convolution 畳み込みconvolution
$ c_i = \sum_{j=0}^i a_jb_{i-j} とか$ \sum c_ix^i = \left ( \sum a_ix^i \right )\left ( \sum b_ix^i \right )の計算
Modintを使って書かれているため、やや遅い。
convolution (mod m)concolution.convolution(m, a, b)$ O(n \log n + \log m)
$ \bmod m で畳み込む
$ m は998244353など、例の素数
convolution (ll)convolution.convolution_int(a, b)$ O(n \log n)
mod を取らずに畳み込む
実際の上限は59501818244292734739283968(26桁)。$ 2^{85} < 5.9\times10^{26} < 2^{86} くらいの値
concolution.convolution_mod(a, b)はa, bがModint列である必要があるので、基本使わないかと
Modintmodint
実行速度が怪しいらしい
with modint.ModContext(mod):として使うっぽい?
コンストラクタmodint.Modint(x)$ O(1)
mod.mod()$ O(1)
値の取得.val()$ O(1)
各種演算 基本$ O(1) 、除算$ O(\log \text{mod})
できる演算 m: Modint, i: int, x: どちらでも
符号-m, +m
四則演算と累乗m + x, m - x, m * x, m // x, m ** i
代入もm += x, m -= x, m *= x, m //= x, m **= i
比較m == x, m != x
できない演算
i + m, i - m, i * m, i // m:Modintが先に来る必要がある
x ** m:指数にModintはNG
$ \gcd(b, \text{mod}) \not = 1な除算m //= b, m // b
inv.inv()$ O(\log \text{mod})
逆数を得る。要gcd(.val(), mod) == 1