結果

問題 No.1907 DETERMINATION
コンテスト
ユーザー lam6er
提出日時 2025-03-20 20:56:53
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,771 bytes
コンパイル時間 368 ms
コンパイル使用メモリ 82,172 KB
実行使用メモリ 134,440 KB
最終ジャッジ日時 2025-03-20 20:57:03
合計ジャッジ時間 9,352 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 3 TLE * 1 -- * 59
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

mod = 998244353

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

def main():
    import sys
    data = readints()
    ptr = 0
    N = data[ptr]
    ptr +=1
    
    M0 = []
    for _ in range(N):
        row = data[ptr:ptr+N]
        ptr += N
        M0.append(row)
    
    M1 = []
    for _ in range(N):
        row = data[ptr:ptr+N]
        ptr += N
        M1.append(row)
    
    x_values = list(range(N+1))
    y_values = []
    
    for x in x_values:
        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)
        
        det = 1
        mat_copy = [row.copy() for row in mat]
        n = N
        for i in range(n):
            pivot = -1
            for j in range(i, n):
                if mat_copy[j][i] != 0:
                    pivot = j
                    break
            if pivot == -1:
                det = 0
                break
            
            if pivot != i:
                mat_copy[i], mat_copy[pivot] = mat_copy[pivot], mat_copy[i]
                det = (-det) % mod
            
            inv = pow(mat_copy[i][i], mod-2, mod)
            for j in range(i+1, n):
                factor = (mat_copy[j][i] * inv) % mod
                for k in range(i, n):
                    mat_copy[j][k] = (mat_copy[j][k] - factor * mat_copy[i][k]) % mod
            
            det = (det * mat_copy[i][i]) % mod
        
        y_values.append(det)
    
    V = []
    for x in x_values:
        row = [1] * (N+1)
        current = x
        row[1] = current
        for j in range(2, N+1):
            current = (current * x) % mod
            row[j] = current
        V.append(row)
    
    A = [row.copy() for row in V]
    for i in range(N+1):
        A[i].append(y_values[i])
    
    for col in range(N+1):
        pivot = -1
        for row in range(col, N+1):
            if A[row][col] != 0:
                pivot = row
                break
        if pivot == -1:
            continue
        if pivot != col:
            A[col], A[pivot] = A[pivot], A[col]
        
        inv = pow(A[col][col], mod-2, mod)
        for j in range(col, N+2):
            A[col][j] = (A[col][j] * inv) % mod
        
        for row in range(N+1):
            if row == col or A[row][col] == 0:
                continue
            factor = A[row][col]
            for j in range(col, N+2):
                A[row][j] = (A[row][j] - factor * A[col][j]) % mod
    
    coefficients = [0]*(N+1)
    for i in range(N+1):
        coefficients[i] = A[i][N+1]
    
    for coeff in coefficients:
        print(coeff % mod)

if __name__ == '__main__':
    main()
0