添字 or による畳み込み
(NumberTheory/Convolution/or_convolve.py)

• View this file on GitHub
• Last update: 2021-06-21 01:35:29+09:00

Depends on

• 高速メビウス変換 (fast möbius transform) (NumberTheory/Convolution/mobius_transform.py)
• 高速ゼータ変換 (fast zeta transform) (NumberTheory/Convolution/zeta_transform.py)

Verified with

• TestCase/LibraryChecker/bitwise_and_convolution.or.test.py

Code

from NumberTheory.Convolution.zeta_transform import subset_zeta_transform
from NumberTheory.Convolution.mobius_transform import subset_mobius_transform
MOD = 998244353


def or_convolve(a, b):
    add = lambda x, y: (x + y) % MOD
    inv = lambda x: -x
    mul = lambda x, y: (x * y) % MOD

    a = subset_zeta_transform(a, add)
    b = subset_zeta_transform(b, add)
    res = [mul(v1, v2) for v1, v2 in zip(a, b)]
    res = subset_mobius_transform(res, add, inv)
    return res

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page