結果

問題 No.1907 DETERMINATION
ユーザー gew1fw
提出日時 2025-06-12 17:07:16
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,628 bytes
コンパイル時間 572 ms
コンパイル使用メモリ 82,384 KB
実行使用メモリ 117,236 KB
最終ジャッジ日時 2025-06-12 17:07:30
合計ジャッジ時間 9,818 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 3 TLE * 1 -- * 59
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

MOD = 998244353

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

def determinant(matrix, mod):
    n = len(matrix)
    det = 1
    for i in range(n):
        max_row = i
        for j in range(i, n):
            if matrix[j][i] != 0:
                max_row = j
                break
        else:
            return 0
        if max_row != i:
            matrix[i], matrix[max_row] = matrix[max_row], matrix[i]
            det = (-det) % mod
        inv_pivot = pow(matrix[i][i], mod-2, mod)
        for j in range(i+1, n):
            factor = (matrix[j][i] * inv_pivot) % mod
            for k in range(i, n):
                matrix[j][k] = (matrix[j][k] - factor * matrix[i][k]) % mod
    for i in range(n):
        det = (det * matrix[i][i]) % mod
    return det

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)
    
    evaluated = []
    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)
        det = determinant([row[:] for row in mat], MOD)
        evaluated.append(det)
    
    x_values = list(range(N+1))
    y_values = evaluated
    
    denominators = []
    for i in range(N+1):
        denom = 1
        for j in range(N+1):
            if j != i:
                denom = (denom * (i - j)) % MOD
        denominators.append(denom)
    
    inv_denoms = [pow(den, MOD-2, MOD) for den in denominators]
    
    result = [0] * (N+1)
    for i in range(N+1):
        yi = y_values[i]
        inv_den = inv_denoms[i]
        
        poly = [1]
        for j in range(N+1):
            if j == i:
                continue
            x_j = j
            new_poly = [0] * (len(poly) + 1)
            for k in range(len(poly)):
                new_poly[k] = (new_poly[k] + poly[k] * (-x_j)) % MOD
                new_poly[k+1] = (new_poly[k+1] + poly[k]) % MOD
            poly = new_poly
        
        scaled_poly = [(coeff * inv_den) % MOD for coeff in poly]
        scaled_poly = [(coeff * yi) % MOD for coeff in scaled_poly]
        
        for k in range(len(scaled_poly)):
            if k <= N:
                result[k] = (result[k] + scaled_poly[k]) % MOD
    
    for coeff in result:
        print(coeff % MOD)
    
if __name__ == '__main__':
    main()
0