結果

問題 No.1907 DETERMINATION
ユーザー qwewe
提出日時 2025-05-14 12:51:37
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,820 bytes
コンパイル時間 372 ms
コンパイル使用メモリ 82,712 KB
実行使用メモリ 140,956 KB
最終ジャッジ日時 2025-05-14 12:52:11
合計ジャッジ時間 7,927 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 3 TLE * 1 -- * 59
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
MOD = 998244353

def readints():
    return list(map(int, sys.stdin.readline().split()))

n = int(sys.stdin.readline())
M0 = []
for _ in range(n):
    M0.append(readints())
M1 = []
for _ in range(n):
    M1.append(readints())

def det(mat):
    n = len(mat)
    res = 1
    for i in range(n):
        pivot = -1
        for j in range(i, n):
            if mat[j][i] != 0:
                pivot = j
                break
        if pivot == -1:
            return 0
        mat[i], mat[pivot] = mat[pivot], mat[i]
        if i != pivot:
            res = (-res) % MOD
        inv = pow(mat[i][i], MOD-2, MOD)
        res = (res * mat[i][i]) % MOD
        for j in range(i+1, n):
            factor = (mat[j][i] * inv) % MOD
            for k in range(i, n):
                mat[j][k] = (mat[j][k] - factor * mat[i][k]) % MOD
    return res

points = []
for x in range(n+1):
    mat = []
    for i in range(n):
        row = []
        for j in range(n):
            val = (M0[i][j] + x * M1[i][j]) % MOD
            row.append(val)
        mat.append(row)
    points.append(det([row.copy() for row in mat]))

coeff = [0]*(n+1)
for i in range(n+1):
    xi = i
    yi = points[i]
    L = [0]*(n+1)
    L[0] = 1
    for k in range(n+1):
        if k == i:
            continue
        term = [0]*(n+2)
        term[0] = (-k) % MOD
        term[1] = 1
        new_L = [0]*(n+1)
        for deg in range(n+1):
            if L[deg] == 0:
                continue
            for d in range(2):
                new_L[deg + d] = (new_L[deg + d] + L[deg] * term[d]) % MOD
        inv = pow((xi - k) % MOD, MOD-2, MOD)
        for deg in range(n+1):
            new_L[deg] = new_L[deg] * inv % MOD
        L = new_L
    for j in range(n+1):
        coeff[j] = (coeff[j] + yi * L[j]) % MOD

for c in coeff:
    print(c)
0