# acl-cpp-python
English | [日本語](https://github.com/tatyam-prime/acl-cpp-python/blob/main/README_ja.md)
`acl-cpp-python` is a Python binding of the [AtCoder Library (ACL)](https://github.com/atcoder/ac-library) implemented in C++ using [nanobind](https://github.com/wjakob/nanobind).
## Installation
```bash
pip install acl-cpp-python
```
## Example
```python
from acl_cpp.convolution import convolution998244353
a = [1, 1]
b = convolution998244353(a, a)
print(*b) # 1 2 1
```
## Notes
- `segtree` and `lazysegtree` are not currently implemented. These structures abstract types and operations, and performance improvement is not expected if implemented in Python.
- Please use Python implementations of segment trees, such as <https://github.com/shakayami/ACL-for-python> or <https://github.com/not522/ac-library-python>.
- Be mindful of integer sizes. Refer to the [AC Library documentation](https://atcoder.github.io/ac-library/production/document_ja/) and ensure that for functions requiring the `int` type, the input values fall within the range of 32-bit signed integers, and for those requiring the `long long` type, the input values fall within the range of 64-bit signed integers. A `TypeError` will occur for out-of-range values.
- Be cautious of overflow. Most integers are implemented as 64-bit signed integers, and calculations exceeding this range may result in overflow and incorrect results.
## Documentation
Refer to the [AC Library documentation](https://atcoder.github.io/ac-library/production/document_ja/).
Differences from the C++ version are outlined below.
### Data Structures
#### `acl_cpp.fenwicktree`
Includes the class `fenwicktree.fenwick_tree` with `T = long long` and `fenwicktree.fenwick_tree_modint` with `T = modint`.
#### `acl_cpp.segtree`
Not available.
#### `acl_cpp.lazysegtree`
Not available.
#### `acl_cpp.string`
Includes a string version and one with `T = long long`.
### Mathematics
#### `acl_cpp.math`
- `pow_mod` is not available. Use `pow(x, n, m)` instead.
- `inv_mod` is not available. Use `pow(x, -1, m)` instead.
#### `acl_cpp.math.internal`
The following are available:
- `math.internal.barrett`
- <https://github.com/atcoder/ac-library/blob/fe9b6fca9ab4e1be946ea23a4e6a2a751cf4aaa2/atcoder/internal_math.hpp#L25>
- `math.internal.is_prime(n: int) -> bool:`
- <https://github.com/atcoder/ac-library/blob/fe9b6fca9ab4e1be946ea23a4e6a2a751cf4aaa2/atcoder/internal_math.hpp#L83>
- `math.internal.inv_gcd(a: long long, b: long long) -> (long long, long long):`
- <https://github.com/atcoder/ac-library/blob/fe9b6fca9ab4e1be946ea23a4e6a2a751cf4aaa2/atcoder/internal_math.hpp#L107>
- `math.internal.primitive_root(m: int) -> int:`
- <https://github.com/atcoder/ac-library/blob/fe9b6fca9ab4e1be946ea23a4e6a2a751cf4aaa2/atcoder/internal_math.hpp#L144C15-L144C29>
#### `acl_cpp.convolution`
The following functions are available:
- `convolution.convolution(a: list[modint.modint998244353], b: list[modint.modint998244353]) -> list[modint.modint998244353]:`
- `convolution.convolution(a: list[modint.modint], b: list[modint.modint]) -> list[modint.modint]:`
- Implements convolution for `modint`, not present in the C++ version.
- Note the condition for NTT-friendly mods: `(mod - 1) % (2 ** c) == 0` and `len(a) + len(b) - 1 <= 2 ** c`.
- `convolution.convolution(a: list[long long], b: list[long long], mod: int) -> list[long long]:`
- Specify `mod` as the third argument for integer mod convolution.
- Ensure the mod satisfies the NTT-friendly condition above.
- `convolution.convolution_ll(a: list[long long], b: list[long long]) -> list[long long]:`
#### `acl_cpp.convolution.internal`
The following functions, useful for accelerating FPS (Formal Power Series) computations, are available.
Unlike the C++ version, they do not modify the arguments and return values.
- `convolution.internal.butterfly(a: list[modint.modint998244353]) -> list[modint.modint998244353]:`
- `convolution.internal.butterfly(a: list[modint.modint]) -> list[modint.modint]:`
- `convolution.internal.butterfly_inv(a: list[modint.modint998244353]) -> list[modint.modint998244353]:`
- `convolution.internal.butterfly_inv(a: list[modint.modint]) -> list[modint.modint]:`
#### `acl_cpp.modint`
Includes `modint.modint998244353`, `modint.modint1000000007`, and `modint.modint`.
`static_modint` and `dynamic_modint` are not available.
TODO: Add support for creating multiple `dynamic_modint`.
Supports the notation `modint(10) ** 10`.
`str(modint(10))` converts the value directly to a string.
### Graph
#### `acl_cpp.dsu`
Includes `dsu.dsu`.
#### `acl_cpp.maxflow`
`Cap = long long`.
Includes `maxflow.mf_graph` and `maxflow.mf_graph.edge`.
#### `acl_cpp.mincostflow`
`Cap = Cost = long long`.
Includes `mincostflow.mcf_graph` and `mincostflow.mcf_graph.edge`.
#### `acl_cpp.scc`
Includes `scc.scc_graph`.
#### `acl_cpp.twosat`
Includes `twosat.two_sat`.
Raw data
{
"_id": null,
"home_page": "https://github.com/tatyam-prime/acl-cpp-python",
"name": "acl-cpp-python",
"maintainer": null,
"docs_url": null,
"requires_python": ">=3.9",
"maintainer_email": null,
"keywords": "AtCoder, AtCoder Library, ACL",
"author": "tatyam",
"author_email": null,
"download_url": "https://files.pythonhosted.org/packages/5f/d8/f00b80239be1fcab49a4b5745d6965559897e7c804204ae4eb6e6060148a/acl-cpp-python-0.2.0.tar.gz",
"platform": null,
"description": "# acl-cpp-python\n\nEnglish | [\u65e5\u672c\u8a9e](https://github.com/tatyam-prime/acl-cpp-python/blob/main/README_ja.md)\n\n`acl-cpp-python` is a Python binding of the [AtCoder Library (ACL)](https://github.com/atcoder/ac-library) implemented in C++ using [nanobind](https://github.com/wjakob/nanobind).\n\n## Installation\n\n```bash\npip install acl-cpp-python\n```\n\n## Example\n\n```python\nfrom acl_cpp.convolution import convolution998244353\n\na = [1, 1]\nb = convolution998244353(a, a)\nprint(*b) # 1 2 1\n```\n\n## Notes\n\n- `segtree` and `lazysegtree` are not currently implemented. These structures abstract types and operations, and performance improvement is not expected if implemented in Python.\n - Please use Python implementations of segment trees, such as <https://github.com/shakayami/ACL-for-python> or <https://github.com/not522/ac-library-python>.\n- Be mindful of integer sizes. Refer to the [AC Library documentation](https://atcoder.github.io/ac-library/production/document_ja/) and ensure that for functions requiring the `int` type, the input values fall within the range of 32-bit signed integers, and for those requiring the `long long` type, the input values fall within the range of 64-bit signed integers. A `TypeError` will occur for out-of-range values.\n- Be cautious of overflow. Most integers are implemented as 64-bit signed integers, and calculations exceeding this range may result in overflow and incorrect results.\n\n## Documentation\n\nRefer to the [AC Library documentation](https://atcoder.github.io/ac-library/production/document_ja/). \nDifferences from the C++ version are outlined below.\n\n### Data Structures\n\n#### `acl_cpp.fenwicktree`\n\nIncludes the class `fenwicktree.fenwick_tree` with `T = long long` and `fenwicktree.fenwick_tree_modint` with `T = modint`.\n\n#### `acl_cpp.segtree`\n\nNot available.\n\n#### `acl_cpp.lazysegtree`\n\nNot available.\n\n#### `acl_cpp.string`\n\nIncludes a string version and one with `T = long long`.\n\n### Mathematics\n\n#### `acl_cpp.math`\n\n- `pow_mod` is not available. Use `pow(x, n, m)` instead.\n- `inv_mod` is not available. Use `pow(x, -1, m)` instead.\n\n#### `acl_cpp.math.internal`\n\nThe following are available:\n\n- `math.internal.barrett` \n - <https://github.com/atcoder/ac-library/blob/fe9b6fca9ab4e1be946ea23a4e6a2a751cf4aaa2/atcoder/internal_math.hpp#L25>\n- `math.internal.is_prime(n: int) -> bool:` \n - <https://github.com/atcoder/ac-library/blob/fe9b6fca9ab4e1be946ea23a4e6a2a751cf4aaa2/atcoder/internal_math.hpp#L83>\n- `math.internal.inv_gcd(a: long long, b: long long) -> (long long, long long):` \n - <https://github.com/atcoder/ac-library/blob/fe9b6fca9ab4e1be946ea23a4e6a2a751cf4aaa2/atcoder/internal_math.hpp#L107>\n- `math.internal.primitive_root(m: int) -> int:` \n - <https://github.com/atcoder/ac-library/blob/fe9b6fca9ab4e1be946ea23a4e6a2a751cf4aaa2/atcoder/internal_math.hpp#L144C15-L144C29>\n\n#### `acl_cpp.convolution`\n\nThe following functions are available:\n\n- `convolution.convolution(a: list[modint.modint998244353], b: list[modint.modint998244353]) -> list[modint.modint998244353]:`\n- `convolution.convolution(a: list[modint.modint], b: list[modint.modint]) -> list[modint.modint]:`\n - Implements convolution for `modint`, not present in the C++ version.\n - Note the condition for NTT-friendly mods: `(mod - 1) % (2 ** c) == 0` and `len(a) + len(b) - 1 <= 2 ** c`.\n- `convolution.convolution(a: list[long long], b: list[long long], mod: int) -> list[long long]:`\n - Specify `mod` as the third argument for integer mod convolution.\n - Ensure the mod satisfies the NTT-friendly condition above.\n- `convolution.convolution_ll(a: list[long long], b: list[long long]) -> list[long long]:`\n\n#### `acl_cpp.convolution.internal`\n\nThe following functions, useful for accelerating FPS (Formal Power Series) computations, are available. \nUnlike the C++ version, they do not modify the arguments and return values.\n\n- `convolution.internal.butterfly(a: list[modint.modint998244353]) -> list[modint.modint998244353]:`\n- `convolution.internal.butterfly(a: list[modint.modint]) -> list[modint.modint]:`\n- `convolution.internal.butterfly_inv(a: list[modint.modint998244353]) -> list[modint.modint998244353]:`\n- `convolution.internal.butterfly_inv(a: list[modint.modint]) -> list[modint.modint]:`\n\n#### `acl_cpp.modint`\n\nIncludes `modint.modint998244353`, `modint.modint1000000007`, and `modint.modint`. \n`static_modint` and `dynamic_modint` are not available. \nTODO: Add support for creating multiple `dynamic_modint`.\n\nSupports the notation `modint(10) ** 10`. \n`str(modint(10))` converts the value directly to a string.\n\n### Graph\n\n#### `acl_cpp.dsu`\n\nIncludes `dsu.dsu`.\n\n#### `acl_cpp.maxflow`\n\n`Cap = long long`. \nIncludes `maxflow.mf_graph` and `maxflow.mf_graph.edge`.\n\n#### `acl_cpp.mincostflow`\n\n`Cap = Cost = long long`. \nIncludes `mincostflow.mcf_graph` and `mincostflow.mcf_graph.edge`.\n\n#### `acl_cpp.scc`\n\nIncludes `scc.scc_graph`.\n\n#### `acl_cpp.twosat`\n\nIncludes `twosat.two_sat`.\n",
"bugtrack_url": null,
"license": null,
"summary": "Python bindings for the AtCoder Library",
"version": "0.2.0",
"project_urls": {
"Homepage": "https://github.com/tatyam-prime/acl-cpp-python",
"Repository": "https://github.com/tatyam-prime/acl-cpp-python"
},
"split_keywords": [
"atcoder",
" atcoder library",
" acl"
],
"urls": [
{
"comment_text": "",
"digests": {
"blake2b_256": "5fd8f00b80239be1fcab49a4b5745d6965559897e7c804204ae4eb6e6060148a",
"md5": "1ea9096713d16c7c2cce32e3477bffa2",
"sha256": "31918b02fd71b8d95a1efaea94e94382af695d4e85675f4c86092c96ffa5d2a4"
},
"downloads": -1,
"filename": "acl-cpp-python-0.2.0.tar.gz",
"has_sig": false,
"md5_digest": "1ea9096713d16c7c2cce32e3477bffa2",
"packagetype": "sdist",
"python_version": "source",
"requires_python": ">=3.9",
"size": 27418,
"upload_time": "2024-12-15T23:09:41",
"upload_time_iso_8601": "2024-12-15T23:09:41.797830Z",
"url": "https://files.pythonhosted.org/packages/5f/d8/f00b80239be1fcab49a4b5745d6965559897e7c804204ae4eb6e6060148a/acl-cpp-python-0.2.0.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2024-12-15 23:09:41",
"github": true,
"gitlab": false,
"bitbucket": false,
"codeberg": false,
"github_user": "tatyam-prime",
"github_project": "acl-cpp-python",
"travis_ci": false,
"coveralls": false,
"github_actions": true,
"lcname": "acl-cpp-python"
}
JSON
