This documentation is automatically generated by online-judge-tools/verification-helper
# verification-helper: PROBLEM https://judge.yosupo.jp/problem/find_linear_recurrence
from pathlib import Path
import sys
sys.path.append(str(Path(__file__).resolve().parent.parent.parent.parent))
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:]
n = int(input())
if n == 0:
A = []
else:
A = list(map(int, input().split()))
C = berlekamp_massey(A, 998244353)
print(len(C))
print(*C)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