TestCase/unittest/zeta_mobius_transform.unittest.test.py

• View this file on GitHub
• Last update: 2021-06-20 22:49:02+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A

Depends on

• 高速メビウス変換 (fast möbius transform) (NumberTheory/Convolution/mobius_transform.py)
• 高速ゼータ変換 (fast zeta transform) (NumberTheory/Convolution/zeta_transform.py)
• 乱数生成 (Xorshift) (misc/xorshift.py)

Code

# verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A
import sys
input = sys.stdin.buffer.readline

from NumberTheory.Convolution.zeta_transform import subset_zeta_transform, superset_zeta_transform
from NumberTheory.Convolution.mobius_transform import subset_mobius_transform, superset_mobius_transform
from misc.xorshift import xorshift32


def naive_subset_zeta_transform(a, op):
    """O(N^2) naive calculation"""
    n = len(a)
    res = a[:]
    for i in range(n):
        for j in range(n):
            if i != j and i & j == j:
                res[i] = op(res[i], a[j])
    return res


def naive_superset_zeta_transform(a, op):
    """O(N^2) naive calculation"""
    n = len(a)
    res = a[:]
    for i in range(n):
        for j in range(n):
            if i != j and i | j == j:
                res[i] = op(res[i], a[j])
    return res


def group_test(arr, op, inv):
    sub_zeta = subset_zeta_transform(arr, op)
    naive_sub_zeta = naive_subset_zeta_transform(arr, op)
    assert(sub_zeta == naive_sub_zeta)

    sup_zeta = superset_zeta_transform(arr, op)
    naive_sup_zeta = naive_superset_zeta_transform(arr, op)
    assert(sup_zeta == naive_sup_zeta)

    sub_mobius = subset_mobius_transform(sub_zeta, op, inv)
    assert(arr == sub_mobius)

    sup_mobius = superset_mobius_transform(sup_zeta, op, inv)
    assert(arr == sup_mobius)


def monoid_test(arr, op):
    sub_zeta = subset_zeta_transform(arr, op)
    naive_sub_zeta = naive_subset_zeta_transform(arr, op)
    assert(sub_zeta == naive_sub_zeta)

    sup_zeta = superset_zeta_transform(arr, op)
    naive_sup_zeta = naive_superset_zeta_transform(arr, op)
    assert(sup_zeta == naive_sup_zeta)


def main():
    rand32 = xorshift32()
    arr = [rand32() for i in range(1000)]

    op = lambda x, y: x + y
    inv = lambda x: -x
    group_test(arr, op, inv)

    monoid_test(arr, max)


if __name__ == '__main__':
    main()
    print("Hello World")

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