ACL_数学 - isee競プロメモ

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