結果

問題 No.1907 DETERMINATION
ユーザー qwewe
提出日時 2025-05-14 13:25:31
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 4,731 bytes
コンパイル時間 269 ms
コンパイル使用メモリ 82,052 KB
実行使用メモリ 115,504 KB
最終ジャッジ日時 2025-05-14 13:26:29
合計ジャッジ時間 7,789 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 3 TLE * 1 -- * 59
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def solve():
    N = int(sys.stdin.readline())
    M0_orig = []
    for _ in range(N):
        M0_orig.append(list(map(int, sys.stdin.readline().split())))
    M1_orig = []
    for _ in range(N):
        M1_orig.append(list(map(int, sys.stdin.readline().split())))

    MOD = 998244353

    eval_points_x = []
    eval_points_y = []

    for k_eval in range(N + 1):
        x_val = k_eval
        
        current_M_rows = [[(M0_orig[r][c] + x_val * M1_orig[r][c]) % MOD for c in range(N)] for r in range(N)]
        
        # Compute determinant of current_M_rows using Gaussian elimination
        mat = [row[:] for row in current_M_rows]
        
        det = 1
        
        for j in range(N): # Iterate through columns (for pivot mat[j][j])
            pivot_row_idx = j
            # Find a non-zero pivot in column j at or below row j
            while pivot_row_idx < N and mat[pivot_row_idx][j] == 0:
                pivot_row_idx += 1
            
            if pivot_row_idx == N: # No non-zero pivot found
                det = 0
                break
            
            if pivot_row_idx != j:
                mat[j], mat[pivot_row_idx] = mat[pivot_row_idx], mat[j]
                det = (MOD - det) % MOD # Swapped rows, so negate determinant
            
            # Pivot element is mat[j][j]
            det = (det * mat[j][j]) % MOD
            
            if det == 0: # If accumulated det becomes 0, can stop early
                 break

            inv_pivot_val = pow(mat[j][j], MOD - 2, MOD)
            
            # Eliminate other entries in column j (only for rows below pivot)
            for r_idx in range(j + 1, N):
                if mat[r_idx][j] != 0:
                    factor = (mat[r_idx][j] * inv_pivot_val) % MOD
                    # mat[r_idx][j] will become 0
                    for c_idx in range(j, N): # Iterate from current column to the right
                        mat[r_idx][c_idx] = (mat[r_idx][c_idx] - factor * mat[j][c_idx]) % MOD
        
        eval_points_x.append(x_val)
        eval_points_y.append(det)

    # Polynomial interpolation using Newton's divided differences
    # x_k = k for k = 0, ..., N
    # f_coeffs[k] will store c_k = [y_0, ..., y_k]
    
    f_coeffs = list(eval_points_y) # Initially f_coeffs[i] = y_i
    
    inv_k_plus_1 = [0] * (N + 1) # To store 1/(k+1) mod MOD
    for i in range(1, N + 1):
        inv_k_plus_1[i] = pow(i, MOD - 2, MOD)

    for k_diff_len in range(N): # k_diff_len is j in (x_i - x_{i-j-1})^{-1}
        for i in range(N, k_diff_len, -1): # i from N down to k_diff_len + 1
            # f_coeffs[i] stores [y_{i-(k_diff_len)}, ..., y_i]
            # f_coeffs[i-1] stores [y_{i-(k_diff_len)-1}, ..., y_{i-1}]
            # Update f_coeffs[i] to [y_{i-(k_diff_len)-1}, ..., y_i]
            f_coeffs[i] = (f_coeffs[i] - f_coeffs[i-1] + MOD) % MOD
            # Denominator is x_i - x_{i-(k_diff_len+1)} = i - (i-(k_diff_len+1)) = k_diff_len+1
            f_coeffs[i] = (f_coeffs[i] * inv_k_plus_1[k_diff_len+1]) % MOD
            
    # f_coeffs now stores c_0, c_1, ..., c_N for Newton form
    # P(x) = c_0 + c_1(x-x_0) + c_2(x-x_0)(x-x_1) + ...
    # Convert to monomial basis a_0, a_1 x, ...
    # dp_coeffs[k] is coefficient of x^k
    # Start with P(x) = c_N
    # Then P(x) = P(x)*(x-x_{N-1}) + c_{N-1}
    # Then P(x) = P(x)*(x-x_{N-2}) + c_{N-2}, etc.
    
    dp_coeffs = [0] * (N + 1)
    if N >= 0:
        dp_coeffs[0] = f_coeffs[N] # Current polynomial is c_N (degree 0)
    
    current_degree = 0
    for i in range(N - 1, -1, -1): # i for x_i from x_{N-1} down to x_0
        # Current dp_coeffs represents P_partial(x)
        # New P_partial(x) = P_partial(x) * (x - x_i) + f_coeffs[i]
        # Multiply by (x - x_i):
        #   P_partial(x) * x: shift coefficients, dp_coeffs[j] moves to x^{j+1}
        #   P_partial(x) * (-x_i): multiply dp_coeffs[j] by (-x_i)
        
        # Multiply by x (update for P_partial(x) * x part):
        # dp_coeffs[j] contributes to x^{j+1}
        # Iterate downwards to use dp_coeffs[j] before it's overwritten if j+1 = j
        for j_deg in range(current_degree, -1, -1):
            term_mul_x = dp_coeffs[j_deg]
            dp_coeffs[j_deg+1] = (dp_coeffs[j_deg+1] + term_mul_x) % MOD
            
            # Multiply by -x_i (update for P_partial(x) * (-x_i) part):
            # dp_coeffs[j_deg] is multiplied by (-x_i)
            dp_coeffs[j_deg] = (dp_coeffs[j_deg] * (MOD - eval_points_x[i])) % MOD
        
        current_degree += 1
        # Add f_coeffs[i] (constant term)
        dp_coeffs[0] = (dp_coeffs[0] + f_coeffs[i]) % MOD
        
    for val in dp_coeffs:
        sys.stdout.write(str(val) + "\n")

solve()
0