This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub Rin204/Library-Python
数列$A = [a_0, a_1, …]$が与えられた時,
$a_i \equiv \sum_{j=1}^d c_j a_{i-j} \pmod {\rm MOD}$を満たす長さ$d$の数列$C$を求めます.$d$は可能な限り最小なものを求めます.
C = berlekamp_massey(A, MOD)
def modinv(a, MOD): b = MOD u = 1 v = 0 while b > 0: t = a // b a -= t * b u -= t * v a, b = b, a u, v = v, u if a != 1: return -1 if u != 0: u += MOD return u def berlekamp_massey(A, MOD): 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