src/polynomial/BostanMori998.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

Verified with

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

Code

from src.convolution.NTT998 import NTT998
from src.math.modinv import modinv


def BostanMori998(P, Q, n):
    le = max(len(P), len(Q))
    le = 1 << (le - 1).bit_length()
    P.extend([0] * (le - len(P)))
    Q.extend([0] * (le - len(Q)))
    while n > 0:
        P.extend([0] * le)
        Q.extend([0] * le)
        R = [x * ((1, -1)[i & 1]) for i, x in enumerate(Q)]
        NTT998.butterfly(P)
        NTT998.butterfly(Q)
        NTT998.butterfly(R)

        P = [p * r % 998244353 for p, r in zip(P, R)]
        NTT998.butterfly_inv(P)
        P = P[n % 2 :: 2]

        Q = [q * r % 998244353 for q, r in zip(Q, R)]
        NTT998.butterfly_inv(Q)
        Q = Q[::2]

        n >>= 1
    return P[0] * modinv(Q[0], 998244353) % 998244353

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