n_ha_ac_library package

Submodules

n_ha_ac_library.cum module

累積和

class n_ha_ac_library.cum.Cum(v: int | list[T], op: Callable[[T, T], T], inv: Callable[[T], T], e: T)

ベースクラス: Generic

累積和

Tip

型が任意なのでデフォルト値はありません。整数のみを扱う場合は CumInt を利用できます。

Tip

T: 群 ( get で left が常に 0 ならば左単位的マグマ)

build(a: list[T]) → None

構築

リスト a を用いて累積和のリスト self.data を構築します。 要素数で初期化をした場合に、一度のみ実行可能です。

パラメータ:: a (list[T]) -- リスト

get(left: int, right: int | None = None) → T

二項演算を作用させた値の取得

半開区間[left, right)の要素に二項演算を作用させた値を求めます。

パラメータ:

left (int) -- 左端
right (int | None, optional) -- 右端. Defaults to left + 1.

戻り値:

累積和

戻り値の型:

T

set(index: int, value: T) → None

値の更新

index の要素の値を value に更新します。

パラメータ:

index (int) -- インデックス
value (T) -- 更新値

class n_ha_ac_library.cum.CumInt(v: int | list[int | ~n_ha_ac_library.modint.ModInt], op: ~typing.Callable[[int | ~n_ha_ac_library.modint.ModInt, int | ~n_ha_ac_library.modint.ModInt], int | ~n_ha_ac_library.modint.ModInt] = <function op>, inv: ~typing.Callable[[int | ~n_ha_ac_library.modint.ModInt], int | ~n_ha_ac_library.modint.ModInt] = <function inv>, e: int | ~n_ha_ac_library.modint.ModInt = 0)

ベースクラス: Cum[int | ModInt]

整数用累積和

Cum[Int] を継承した整数のみに対応した累積和です。デフォルト値を用いた場合は一般的な累積和を求めます。

サンプル

>>> a = [3, 1, 4]
>>> cum = CumInt(a) # 累積和の構築
>>> len(cum) # 要素数
3
>>> cum[1] # a[1]の値
1
>>> cum[0:3] # a[0] + a[1] + a[2]の値
8
>>> cum[0] = 1 # a[0]の値を1に更新
>>> cum[0:3] # a[0] + a[1] + a[2]の値
6

注釈

Cum の更新は非効率です。更新を頻繁に行う場合は FenwickTree を利用してください。

n_ha_ac_library.dsu module

DSU

class n_ha_ac_library.dsu.DSU(Union-Find Tree)

ベースクラス: object

groups() → list[list[int]]

グループのリストを取得

戻り値:: グループのリスト
戻り値の型:: list[list[int]]

leader(a: int) → int

頂点 a のグループの代表を取得

パラメータ:: a (int) -- 頂点
戻り値:: グループの代表
戻り値の型:: int

members(a: int) → list[int]

頂点 a と同じグループに属する頂点のリストを取得

パラメータ:: a (int) -- 頂点
戻り値:: 頂点 a と同じグループに属する頂点のリスト
戻り値の型:: list[int]

merge(a: int, b: int) → int

頂点 a と b を併合

パラメータ:

a (int) -- 頂点
b (int) -- 頂点

戻り値:

併合されたグループの代表

戻り値の型:

int

roots() → list[int]

グループの代表のリストを取得

戻り値:: グループの代表のリスト
戻り値の型:: list[int]

same(a: int, b: int) → bool

頂点 a と b が同じグループに属するかを判定

パラメータ:

a (int) -- 頂点
b (int) -- 頂点

戻り値:

同じグループに属するか

戻り値の型:

bool

size(a: int) → int

頂点 a が属するグループのサイズを取得

パラメータ:: a (int) -- 頂点
戻り値:: グループのサイズ
戻り値の型:: int

n_ha_ac_library.fenwicktree module

フェニック木(Binary Indexed Tree)

class n_ha_ac_library.fenwicktree.FenwickTree(v: int | list[T], op: Callable[[T, T], T], inv: Callable[[T], T], e: T)

ベースクラス: Generic

フェニック木 (Binary Indexed Tree)

Tip

型が任意なのでデフォルト値はありません。整数のみを扱う場合は FenwickTreeInt を利用できます。

Tip

T: アーベル群 (可換群)

add(index: int, value: T) → None

値の差分更新

index の要素の値を自分自身と value に二項演算を作用させた値に更新します。

パラメータ:

index (int) -- インデックス
value (T) -- 更新値の差分

build(a: list[T]) → None

構築

リスト a を用いてフェニック木のリスト self.data を構築します。 要素数で初期化をした場合に、一度のみ実行可能です。

パラメータ:: a (list[T]) -- リスト

get(left: int, right: int | None = None) → T

二項演算を作用させた値を取得

半開区間[left, right)の要素に二項演算を作用させた値を求めます。

パラメータ:

left (int) -- 左端
right (int | None, optional) -- 右端. Defaults to left + 1.

戻り値:

作用させた値

戻り値の型:

T

prod(index: int) → T

右端を指定して二項演算を作用させた値を取得

半開区間[0, index)の要素に二項演算を作用させた値を求めます。

パラメータ:: index (int) -- インデックス
戻り値:: 作用させた値
戻り値の型:: T

set(index: int, value: T) → None

値の更新

index の要素の値を value に更新します。

パラメータ:

index (int) -- インデックス
value (T) -- 更新値

class n_ha_ac_library.fenwicktree.FenwickTreeInt(v: int | list[int | ~n_ha_ac_library.modint.ModInt], op: ~typing.Callable[[int | ~n_ha_ac_library.modint.ModInt, int | ~n_ha_ac_library.modint.ModInt], int | ~n_ha_ac_library.modint.ModInt] = <function op>, inv: ~typing.Callable[[int | ~n_ha_ac_library.modint.ModInt], int | ~n_ha_ac_library.modint.ModInt] = <function inv>, e: int | ~n_ha_ac_library.modint.ModInt = 0)

ベースクラス: FenwickTree[int | ModInt]

整数用フェニック木

FenwickTree[Int] を継承した整数のみに対応したフェニック木です。デフォルト値を用いた場合は一般的な累積和を求めます。

サンプル

>>> a = [3, 1, 4]
>>> ft = FenwickTreeInt(a) # フェニック木の構築
>>> len(ft) # 要素数
3
>>> ft[1] # a[1]の値
1
>>> ft[0:3] # a[0] + a[1] + a[2]の値
8
>>> ft[0] = 1 # a[0]の値を1に更新
>>> ft[0:3] # a[0] + a[1] + a[2]の値
6

n_ha_ac_library.modint module

ModInt

class n_ha_ac_library.modint.ModInt

ベースクラス: object

注釈

最初に set_mod クラスメソッドで法を設定する必要があります。法として 998244353 または 1000000007 のみを扱う場合は、それぞれ ModInt998244353 と ModInt1000000007 を利用できます。

inv() → ModInt

逆元の取得

戻り値:: 逆元
戻り値の型:: ModInt

classmethod mod() → int

法の取得

戻り値:: 法
戻り値の型:: int

classmethod raw(value: int) → ModInt

剰余を取らない ModInt インスタンスの生成

__init__ をバイパスしてインスタンス化し、剰余演算をスキップするためのクラスメソッドです。

パラメータ:: value (int) -- 値、0以上 MOD 未満の整数
戻り値:: 剰余を取らない ModInt インスタンス
戻り値の型:: ModInt

classmethod set_mod(m: int) → None

法の設定

最初に一度だけ実行してください。

パラメータ:: m (int) -- 法、正の整数

class n_ha_ac_library.modint.ModInt1000000007(value: int | ModInt = 0)

ベースクラス: ModInt

1000000007を法とするModInt

ModInt を継承した、法が 1000000007 に固定された ModInt クラスです。

注釈

法が固定されているため、 set_mod クラスメソッドは呼び出せません。

class n_ha_ac_library.modint.ModInt998244353(value: int | ModInt = 0)

ベースクラス: ModInt

998244353を法とするModInt

ModInt を継承した、法が 998244353 に固定された ModInt クラスです。

注釈

法が固定されているため、 set_mod クラスメソッドは呼び出せません。

n_ha_ac_library.modint.generate_modint(mod: int) → type[ModInt]

任意の法を持つ新しいModIntクラスを生成するファクトリ関数

パラメータ:: mod (int) -- 法、正の整数
戻り値:: 新しいModIntクラス
戻り値の型:: type[ModInt]

n_ha_ac_library.segtree module

セグメント木

class n_ha_ac_library.segtree.SetTree(v: int | list[T], op: Callable[[T, T], T], e: T)

ベースクラス: Generic

セグメント木

Tip

型が任意なのでデフォルト値はありません。整数のみを扱う場合は SetTreeInt を利用できます。

Tip

T: モノイド

build(a: list[T]) → None

構築

リスト a を用いてセグメント木のリスト self.data を構築します。 要素数で初期化をした場合に、一度のみ実行可能です。

パラメータ:: a (list[T]) -- リスト

get(left: int, right: int | None = None) → T

二項演算を作用させた値の取得

半開区間[left, right)の要素に二項演算を作用させた値を求めます。

パラメータ:

left (int) -- 左端
right (int | None, optional) -- 右端. Defaults to left + 1.

戻り値:

作用させた値

戻り値の型:

T

max_right(left: int, f: Callable[[T], bool]) → int

左端を指定して条件を満たす最大のインデックスの取得

パラメータ:

left (int) -- 左端
f (Callable[[T], bool]) -- 条件を満たすかどうかの判定関数

戻り値:

条件を満たす最大のインデックス

戻り値の型:

int

min_left(right: int, f: Callable[[T], bool]) → int

右端を指定して条件を満たす最小のインデックスの取得

パラメータ:

right (int) -- 右端
f (Callable[[T], bool]) -- 条件を満たすかどうかの判定関数

戻り値:

条件を満たす最小のインデックス

戻り値の型:

int

set(index: int, value: T) → None

値の更新

index の要素の値を value に更新します。

パラメータ:

index (int) -- インデックス
value (T) -- 更新値

update(k: int) → None

ノードの更新

k のノードの値を子ノードの値から再計算します。

パラメータ:: k (int) -- ノードのインデックス

ベースクラス: SetTree[int | ModInt]

整数用セグメント木

SetTree[Int] を継承した整数のみに対応したセグメント木です。デフォルト値を用いた場合は一般的な最大値を求めます。

サンプル

>>> a = [3, 1, 4]
>>> st = SetTreeInt(a, op=max, e=0) # セグメント木の構築
>>> len(st) # 要素数
3
>>> st[1] # a[1]の値
1
>>> st[0:3] # a[0] + a[1] + a[2]の値
8
>>> st[0] = 1 # a[0]の値を1に更新
>>> st[0:3] # a[0] + a[1] + a[2]の値
6

Module contents

N-ha's AtCoder library