🥮 mooncakes.io

    ac-library-mbt

    A complete MoonBit port of AtCoder Library v1.6

    Download zip
    Author
    Version
    0.1.0
    License
    CC0-1.0
    Last updated
    20 hours ago
    Downloads
    7

    #ac-library-mbt

    AtCoder Library v1.6 の MoonBit 移植です。ACL の全 12 カテゴリを実装し、半開区間・境界探索・作用の合成順・フローの追加実行など、公開 API の意味を踏襲しています。ライブラリの依存は MoonBit core のみです。

    ACLMoonBit の公開 API
    dsuDsu
    fenwicktreeFenwickTree[T]
    segtreeSegTree[S]
    lazysegtreeLazySegTree[S, F]
    mathpow_mod, inv_mod, crt, floor_sum
    modintStaticModInt[M], DynamicModInt[Id]、定番の型エイリアス
    convolutionconvolution, convolution_modint, convolution_ll
    maxflowMfGraph[Cap], MfEdge[Cap]
    mincostflowMcfGraph[Cap, Cost], McfEdge[Cap, Cost]
    sccSccGraph
    twosatTwoSat
    stringsuffix array / LCP / Z：配列・Bytes・String

    #開発・検証

    Python 3.12 以上、C/C++ コンパイラ、Node.js 22 を用意してください。セットアップは公式配布物の SHA256 を検証し、このディレクトリの .tools/moon にインストールします。シェルの設定は変更しません。Linux x86_64 / aarch64、macOS aarch64 に対応しています。

    python3 scripts/setup.py
scripts/moon test --target all
scripts/check.sh

    固定バージョンは moonc v0.10.12+1634b282e (2026-09-07)。コンパイラと core の対応、配布物のハッシュは moonbit-toolchain.json に記録しています。scripts/moon はローカルのツールチェーンを優先し、なければ PATH 上の moon を使います。

    検証対象は native / js / wasm / wasm-gc の debug・release。C++ ACL と照合した 1,186 ケース、独立した全探索・ランダムテスト、上流の境界回帰ケース、長さ 100,000 の入力、Practice2 全問の公式サンプル 18 件を含みます。検証手順 を参照してください。

    #使い方

    モジュール名は manabeai/ac-library-mbt です。Mooncakes から追加する場合は、利用側のプロジェクトで次を実行します。

    moon add manabeai/ac-library-mbt@0.1.0

    ローカルのソースを依存として使う場合は、両方のモジュールを moon.work の members に登録し、利用側の moon.mod に依存を書きます。

    // moon.work（両モジュールの親ディレクトリ）
    members = [ "ac-library-mbt", "solution" ]

    // solution/moon.mod
    name = "local/solution"
    import { "manabeai/ac-library-mbt@0.1.0" }

    // solution/moon.pkg（または source 配下の moon.pkg）
    import { "manabeai/ac-library-mbt" @ac }

    root パッケージは全公開 API を再公開します。必要なカテゴリだけを import することもできます。

    import { "manabeai/ac-library-mbt/segtree" @segtree }

    #Fenwick tree と segment tree

    let fw : @ac.FenwickTree[Int64] = @ac.FenwickTree::new(5)
    fw.add(2, 10L)
    assert_eq(fw.sum(1, 4), 10L)

    let seg = @ac.SegTree::from_array(
      [1, 3, 2, 5],
      op=Int::max,
      e=() => -1,
    )
    assert_eq(seg.prod(1, 3), 3)
    assert_eq(seg.max_right(0, maximum => maximum < 5), 3)

    演算はコンストラクタにクロージャとして渡します。SegTree の値には trait 制約がありません。FenwickTree は Zero + Add + Sub を要求します。Debug は必要な型が実装しているときだけ利用でき、データ構造そのものの利用条件には含めていません。

    #Lazy segment tree：区間 affine 変換・区間和

    let tree : @ac.LazySegTree[(Int64, Int), (Int64, Int64)] =
      @ac.LazySegTree::from_array(
        [(1L, 1), (2L, 1), (3L, 1)],
        op=(a, b) => (a.0 + b.0, a.1 + b.1),
        e=() => (0L, 0),
        mapping=(f, x) => (f.0 * x.0 + f.1 * x.1.to_int64(), x.1),
        composition=(f, g) => (f.0 * g.0, f.0 * g.1 + f.1),
        id=() => (1L, 0L),
      )
    tree.apply_range(0, 2, (2L, 1L))
    assert_eq(tree.prod(0, 3).0, 11L)

    composition(f, g) は g を適用してから f を適用する作用です。

    #Modint

    let a : @ac.ModInt998244353 = @ac.StaticModInt::new(10)
    let b : @ac.ModInt998244353 = @ac.StaticModInt::new(3)
    assert_eq((a / b * b).val(), 10)
    assert_eq(a.pow(3L).val(), 1000)

    @ac.set_mod(11)
    let x : @ac.ModInt = @ac.DynamicModInt::new(15)
    assert_eq(x.val(), 4)
    assert_eq(x.mod(), 11)

    コンストラクタには結果の型注釈を付けます。型エイリアス名からの ModInt998244353::new(...) だけでは、固定した modulus の型パラメータを推論できない場合があります。独自の固定 modulus と、ID ごとに独立する動的 modulus の定義例は API 仕様 にあります。

    #畳み込み・文字列

    assert_eq(@ac.convolution([1L, 2L], [3L, 4L]), [3L, 10L, 8L])
    assert_eq(@ac.convolution_ll([-1L, 2L], [3L, -4L]), [-3L, 10L, -8L])
    assert_eq(@ac.suffix_array_string("banana"), [5, 3, 1, 0, 4, 2])

    String 版の index と LCP/Z の長さは UTF-8 のバイト単位です。MoonBit String の UTF-16 index と混同しないでください。コードポイント単位が必要なら s.iter().to_array() を汎用配列版に渡します。

    #仕様・利用例

    #ライセンスと上流

    実装は CC0-1.0。基準とした上流は ACL v1.6 / 864245a00b00dd008d1abfdc239618fdb7d139da です。tests/reference/UPSTREAM に記録した未改変ヘッダを C++ 差分テストに使用しています。公式サンプルはテストデータとして出典 URL とともに保存しており、AtCoder の問題文・サンプルに本リポジトリの CC0 を適用するものではありません。

    DefaultId

    source

    Dsu

    source

    Disjoint sets with union by size and path compression.

    DynamicModInt

    source

    Immutable residue in [0, modulus).

    DynamicModulus

    source

    Each tag must return the same ModState instance on every call. Changing its modulus invalidates all existing residues for that tag, as in ACL.

    FenwickTree

    source

    Fenwick tree over an abelian additive group. Integer arithmetic wraps at its bit width.

    FlowInt

    source

    Signed capacity/cost types supported by flow algorithms.

    LazySegTree

    source

    Lazy monoid tree. composition(f,g) means f after g. All callbacks must be pure.

    McfEdge

    source

    Immutable snapshot of an original edge.

    McfGraph

    source

    Minimum-cost flow with nonnegative original costs. Capacity and cost can independently be Int or Int64.

    MfEdge

    source

    Immutable snapshot of an original edge.

    MfGraph

    source

    Dinic's maximum-flow graph with Int or Int64 capacities.

    Mod1000000007

    source

    Mod998244353

    source

    ModInput

    source

    Lossless modular reduction of the four ACL integer types.

    ModInt

    source

    Immutable residue in [0, modulus).

    ModInt1000000007

    source

    Immutable residue in [0, modulus).

    ModInt998244353

    source

    Immutable residue in [0, modulus).

    ModState

    source

    Independent mutable modulus shared by all values of a dynamic tag.

    Modulus

    source

    A fixed, positive Int modulus. A tag must always return the same modulus.

    SccGraph

    source

    Directed graph. SCC enumeration is O(n+m), with an explicit DFS stack.

    SegTree

    source

    A monoid segment tree. op and e must be pure; op need not commute.

    StaticModInt

    source

    Immutable residue in [0, modulus).

    TwoSat

    source

    Boolean 2-SAT over clauses (x_i = f) OR (x_j = g).

    Zero

    source

    Additive identity. Implementations used in Fenwick trees must form an abelian group.

    convolution

    source
    fn[T : 
    ModInput    ] convolution(a : Array[T], b : Array[T], modulus? : Int) -> Array[T]

    Modular convolution for Int, UInt, Int64, UInt64. Empty inputs yield []. Requires a prime positive Int modulus and next_power_of_two(n+m-1) dividing modulus-1.

    convolution_ll

    source
    fn convolution_ll(a : Array[Int64], b : Array[Int64]) -> Array[Int64]

    Exact signed Int64 convolution; each output must fit Int64, length <= 2^24.

    convolution_modint

    source

    crt

    source
    fn crt(remainders : Array[Int64], moduli : Array[Int64]) -> (Int64, Int64)

    Chinese remainder theorem. Returns (0,0) if inconsistent, (0,1) for no constraints. Positive moduli and their LCM must fit Int64.

    floor_sum

    source
    fn floor_sum(n : Int64, m : Int64, a : Int64, b : Int64) -> Int64

    Sum floor((a*i+b)/m), 0 <= i < n. The result wraps modulo 2^64. Requires 0 <= n < 2^32, 1 <= m < 2^32. O(log m).

    inv_mod

    source
    fn inv_mod(x : Int64, m : Int64) -> Int64

    Multiplicative inverse in [0,m); requires m >= 1 and gcd(x,m) = 1.

    lcp_array

    source
    fn[T : Eq] lcp_array(s : Array[T], sa : Array[Int]) -> Array[Int]

    Adjacent suffix LCP lengths. Requires nonempty s and its suffix array. O(n).

    lcp_array_bytes

    source
    fn lcp_array_bytes(s : Bytes, sa : Array[Int]) -> Array[Int]

    lcp_array_string

    source
    fn lcp_array_string(s : String, sa : Array[Int]) -> Array[Int]

    pow_mod

    source
    fn pow_mod(x : Int64, n : Int64, m : Int) -> Int64

    x^n modulo m, for n >= 0 and m >= 1. O(log n).

    set_mod

    source
    fn set_mod(modulus : Int) -> Unit

    Sets the modulus of the default ModInt tag. Custom tags use ModState::set_mod.

    suffix_array

    source
    fn[T : Compare + Eq] suffix_array(s : Array[T]) -> Array[Int]

    Suffix array for ordered values, using coordinate compression. O(n log n).

    suffix_array_bounded

    source
    fn suffix_array_bounded(s : Array[Int], upper : Int) -> Array[Int]

    SA-IS for integers in [0,upper]. O(n+upper).

    suffix_array_bytes

    source
    fn suffix_array_bytes(s : Bytes) -> Array[Int]

    Unsigned byte lexicographic order. O(n).

    suffix_array_string

    source
    fn suffix_array_string(s : String) -> Array[Int]

    UTF-8 byte offsets, NOT MoonBit String (UTF-16) indices.

    z_algorithm

    source
    fn[T : Eq] z_algorithm(s : Array[T]) -> Array[Int]

    LCP of every suffix with the whole sequence. z[0] = n; empty input yields []. O(n).

    z_algorithm_bytes

    source
    fn z_algorithm_bytes(s : Bytes) -> Array[Int]

    z_algorithm_string

    source
    fn z_algorithm_string(s : String) -> Array[Int]

    Source Files

    Powered by MoonBit

    Site sourceReport issuePackagesBuild queueSkillsStatistics

    © 2026 mooncakes.io