結果
| 問題 | No.1907 DETERMINATION |
| コンテスト | |
| ユーザー |
 えりす
|
| 提出日時 | 2026-06-03 01:32:00 |
| 言語 | PyPy3 (7.3.17) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 5,492 bytes |
| 記録 | |
| コンパイル時間 | 507 ms |
| コンパイル使用メモリ | 85,248 KB |
| 実行使用メモリ | 152,432 KB |
| 最終ジャッジ日時 | 2026-06-03 01:32:43 |
| 合計ジャッジ時間 | 12,386 ms |
|
ジャッジサーバーID （参考情報） |
judge2_1 / judge1_1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 6 TLE * 1 -- * 56 |
ソースコード
import sys, random
MOD = 998244353
def mat_mul(a, b, n):
c = [[0] * n for _ in range(n)]
for i in range(n):
ai = a[i]
ci = c[i]
for k in range(n):
aik = ai[k]
if aik:
bk = b[k]
for j in range(n):
ci[j] = (ci[j] + aik * bk[j]) % MOD
return c
def mat_vec_mul(a, v, n):
res = [0] * n
for i in range(n):
s = 0
ai = a[i]
vi = v
for j in range(n):
s = (s + ai[j] * vi[j]) % MOD
res[i] = s
return res
def mat_det(a, n):
res = 1
for i in range(n):
ai = a[i]
if ai[i] == 0:
for j in range(i + 1, n):
if a[j][i]:
a[i], a[j] = a[j], a[i]
res = (-res) % MOD
ai = a[i]
break
else:
return 0
inv = pow(ai[i], MOD - 2, MOD)
res = res * ai[i] % MOD
for j in range(i + 1, n):
aj = a[j]
if aj[i]:
f = aj[i] * inv % MOD
for k in range(i, n):
aj[k] = (aj[k] - f * ai[k]) % MOD
return res
def mat_inv(a, n):
b = [[0] * n for _ in range(n)]
for i in range(n):
b[i][i] = 1
a = [row[:] for row in a]
for i in range(n):
ai = a[i]
bi = b[i]
if ai[i] == 0:
for j in range(i + 1, n):
if a[j][i]:
a[i], a[j] = a[j], a[i]
b[i], b[j] = b[j], b[i]
ai = a[i]
bi = b[i]
break
inv_val = pow(ai[i], MOD - 2, MOD)
for j in range(n):
ai[j] = ai[j] * inv_val % MOD
bi[j] = bi[j] * inv_val % MOD
for j in range(n):
if i != j:
aj = a[j]
f = aj[i]
if f:
bj = b[j]
for k in range(n):
aj[k] = (aj[k] - f * ai[k]) % MOD
bj[k] = (bj[k] - f * bi[k]) % MOD
return b
def berlekamp_massey(s, mod):
n = len(s)
c = [1]
b = [1]
l = 0
m = 1
inv_b = 1
for i in range(n):
d = s[i]
for j in range(1, l + 1):
d = (d + c[j] * s[i - j]) % mod
if d == 0:
m += 1
else:
t = c[:]
coef = d * pow(inv_b, mod - 2, mod) % mod
while len(c) < len(b) + m:
c.append(0)
for j in range(len(b)):
c[j + m] = (c[j + m] - coef * b[j]) % mod
if 2 * l <= i:
l = i + 1 - l
b = t
inv_b = d
m = 1
else:
m += 1
return c[:l + 1]
def solve():
random.seed(42)
it = iter(sys.stdin.buffer.read().split())
n = int(next(it))
a = [[0] * n for _ in range(n)]
b = [[0] * n for _ in range(n)]
for i in range(n):
for j in range(n):
a[i][j] = int(next(it))
for i in range(n):
for j in range(n):
b[i][j] = int(next(it))
t = 0
while t <= n:
atb = [[(a[i][j] + t * b[i][j]) % MOD for j in range(n)] for i in range(n)]
det_atb = mat_det([row[:] for row in atb], n)
if det_atb != 0:
break
t += 1
if det_atb == 0:
for i in range(n + 1):
print(0)
return
inv_atb = mat_inv(atb, n)
c = mat_mul(inv_atb, b, n)
v = [random.randrange(1, MOD) for _ in range(n)]
seq = [0] * (2 * n)
w = v[:]
for i in range(2 * n):
seq[i] = w[0]
w = mat_vec_mul(c, w, n)
poly = berlekamp_massey(seq, MOD)
poly.reverse()
deg = len(poly) - 1
ok = (deg == n)
if not ok:
y_vals = [0] * (n + 1)
for x in range(n + 1):
mx = [[(a[i][j] + x * b[i][j]) % MOD for j in range(n)] for i in range(n)]
y_vals[x] = mat_det([row[:] for row in mx], n)
if ok:
y_coef = [0] * (n + 1)
for j in range(n + 1):
sign = 1 if j % 2 == 0 else MOD - 1
y_coef[j] = sign * poly[deg - j] % MOD * det_atb % MOD
c_nk = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(n + 1):
c_nk[i][0] = c_nk[i][i] = 1
for j in range(1, i):
c_nk[i][j] = (c_nk[i - 1][j - 1] + c_nk[i - 1][j]) % MOD
pow_t = [1] * (n + 1)
for i in range(1, n + 1):
pow_t[i] = pow_t[i - 1] * (-t) % MOD
ans = [0] * (n + 1)
for k in range(n + 1):
for j in range(k, n + 1):
coef = y_coef[j] * c_nk[j][k] % MOD * pow_t[j - k] % MOD
ans[k] = (ans[k] + coef) % MOD
for v in ans:
print(v)
else:
dd = y_vals[:]
for k in range(1, n + 1):
for i in range(n, k - 1, -1):
dd[i] = (dd[i] - dd[i - 1]) * pow(k, MOD - 2, MOD) % MOD
stir = [[0] * (n + 1) for _ in range(n + 1)]
stir[0][0] = 1
for i in range(1, n + 1):
for j in range(1, i + 1):
stir[i][j] = (stir[i - 1][j - 1] - (i - 1) * stir[i - 1][j]) % MOD
ans = [0] * (n + 1)
for k in range(n + 1):
for j in range(k, n + 1):
ans[k] = (ans[k] + dd[j] * stir[j][k]) % MOD
for v in ans:
print(v)
if __name__ == '__main__':
solve()