結果
問題 |
No.1907 DETERMINATION
|
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
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()