結果
問題 |
No.3175 転移迷宮 (Easy)
|
ユーザー |
![]() |
提出日時 | 2025-06-13 20:06:33 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 715 ms / 3,000 ms |
コード長 | 1,501 bytes |
コンパイル時間 | 1,267 ms |
コンパイル使用メモリ | 82,112 KB |
実行使用メモリ | 78,884 KB |
最終ジャッジ日時 | 2025-06-13 20:06:58 |
合計ジャッジ時間 | 21,522 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 44 |
ソースコード
def GaussJordan_MOD(A, is_extended): H, W = len(A), len(A[0]) for i in range(H): for j in range(W): A[i][j] %= MOD rank = 0 for j in range(W-is_extended): for i in range(rank, H): if A[i][j] != 0: pivot = i break else: continue A[pivot], A[rank] = A[rank], A[pivot] inv = pow(A[rank][j], -1, MOD) for i in range(W): A[rank][i] *= inv A[rank][i] %= MOD for i in range(H): if i == rank or A[i][j] == 0: continue mul = A[i][j] for k in range(W): A[i][k] -= A[rank][k]*mul%MOD A[i][k] %= MOD rank += 1 return rank def linear_equation(A, B): H, W = len(A), len(A[0]) for i in range(H): A[i].append(B[i]) rank = GaussJordan_MOD(A, True) for i in range(rank, H): if A[i][W]: return None, None ans = [A[i][W] for i in range(rank)] C = A[:rank] for i in range(rank): C[i].pop() return C, ans MOD = 998244353 for _ in range(int(input())): N, K = map(int, input().split()) A = [[0]*N for _ in range(N)] for i in range(N): for j in range(max(i-K, 0), min(i+K+1, N)): if i == j: A[i][j] = 2*K%MOD else: A[i][j] = (-1)%MOD B = [(K*2+1)%MOD]*N C, ans = linear_equation(A, B) print(*ans)