結果

問題 No.1907 DETERMINATION
ユーザー lam6er
提出日時 2025-04-16 00:31:47
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,496 bytes
コンパイル時間 220 ms
コンパイル使用メモリ 81,792 KB
実行使用メモリ 137,656 KB
最終ジャッジ日時 2025-04-16 00:33:42
合計ジャッジ時間 7,618 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 3 TLE * 1 -- * 59
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 998244353

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1

    M0 = []
    for _ in range(N):
        row = list(map(int, input[ptr:ptr+N]))
        ptr += N
        M0.append(row)
    
    M1 = []
    for _ in range(N):
        row = list(map(int, input[ptr:ptr+N]))
        ptr += N
        M1.append(row)
    
    # Compute determinants for x = 0, 1, ..., N
    y = []
    for x in range(N + 1):
        A = []
        for i in range(N):
            row = [(M0[i][j] + x * M1[i][j]) % MOD for j in range(N)]
            A.append(row)
        
        det = 1
        mat = [row.copy() for row in A]
        for i in range(N):
            # Find pivot
            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 and solve
    size = N + 1
    V = [[0] * size for _ in range(size)]
    for i in range(size):
        V[i][0] = 1
        for j in range(1, size):
            V[i][j] = (V[i][j-1] * i) % MOD
    # Augment with y
    for i in range(size):
        V[i].append(y[i])
    
    # Gaussian elimination
    for col in range(size):
        pivot = -1
        for row in range(col, size):
            if V[row][col] != 0:
                pivot = row
                break
        if pivot == -1:
            print(0)
            exit()
        V[col], V[pivot] = V[pivot], V[col]
        inv = pow(V[col][col], MOD - 2, MOD)
        for j in range(col, size + 1):
            V[col][j] = (V[col][j] * inv) % MOD
        for row in range(size):
            if row != col and V[row][col] != 0:
                factor = V[row][col]
                for j in range(col, size + 1):
                    V[row][j] = (V[row][j] - factor * V[col][j]) % MOD
    
    coefficients = [V[i][size] for i in range(size)]
    for coeff in coefficients:
        print(coeff)

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