結果

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

ソースコード

diff # 

MOD = 998244353

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

def main():
    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)
    
    # Compute y for x in 0..N
    y = []
    for x in range(N+1):
        matrix = []
        for i in range(N):
            row = [(M0[i][j] + x * M1[i][j]) % MOD for j in range(N)]
            matrix.append(row.copy())
        
        det = 1
        mat = [row.copy() for row in matrix]
        n = N
        for i in range(n):
            pivot = -1
            for j in range(i, n):
                if mat[j][i] != 0:
                    pivot = j
                    break
            if pivot == -1:
                det = 0
                break
            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
            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
        y.append(det)
    
    # Build Vandermonde matrix
    V = [[pow(x, k, MOD) for k in range(N+1)] for x in range(N+1)]
    
    # Solve V a = y using Gaussian elimination
    a = y.copy()
    for i in range(N+1):
        pivot = -1
        for j in range(i, N+1):
            if V[j][i] != 0:
                pivot = j
                break
        if pivot == -1:
            continue
        V[i], V[pivot] = V[pivot], V[i]
        a[i], a[pivot] = a[pivot], a[i]
        
        inv = pow(V[i][i], MOD-2, MOD)
        for k in range(i, N+1):
            V[i][k] = (V[i][k] * inv) % MOD
        a[i] = (a[i] * inv) % MOD
        
        for j in range(N+1):
            if j == i:
                continue
            factor = V[j][i]
            if factor == 0:
                continue
            for k in range(i, N+1):
                V[j][k] = (V[j][k] - factor * V[i][k]) % MOD
            a[j] = (a[j] - factor * a[i]) % MOD
    
    for coeff in a:
        print(coeff % MOD)

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