結果
問題 |
No.1907 DETERMINATION
|
ユーザー |
![]() |
提出日時 | 2025-03-31 17:35:58 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,986 bytes |
コンパイル時間 | 213 ms |
コンパイル使用メモリ | 82,372 KB |
実行使用メモリ | 69,936 KB |
最終ジャッジ日時 | 2025-03-31 17:36:45 |
合計ジャッジ時間 | 10,417 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 3 TLE * 1 -- * 59 |
ソースコード
import sys mod = 998244353 def readints(): return list(map(int, sys.stdin.readline().split())) def main(): import sys sys.setrecursionlimit(1 << 25) N = int(sys.stdin.readline()) M0 = [] for _ in range(N): M0.append(list(map(int, sys.stdin.readline().split()))) M1 = [] for _ in range(N): M1.append(list(map(int, sys.stdin.readline().split()))) # List of evaluation points x = 0, 1, 2, ..., N xs = list(range(N+1)) ys = [] # Precompute all determinants for x in 0..N for x in xs: # Compute matrix M = M0 + x*M1 mat = [ [ (M0[i][j] + x * M1[i][j]) % mod for j in range(N)] for i in range(N)] det = 1 sign = 1 mat = [row[:] for row in mat] # make a copy for i in range(N): # Find pivot in column i 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: # Swap rows mat[i], mat[pivot] = mat[pivot], mat[i] sign *= -1 pivot_val = mat[i][i] det = (det * pivot_val) % mod inv_pivot = pow(pivot_val, mod-2, mod) for j in range(i+1, N): factor = (mat[j][i] * inv_pivot) % mod # Subtract factor * row i from row j for k in range(i, N): mat[j][k] = (mat[j][k] - factor * mat[i][k]) % mod if det == 0: final_det = 0 else: final_det = (det * sign) % mod ys.append(final_det) # Now interpolate to find coefficients of the polynomial # Using Lagrange interpolation a = [0]*(N+1) for i in range(N+1): xi = xs[i] yi = ys[i] # Compute the Lagrange basis polynomial L_i L = [0]*(N+1) L[0] = 1 denom = 1 for j in range(N+1): if j == i: continue # multiply by (x - xs[j]) / (xi - xj) # to construct the numerator and denominator denom = (denom * (xi - xs[j])) % mod # Multiply L by (x - xs[j]) # as a polynomial, shifting degrees new_L = [0]*(len(L)+1) for k in range(len(L)): new_L[k] = (new_L[k] - xs[j] * L[k]) % mod new_L[k+1] = (new_L[k+1] + L[k]) % mod L = new_L[:N+1] # truncate if necessary # Compute inv_denom = 1/denom inv_denom = pow(denom, mod-2, mod) # Multiply L by yi * inv_denom and add to a for k in range(N+1): term = (L[k] * yi) % mod term = (term * inv_denom) % mod a[k] = (a[k] + term) % mod for coeff in a: print(coeff % mod) if __name__ == "__main__": main()