高速ゼータ変換 (fast zeta transform)
(NumberTheory/Convolution/zeta_transform.py)

• View this file on GitHub
• Last update: 2021-06-20 22:49:02+09:00

Required by

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

Verified with

• TestCase/unittest/zeta_mobius_transform.unittest.test.py

Code

def subset_zeta_transform(a, op):
    n = len(a)
    res = a[:]
    for k in range((n - 1).bit_length()):
        bit = 1 << k
        for i in range(n):
            if i & bit:
                res[i] = op(res[i & ~bit], res[i])
    return res


def superset_zeta_transform(a, op):
    n = len(a)
    res = a[:]
    for k in range((n - 1).bit_length()):
        bit = 1 << k
        for i in range(n):
            if i & bit:
                res[i & ~bit] = op(res[i & ~bit], res[i])
    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