# API 仕様

対応基準は [ACL v1.6](https://github.com/atcoder/ac-library/tree/v1.6) と [公式仕様](https://atcoder.github.io/ac-library/master/document_ja/index.html) です。C++ 固有の構文ではなく、有効入力に対する演算の意味・戻り値・計算量を移植対象としています。正確な型シグネチャは `src/*/pkg.generated.mbti` を参照してください。

## 共通規約

- 添字・頂点・サイズは `Int`、0-indexed。区間は **`[l, r)`**。
- `new(n)` の既定値 `n = 0` は設けず、空なら明示的に `new(0)` と書きます。
- 範囲などを `panic` で検証します。release でも検証は残ります。代数法則や結果のオーバーフローなど、すべての前提条件を実行時に検出する保証はありません。
- 可変データ構造の代入は同一インスタンスの共有です。C++ の値コピーとは異なります。`from_array` は配列の外側をコピーしますが、要素内の可変オブジェクトまで複製しません。
- `op/e/mapping/composition/id` は副作用なく、渡された値を変更しない演算として実装してください。サイズに対する計算量はこれらの演算と要素コピーを O(1) と仮定します。
- 配列・木・グラフを確保する API の上限は原則 `n <= 100,000,000`。計算資源が足りることは呼び出し側の責任です。
- `Debug` は診断用で、形式の安定性を保証しません。SegTree/LazySegTree は要素や作用が `Debug` を持つ場合だけ実装します。デバッグ出力は lazy propagation を実行しません。

## DSU

`Dsu::new(n)`、`merge(a,b) -> Int`、`same(a,b) -> Bool`、`leader(a) -> Int`、`size(a) -> Int`、`groups() -> Array[Array[Int]]`。

`merge` は統合後の代表を返します。union by size と経路圧縮により操作は償却 O(α(n))、構築・`groups` は O(n)。`groups` の要素は各頂点をちょうど一度含み、各グループ内は昇順です。代表の選び方やグループの順序に依存しないでください。

## Fenwick tree

`FenwickTree[T]`：`T : Zero + Add + Sub`。

- `new(n)`：ゼロで初期化、O(n)。
- `add(p,x)`：`a[p] += x`、O(log n)。
- `sum(l,r)`：区間和。空区間はゼロ、O(log n)。

加法は可換群をなす必要があります。`Zero::zero()` は加法単位元です。Int / UInt / Int64 / UInt64、固定・動的 ModInt は対応済みです。整数の加減算は各ビット幅で wrap します。独自型にも `Zero` を実装できます。

## Segment tree

`SegTree[S]` は trait 制約なし。`new(n, op~, e~)` または `from_array(values, op~, e~)`。`op : (S,S)->S` は結合的、`e : ()->S` は左右の単位元。可換性は不要です。

| 操作 | 意味 | 計算量 |
|---|---|---|
| `new`, `from_array` | 構築 | O(n) |
| `set(p,x)`, `get(p)` | 点更新・参照 | O(log n), O(1) |
| `prod(l,r)` | 左から右への積 | O(log n) |
| `all_prod()` | 全体の積、空なら e | O(1) |
| `max_right(l,predicate)` | predicate が真である右端を探索 | O(log n) |
| `min_left(r,predicate)` | predicate が真である左端を探索 | O(log n) |

境界探索では `predicate(e()) == true` が必須。同じ引数に同じ結果を返し、区間を拡張する方向に真から偽へ単調に変化する predicate を渡してください。結果はそれぞれ `l..=n`、`0..=r`。非可換演算でも積の順序を維持します。

## Lazy segment tree

`LazySegTree[S,F]` のコンストラクタには SegTree の `op/e` に加え、`mapping : (F,S)->S`、`composition : (F,F)->F`、`id : ()->F` を渡します。

必要な法則は S のモノイド則、作用の恒等則・合成閉包・結合則、`mapping(id(),x) = x`、`mapping(composition(f,g),x) = mapping(f,mapping(g,x))`、`mapping(f,op(x,y)) = op(mapping(f,x),mapping(f,y))` です。ACL と同様、空区間の積は e を返します。長さ付きの区間和などでは、空区間の値も正しく表せる S を用意してください。

- `set/get/prod/all_prod/max_right/min_left` は SegTree と同じ意味です。
- `apply(p,f)` は点への作用、`apply_range(l,r,f)` は区間への作用です。C++ の `apply` オーバーロードを分けています。
- 構築 O(n)、`all_prod` O(1)、その他は O(log n)。`get` も必要な遅延伝播を実施するため O(log n) です。
- 合成順は **`composition(f,g) = f ∘ g`**。

## Math

| 関数 | 型と戻り値 | 前提条件・計算量 |
|---|---|---|
| `pow_mod(x,n,m)` | `(Int64,Int64,Int)->Int64`、`x^n mod m` | n ≥ 0、m ≥ 1、O(log n) |
| `inv_mod(x,m)` | `(Int64,Int64)->Int64`、`[0,m)` の逆元 | m ≥ 1、gcd(x,m)=1、O(log m) |
| `crt(r,m)` | `(Array[Int64],Array[Int64])->(Int64,Int64)` | 同じ長さ、各 m > 0、lcm が Int64 に収まること。O(k log M) |
| `floor_sum(n,m,a,b)` | すべて Int64、`Σ floor((a*i+b)/m)` | 0 ≤ n < 2³²、1 ≤ m < 2³²、O(log m) |

`crt` は解がなければ `(0,0)`、空入力なら `(0,1)`、通常は `(最小非負解, lcm)`。`floor_sum` は負の a/b も扱い、答えは 2⁶⁴ を法として wrap したビット列を Int64 として返します。中間積の wrap も含め ACL の unsigned 演算と合わせています。

## Modint

- `StaticModInt[M : Modulus]`：タグが `modulus() -> Int` を実装。常に同じ正の modulus を返してください。
- `DynamicModInt[Id : DynamicModulus]`：タグが `state() -> ModState` を実装。呼び出すたびに**同一インスタンス**を返してください。
- modulus は `1..=2147483647`。1 を法とする場合の唯一の値は 0 です。
- 定義済みエイリアス：`ModInt998244353`、`ModInt1000000007`、`ModInt = DynamicModInt[DefaultId]`。

| API | 仕様 |
|---|---|
| `new(Int)` | 正規化して構築 |
| `from_int64`, `from_uint`, `from_uint64` | 型の全範囲を正確に正規化 |
| `raw(Int)` | 0 ≤ x < mod が前提、剰余を取らず構築 |
| `val() -> Int` | 正規化された値 |
| `mod() -> Int` | インスタンスが属するタグの現在の modulus |
| `pow(Int64)` | 非負冪、O(log n) |
| `inv()` | gcd(val,mod)=1、O(log mod) |
| `+ - * /`、単項 `-`、`== !=` | 同じタグ同士の演算 |
| `Default`, `Zero` | 0 |

四則の代入演算 `+= -= *= /=` も利用できます。加減乗算は O(1)、除算は O(log mod)。C++ の暗黙整数変換・`++/--` は設けていません。必要に応じて ModInt の 1 を加減算します。

C++ の型上の `mod()` は MoonBit ではインスタンスメソッドです。既定の動的 modulus は `@ac.set_mod(m)`、独自 ID はその `ModState::set_mod(m)` で変更します。同じタグの古い値は変更後に再利用しないでください。modulus の変更をまたぐ Fenwick tree なども再構築が必要です。状態の並行更新を同期する機能はありません。

```moonbit
// 固定 modulus
 type Mod17
 impl @ac.Modulus for Mod17 with fn modulus() { 17 }

// 独立した動的 modulus
 type SessionId
 let session_mod : @ac.ModState = @ac.ModState::new(modulus=11)
 impl @ac.DynamicModulus for SessionId with fn state() { session_mod }

 test "custom moduli" {
   let a : @ac.StaticModInt[Mod17] = @ac.StaticModInt::new(20)
   assert_eq(a.val(), 3)
   session_mod.set_mod(13)
   let b : @ac.DynamicModInt[SessionId] = @ac.DynamicModInt::new(20)
   assert_eq(b.val(), 7)
 }
```

`Modulus` と `DynamicModulus` は open trait。`FlowInt` と `ModInput` はサポートする整数型を限定する sealed trait です。

## Convolution

- `convolution(a : Array[T], b : Array[T], modulus?=998244353) -> Array[T]`。T は Int / Int64 / UInt / UInt64。入力の負数と型の全範囲を正確に剰余化します。
- `convolution_modint(a : Array[StaticModInt[M]], b : Array[StaticModInt[M]])` は同じ固定タグの配列を返します。動的 ModInt の畳み込みは値を整数に取り出して `convolution(..., modulus=...)` を使います。
- modulus は正の Int に収まる素数（2〜2147483647）。非空時、`bit_ceil(n+m-1)` が `modulus-1` を割り切ることが必須です。998244353 なら出力長は 2²³ 以下。
- 片方が空なら空を返します。小入力では直接積、それ以外は radix-2 NTT。O((n+m) log(n+m))、領域 O(n+m)。未登録の素数では初回だけではなく**各呼び出し**で原始根を求めるため、modulus−1 の試し割りと原始根候補探索のセットアップコストが加わります。C++ の constexpr に相当する処理を実行時に行います。
- `convolution_ll(Array[Int64], Array[Int64]) -> Array[Int64]` は剰余ではない整数畳み込み。出力長 ≤ 2²⁴、すべての答えが Int64 に収まることが前提。3 素数 NTT と ACL の CRT 復元を用います。O((n+m) log(n+m))。

## SCC / Two SAT

`SccGraph::new(n)`、`add_edge(from,to)`、`scc() -> Array[Array[Int]]`。

追加は償却 O(1)、分解は O(n+m)、領域 O(n+m)。成分は縮約グラフのトポロジカル順です。異なる成分間の辺は前の成分から後ろの成分へ向かいます。互いに到達しない成分の順序は任意です。明示的スタックを用いた Tarjan 法で、長い有向路でも呼び出しスタックを消費しません。

`TwoSat::new(n)`、`add_clause(i,f,j,g)`、`satisfiable() -> Bool`、`answer() -> Array[Bool]`。

節は `(x[i] == f) OR (x[j] == g)`。追加は償却 O(1)、判定は O(n+m)、`answer` はコピーを返すため O(n)。充足する場合の割り当てだけが有効で、解が複数ある場合の選び方は保証しません。節の追加後には再度 `satisfiable` を呼んでください。

## Maxflow

`MfGraph[Cap]` の Cap は Int / Int64。

- `new(n)`、`add_edge(from,to,cap) -> Int`（追加した辺 ID）。容量は非負、自己ループ・多重辺に対応。
- `get_edge(i) -> MfEdge[Cap]`、`edges() -> Array[MfEdge[Cap]]`。フィールドは `from/to/cap/flow`。元の辺の挿入順で、返す値はスナップショットです。
- `change_edge(i,new_cap,new_flow)`：`0 <= new_flow <= new_cap`。全体のフロー保存則を保つ変更は呼び出し側の責任です。
- `flow(s,t,flow_limit?) -> Cap`：現在の残余グラフから**追加で**流した量。省略時は Cap の最大値。s≠t、limit ≥ 0。繰り返し実行可能です。
- `min_cut(s) -> Array[Bool]`：残余グラフで到達できる頂点。最大流を流し切った後なら最小カットを与えます。

Dinic 法、一般の `flow` は O(n²m)、領域 O(n+m)。全容量が 1 の場合は O(min(n^(2/3), √m)m)。明示的スタックで経路を探索します。`add_edge` は償却 O(1)、get/change は O(1)、edges は O(m)、min_cut は O(n+m)。返却する追加流量が Cap に収まることを保証してください。

## Mincostflow

`McfGraph[Cap,Cost]`：Cap と Cost は独立に Int / Int64 の 4 通り。

- `new(n)`、`add_edge(from,to,cap,cost) -> Int`。元の辺の容量と単価は **非負**。自己ループ・多重辺に対応。
- `get_edge(i)`、`edges()` は `McfEdge` のスナップショット。フィールドは `from/to/cap/flow/cost`。
- `flow(s,t,flow_limit?) -> (Cap,Cost)`：流量とその最小費用。
- `slope(s,t,flow_limit?) -> Array[(Cap,Cost)]`：`(0,0)` からの区分線形な最小費用曲線。同じ限界費用の連続区間は結合し、流量は狭義増加します。隣り合う点の間は線形補間できます。

s≠t、limit ≥ 0。**同じグラフに対する flow / slope は合計 1 回まで**です。これは ACL の前提条件を明示的に検査しています。流量は Cap、単価・最短路長・総費用は Cost に収まることが前提です。ACL の仕様上の上限として、n 頂点、最大単価 C に対し、Int なら `n*C <= 2*10^9+1000`、Int64 なら `n*C <= 8*10^18+1000` を満たしてください。内部計算は Int64 を用いますが、公開型の範囲保証を緩和するものではありません。

ポテンシャル付き Dijkstra と二分ヒープを用い、O(F(n+m) log(n+m))、領域 O(n+m)。F は流量（各反復で整数流量を 1 以上流す上限評価）。初期負コストの一般グラフは対象外です。構築・辺アクセスの計算量は Maxflow と同様です。

## String

| 入力 | Suffix array | LCP array | Z algorithm |
|---|---|---|---|
| `Array[T]` | `suffix_array`（T:Compare） | `lcp_array`（T:Eq） | `z_algorithm`（T:Eq） |
| `Array[Int]`, upper | `suffix_array_bounded` | 上と同じ | 上と同じ |
| `Bytes` | `suffix_array_bytes` | `lcp_array_bytes` | `z_algorithm_bytes` |
| `String` | `suffix_array_string` | `lcp_array_string` | `z_algorithm_string` |

全関数が `Array[Int]` を返します。suffix array は空 suffix を含まず n 要素、LCP は隣接 suffix の共通接頭辞長で n−1 要素、Z は n 要素で非空なら `z[0]=n`。suffix/Z は空入力を受け付け、LCP は n≥1 と同じ入力から作った有効な suffix array が必要です。LCP は長さと permutation を検査しますが、渡された配列が本当に辞書順であることまでは再検証しません。

- `suffix_array` は座標圧縮 + SA-IS、O(n log n)。T の比較が一貫した全順序であることが前提です。
- `suffix_array_bounded(s,upper)` は 0≤s[i]≤upper、upper≥0。O(n+upper)。upper 分の作業領域を確保します。
- Bytes 版は各 byte を **0〜255 の符号なし整数**として扱い、SA-IS は O(n)。
- String 版は UTF-8 に符号化して Bytes 版を呼びます。**位置も長さも UTF-8 byte 単位**で、継続 byte から始まる suffix も含みます。MoonBit の文字列スライスにそのまま渡す index ではありません。
- LCP は Kasai 法、Z は線形アルゴリズム、どちらも O(n)。領域はいずれも O(n)（bounded suffix array は追加 O(upper)）。

C++ の `std::string` の char 符号性に依存する挙動は移植せず、`ac-library-rs` 等の byte 列としての使い方に合わせています。C++ 差分テストも 0〜255 の整数配列として照合しています。