結果

問題 No.1907 DETERMINATION
ユーザー lam6er
提出日時 2025-03-26 15:54:08
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,969 bytes
コンパイル時間 327 ms
コンパイル使用メモリ 82,036 KB
実行使用メモリ 140,684 KB
最終ジャッジ日時 2025-03-26 15:55:00
合計ジャッジ時間 9,585 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 3 TLE * 1 -- * 59
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

MOD = 998244353

def determinant(matrix, n):
    mat = [row[:] for row in matrix]
    det = 1
    sign = 1
    for col in range(n):
        pivot = -1
        for row in range(col, n):
            if mat[row][col] != 0:
                pivot = row
                break
        if pivot == -1:
            return 0
        if pivot != col:
            mat[col], mat[pivot] = mat[pivot], mat[col]
            sign = -sign
        pivot_val = mat[col][col]
        det = (det * pivot_val) % MOD
        inv_pivot = pow(pivot_val, MOD - 2, MOD)
        for row in range(col + 1, n):
            factor = (mat[row][col] * inv_pivot) % MOD
            for c in range(col, n):
                mat[row][c] = (mat[row][c] - factor * mat[col][c]) % MOD
    det = (det * sign) % MOD
    return det

def main():
    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([x % MOD for x in row])
    
    M1 = []
    for _ in range(N):
        row = list(map(int, input[ptr:ptr+N]))
        ptr += N
        M1.append([x % MOD for x in row])
    
    # Precompute factorials
    fact = [1] * (N + 1)
    for i in range(1, N + 1):
        fact[i] = fact[i-1] * i % MOD
    
    # Compute y_i = det(M0 + x_i * M1) for x_i in 0..N
    y = []
    for x_val in range(N + 1):
        M = []
        for i in range(N):
            row = []
            for j in range(N):
                val = (M0[i][j] + x_val * M1[i][j]) % MOD
                row.append(val)
            M.append(row)
        det = determinant(M, N)
        y.append(det % MOD)
    
    # Compute d_i = factorial[i] * factorial[N -i] * (-1)^(N -i) mod MOD
    d = []
    for i in range(N + 1):
        term = (fact[i] * fact[N - i]) % MOD
        if (N - i) % 2 == 1:
            term = (-term) % MOD
        d.append(term)
    
    # Compute P(x) = product_{j=0 to N} (x - j)
    P = [1]
    for j in range(N + 1):
        new_P = [0] * (len(P) + 1)
        for k in range(len(P)):
            new_P[k] = (new_P[k] + P[k] * (-j)) % MOD
            new_P[k + 1] = (new_P[k + 1] + P[k]) % MOD
        P = new_P
    
    # Compute N_i(x) by dividing P by (x - i) for each i
    N_i_coeffs = []
    for i in range(N + 1):
        Q = [0] * (N + 1)
        Q[N] = P[N + 1]
        for k in range(N - 1, -1, -1):
            Q[k] = (P[k + 1] + i * Q[k + 1]) % MOD
        N_i_coeffs.append(Q)
    
    # Compute inverse of d[i]
    inv_d = [pow(di, MOD - 2, MOD) for di in d]
    
    # Compute coefficients a_0 to a_N
    a = [0] * (N + 1)
    for k in range(N + 1):
        total = 0
        for i in range(N + 1):
            term = (y[i] * inv_d[i]) % MOD
            term = (term * N_i_coeffs[i][k]) % MOD
            total = (total + term) % MOD
        a[k] = total % MOD
    
    for coeff in a:
        print(coeff)

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