結果
問題 |
No.3225 2×2行列相似判定 〜easy〜
|
ユーザー |
|
提出日時 | 2025-08-12 00:58:29 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,565 bytes |
コンパイル時間 | 2,069 ms |
コンパイル使用メモリ | 200,820 KB |
実行使用メモリ | 7,720 KB |
最終ジャッジ日時 | 2025-08-12 00:58:32 |
合計ジャッジ時間 | 3,429 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | WA * 3 |
other | WA * 33 |
ソースコード
#include <bits/stdc++.h> using namespace std; using vc = std::vector<int> ; using mat = vector<vc>; const int p = 67; mat prod(const mat& A, const mat& B) { mat ret(A.size(), vc(B[0].size())); for (int i = 0; i < A.size(); i ++) { for (int j = 0; j < B[0].size(); j ++) { ret[i][j] = 0; for (int k = 0; k < A[0].size(); k ++) { ret[i][j] += A[i][k] * B[k][j]; } } } return ret; } int main () { mat A(2, vc(2)), B(2, vc(2)); for (auto& a : A) { for (auto& b : a) { cin >> b; } } for (auto& a : B) { for (auto& b : a) { cin >> b; } } mat X(4, vc(4, 0)); for (int i = 0; i < 2; i ++) { for (int j = 0; j < 2; j ++) { for (int k = 0; k < 2; k ++) { int p = i * 2 + j; int q = i * 2 + k; int r = k * 2 + j; X[p][q] += A[k][j]; X[p][r] -= B[i][k]; } } } for (auto& a : X) { for (auto& b : a) { b += p * p; b %= p; } } vc iv(p, 0); for (int i = 1; i < p; i ++) { for (int j = 1; j < p; j ++) { if ((i * j) % p == 1) { iv[i] = j; iv[j] = i; } } } return 0; for (int i = 0; i < 4; i ++) { int r = i; while (r < 4 && (A[r][i] == 0)) r ++; if (r == 4) { puts("No"); return 0; } int b = A[r][i]; for (int j = 3; j >= i; j --) { swap(A[i][j], A[r][j]); A[i][j] = (A[i][j] * iv[b]) % p; } for (int x = 0; x < 4; x ++) { if (x == i) continue; for (int j = 3; j >= i; j --) { A[x][j] -= A[x][i] * A[i][j]; if (A[x][j] < 0) { A[x][j] = (-A[x][j]) % p; A[x][j] = p - A[x][j]; } A[x][j] %= p; } } } puts("Yes"); }