src/polynomial/berlekamp_massey_global_mod.py

View this file on GitHub
Last update: 2023-07-23 02:22:37+09:00
Link: View error logs on GitHub Actions

Depends on

src/math/modinv.py

Verified with

src/$tests/polynomial/berlekamp_massey_global_mod.test.py

Code

from src.math.modinv import modinv

MOD = 998244353


def berlekamp_massey_global_mod(A):
    n = len(A)
    B = [MOD - 1]
    C = [MOD - 1]
    y = 1
    for j in range(1, n + 1):
        l = len(C)
        m = len(B)
        x = 0
        for i in range(l):
            x += C[i] * A[j - l + i]
            x %= MOD
        B.append(0)
        m += 1
        if x == 0:
            continue
        freq = x * modinv(y, MOD) % MOD
        if l < m:
            tmp = C[:]
            C = [0] * (m - l) + C
            for i in range(m):
                C[m - 1 - i] -= freq * B[m - 1 - i]
                C[m - 1 - i] %= MOD
            B = tmp
            y = x
        else:
            for i in range(m):
                C[l - 1 - i] -= freq * B[m - 1 - i]
                C[l - 1 - i] %= MOD

    return C[::-1][1:]

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.11.4/x64/lib/python3.11/site-packages/onlinejudge_verify/documentation/build.py", line 81, in _render_source_code_stat
    bundled_code = language.bundle(
                   ^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.11.4/x64/lib/python3.11/site-packages/onlinejudge_verify/languages/python.py", line 108, in bundle
    raise NotImplementedError
NotImplementedError