結果
問題 | No.2405 Minimal Matrix Decomposition |
ユーザー |
|
提出日時 | 2023-08-04 22:26:37 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 462 ms / 2,000 ms |
コード長 | 1,404 bytes |
コンパイル時間 | 238 ms |
コンパイル使用メモリ | 82,244 KB |
実行使用メモリ | 81,792 KB |
最終ジャッジ日時 | 2024-10-14 20:26:01 |
合計ジャッジ時間 | 8,924 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 46 |
ソースコード
import sysinput = lambda :sys.stdin.readline().rstrip()mod = int(input())N,M = map(int,input().split())A = [list(map(int,input().split())) for i in range(N)]original = [[A[i][j] for j in range(M)] for i in range(N)]rank = 0B = [[] for i in range(N)]C = []for j in range(M):pivot = -1for i in range(j,N):if A[i][j]!=0:pivot = ibreakif pivot == -1:continuerank += 1C.append([A[pivot][j] for j in range(M)])inv = pow(A[pivot][j],mod-2,mod)for i in range(N):if i == pivot:continuet = A[i][j] * inv % modB[i].append(t)for k in range(j,M):A[i][k] -= A[pivot][k] * t % modA[i][k] %= mod#print(A[i])B[pivot].append(1)for j in range(M):A[pivot][j] = 0#print()if rank == 0:if N*M >= N+M:print(2)print(N,1)for i in range(N):print(0)print(1,M)print(*[0]*M)exit()else:print(1)print(N,M)for i in range(N):print(*[0]*M)exit()if N*M <= rank * (N+M):print(1)print(N,M)for i in range(N):print(*original[i])else:print(2)print(N,rank)for i in range(N):print(*B[i])print(rank,M)for i in range(rank):print(*C[i])