結果

問題 No.1907 DETERMINATION
ユーザー lam6er
提出日時 2025-04-09 21:00:59
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,361 bytes
コンパイル時間 1,077 ms
コンパイル使用メモリ 82,584 KB
実行使用メモリ 67,072 KB
最終ジャッジ日時 2025-04-09 21:01:59
合計ジャッジ時間 10,183 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 3 TLE * 1 -- * 59
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

mod = 998244353

def main():
    n = int(sys.stdin.readline())
    m0 = []
    for _ in range(n):
        row = list(map(int, sys.stdin.readline().split()))
        m0.append(row)
    m1 = []
    for _ in range(n):
        row = list(map(int, sys.stdin.readline().split()))
        m1.append(row)
    
    y = []
    for x in range(n + 1):
        mat = []
        for i in range(n):
            row = [(m0[i][j] + x * m1[i][j]) % mod for j in range(n)]
            mat.append(row.copy())
        det = determinant(mat)
        y.append(det % mod)
    
    size = n + 1
    d = [[0] * size for _ in range(size)]
    for i in range(size):
        d[i][0] = y[i]
    for j in range(1, size):
        inv_j = pow(j, mod-2, mod)
        for i in range(size - j):
            numerator = (d[i+1][j-1] - d[i][j-1]) % mod
            d[i][j] = (numerator * inv_j) % mod
    
    newton_coeffs = [d[0][k] for k in range(size)]
    
    pre_poly = [[1]]
    for k in range(1, size):
        a = k - 1
        prev_poly = pre_poly[-1]
        new_poly = [0] * (len(prev_poly) + 1)
        for i in range(len(prev_poly)):
            new_poly[i+1] = prev_poly[i]
        for i in range(len(prev_poly)):
            new_poly[i] = (new_poly[i] - a * prev_poly[i]) % mod
        pre_poly.append(new_poly)
    
    result = [0] * size
    for k in range(size):
        coeff = newton_coeffs[k]
        current_p = pre_poly[k]
        for i in range(len(current_p)):
            result[i] = (result[i] + coeff * current_p[i]) % mod
    
    for coeff in result:
        print(coeff % mod)

def determinant(mat):
    n = len(mat)
    det = 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
        if pivot != i:
            mat[i], mat[pivot] = mat[pivot], mat[i]
            det = (-det) % mod
        inv = pow(mat[i][i], mod-2, mod)
        det = (det * mat[i][i]) % mod
        
        mat[i][i] = 1
        for j in range(i+1, n):
            mat[i][j] = (mat[i][j] * inv) % mod
        
        for j in range(i+1, n):
            factor = mat[j][i]
            for k in range(i, n):
                mat[j][k] = (mat[j][k] - factor * mat[i][k]) % mod
    return det % mod

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