結果

問題 No.3225 2×2行列相似判定 〜easy〜
コンテスト
ユーザー wasd314
提出日時 2025-08-08 21:49:13
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 199 ms / 2,000 ms
コード長 1,921 bytes
コンパイル時間 3,256 ms
コンパイル使用メモリ 177,580 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-08-08 21:49:34
合計ジャッジ時間 7,619 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <algorithm>
#include <array>
#include <iostream>
#include <vector>

#include <atcoder/all>
// using namespace std;
// using namespace atcoder;
// using mint = modint998244353;


template <typename Mint>
struct Binomial {
    std::vector<Mint> fact, invfact;
    Binomial(int nn) : fact(nn, 1), invfact(nn, 1)
    {
        for (int i = 0; i < nn - 1; i++) fact[i + 1] = fact[i] * (i + 1);
        invfact[nn - 1] = fact[nn - 1].inv();
        for (int i = nn - 2; i >= 0; i--) invfact[i] = invfact[i + 1] * (i + 1);
    }
    Mint operator()(int x, int y) const
    {
        if (x < 0 || y < 0 || x - y < 0) return 0;
        return fact[x] * invfact[y] * invfact[x - y];
    }
};

int main()
{
    using namespace std;
    const int mod = 67;
    using mint = atcoder::static_modint<mod>;
    using mat_t = array<mint, 4>;
    auto get_mat = [&] {
        mat_t m;
        for (auto& e : m) {
            int x;
            cin >> x;
            e = x;
        }
        return m;
    };
    auto a = get_mat();
    auto b = get_mat();
    auto mat_mul = [](mat_t m1, mat_t m2) {
        return mat_t{
            m1[0] * m2[0] + m1[1] * m2[2],
            m1[0] * m2[1] + m1[1] * m2[3],
            m1[2] * m2[0] + m1[3] * m2[2],
            m1[2] * m2[1] + m1[3] * m2[3],
        };
    };
    auto cond = [&] {
        for (int p0 = 0; p0 < mod; ++p0) {
            for (int p1 = 0; p1 < mod; ++p1) {
                for (int p2 = 0; p2 < mod; ++p2) {
                    for (int p3 = 0; p3 < mod; ++p3) {
                        if (p0 * p3 - p1 * p2 == 0) continue;
                        mat_t p{p0, p1, p2, p3};
                        auto pa = mat_mul(p, a);
                        auto bp = mat_mul(b, p);
                        if (pa == bp) return true;
                    }
                }
            }
        }
        return false;
    }();
    cout << (cond ? "Yes" : "No") << endl;
}
0