添字 lcm による畳み込み
(NumberTheory/Convolution/lcm_convolve.py)

• View this file on GitHub
• Last update: 2022-07-31 17:54:32+09:00

Depends on

• 約数/倍数を集合とした累積和/差分 (NumberTheory/Convolution/multiple_divisor_transform.py)

Verified with

• TestCase/LibraryChecker/lcm_convolution.test.py

Code

from NumberTheory.Convolution.multiple_divisor_transform import (
    divisor_zeta_transform,
    divisor_mobius_transform
)
MOD = 998244353


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

    a = divisor_zeta_transform(a, add)
    b = divisor_zeta_transform(b, add)
    res = [mul(v1, v2) for v1, v2 in zip(a, b)]
    res = divisor_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