acl-cpp-python
English | 日本語
acl-cpp-python is a package that binds the AtCoder Library (ACL) implemented in C++ to Python. Internally, it is implemented in C++, so you can use fast convolutions, flows, string algorithms, etc. from Python.
How to install
python3 -m pip install acl-cpp-python
If you get error: externally-managed-environment:
Create a virtual environment in the folder you want to run it in, and try again.
If you find virtual environments cumbersome and want to use it anywhere, execute:
python3 -m pip install acl-cpp-python --break-system-packages
How to update
python3 -m pip install --upgrade acl-cpp-python
Examples
from acl_cpp.convolution import convolution998244353
a = [1, 1]
b = convolution998244353(a, a)
print(b) # [1, 2, 1]
from acl_cpp.string import z_algorithm
a = z_algorithm("abacaba")
print(a) # [7, 0, 1, 0, 3, 0, 1]
Notes
There is an overhead in converting data between C++ and Python, so the longer the execution time of a function, the more speedup can be expected.
segtree,lazysegtree, andmodintare not currently implemented because they are not expected to speed up.Be careful of overflow. Many integers are implemented as 64-bit signed integers, so calculations beyond this range will cause overflow and incorrect results.
In the documentation,
long long(64-bit signed integer) is denoted asll.