// https://judge.yosupo.jp/submission/183810 #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using lint = long long; using pint = pair; using plint = pair; struct fast_ios { fast_ios(){ cin.tie(nullptr), ios::sync_with_stdio(false), cout << fixed << setprecision(20); }; } fast_ios_; #define ALL(x) (x).begin(), (x).end() #define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i=i##_begin_;i--) #define REP(i, n) FOR(i,0,n) #define IREP(i, n) IFOR(i,0,n) template bool chmax(T &m, const T q) { return m < q ? (m = q, true) : false; } template bool chmin(T &m, const T q) { return m > q ? (m = q, true) : false; } const std::vector> grid_dxs{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; int floor_lg(long long x) { return x <= 0 ? -1 : 63 - __builtin_clzll(x); } template T1 floor_div(T1 num, T2 den) { return (num > 0 ? num / den : -((-num + den - 1) / den)); } template std::pair operator+(const std::pair &l, const std::pair &r) { return std::make_pair(l.first + r.first, l.second + r.second); } template std::pair operator-(const std::pair &l, const std::pair &r) { return std::make_pair(l.first - r.first, l.second - r.second); } template std::vector sort_unique(std::vector vec) { sort(vec.begin(), vec.end()), vec.erase(unique(vec.begin(), vec.end()), vec.end()); return vec; } template int arglb(const std::vector &v, const T &x) { return std::distance(v.begin(), std::lower_bound(v.begin(), v.end(), x)); } template int argub(const std::vector &v, const T &x) { return std::distance(v.begin(), std::upper_bound(v.begin(), v.end(), x)); } template IStream &operator>>(IStream &is, std::vector &vec) { for (auto &v : vec) is >> v; return is; } template OStream &operator<<(OStream &os, const std::vector &vec); template OStream &operator<<(OStream &os, const std::array &arr); template OStream &operator<<(OStream &os, const std::unordered_set &vec); template OStream &operator<<(OStream &os, const pair &pa); template OStream &operator<<(OStream &os, const std::deque &vec); template OStream &operator<<(OStream &os, const std::set &vec); template OStream &operator<<(OStream &os, const std::multiset &vec); template OStream &operator<<(OStream &os, const std::unordered_multiset &vec); template OStream &operator<<(OStream &os, const std::pair &pa); template OStream &operator<<(OStream &os, const std::map &mp); template OStream &operator<<(OStream &os, const std::unordered_map &mp); template OStream &operator<<(OStream &os, const std::tuple &tpl); template OStream &operator<<(OStream &os, const std::vector &vec) { os << '['; for (auto v : vec) os << v << ','; os << ']'; return os; } template OStream &operator<<(OStream &os, const std::array &arr) { os << '['; for (auto v : arr) os << v << ','; os << ']'; return os; } template std::istream &operator>>(std::istream &is, std::tuple &tpl) { std::apply([&is](auto &&... args) { ((is >> args), ...);}, tpl); return is; } template OStream &operator<<(OStream &os, const std::tuple &tpl) { os << '('; std::apply([&os](auto &&... args) { ((os << args << ','), ...);}, tpl); return os << ')'; } template OStream &operator<<(OStream &os, const std::unordered_set &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; } template OStream &operator<<(OStream &os, const std::deque &vec) { os << "deq["; for (auto v : vec) os << v << ','; os << ']'; return os; } template OStream &operator<<(OStream &os, const std::set &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; } template OStream &operator<<(OStream &os, const std::multiset &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; } template OStream &operator<<(OStream &os, const std::unordered_multiset &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; } template OStream &operator<<(OStream &os, const std::pair &pa) { return os << '(' << pa.first << ',' << pa.second << ')'; } template OStream &operator<<(OStream &os, const std::map &mp) { os << '{'; for (auto v : mp) os << v.first << "=>" << v.second << ','; os << '}'; return os; } template OStream &operator<<(OStream &os, const std::unordered_map &mp) { os << '{'; for (auto v : mp) os << v.first << "=>" << v.second << ','; os << '}'; return os; } #ifdef HITONANODE_LOCAL const string COLOR_RESET = "\033[0m", BRIGHT_GREEN = "\033[1;32m", BRIGHT_RED = "\033[1;31m", BRIGHT_CYAN = "\033[1;36m", NORMAL_CROSSED = "\033[0;9;37m", RED_BACKGROUND = "\033[1;41m", NORMAL_FAINT = "\033[0;2m"; #define dbg(x) std::cerr << BRIGHT_CYAN << #x << COLOR_RESET << " = " << (x) << NORMAL_FAINT << " (L" << __LINE__ << ") " << __FILE__ << COLOR_RESET << std::endl #define dbgif(cond, x) ((cond) ? std::cerr << BRIGHT_CYAN << #x << COLOR_RESET << " = " << (x) << NORMAL_FAINT << " (L" << __LINE__ << ") " << __FILE__ << COLOR_RESET << std::endl : std::cerr) #else #define dbg(x) ((void)0) #define dbgif(cond, x) ((void)0) #endif // #include using u32 = unsigned int; using u64 = unsigned long long; constexpr unsigned int P = 1000000007, P2 = P * 2; struct Fp { u32 v; Fp() : v() {} Fp(u32 v) : v(v) {} Fp operator+(const Fp& rhs) const { u32 a = v + rhs.v; if (a >= P) a -= P; return a; } Fp& operator+=(const Fp& rhs) { if ((v += rhs.v) >= P) v -= P; return *this; } Fp operator-() const { return v ? P - v : v; } Fp operator-(const Fp& rhs) const { u32 a = v - rhs.v; if (int(a) < 0) a += P; return a; } Fp& operator-=(const Fp& rhs) { if (int(v -= rhs.v) < 0) v += P; return *this; } Fp operator*(const Fp& rhs) const { return u32(u64(v) * rhs.v % P); } Fp& operator*=(const Fp& rhs) { v = u64(v) * rhs.v % P; return *this; } Fp inv() const; Fp operator/(const Fp& rhs) const { return *this * rhs.inv(); } Fp& operator/=(const Fp& rhs) { return *this *= rhs.inv(); } operator u32() const { return v; } Fp quo2() const { return (v & 1) ? ((v + P) >> 1) : (v >> 1); } }; Fp mpow(const Fp& a, unsigned k) { if (k == 0) return 1u; Fp ret = mpow(a * a, k >> 1); if (k & 1) ret *= a; return ret; } Fp Fp::inv() const { return mpow(*this, P - 2); } std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count()); std::uniform_int_distribution uid(0, P - 1); using Poly = std::vector; using Vec = std::vector; using Matrix = std::vector; const int _ = 505; int N; Matrix transpose(const Matrix& mat) { Matrix ret(N, Vec(N)); for (int i = 0; i != N; ++i) for (int j = 0; j != N; ++j) ret[i][j] = mat[j][i]; return ret; } Matrix operator*(const Matrix& lhs, Matrix rhs) { for (int i = 0; i != N; ++i) for (int j = 0; j != i; ++j) std::swap(rhs[i][j], rhs[j][i]); Matrix ret(N, Vec(N)); for (int i = 0; i != N; ++i) for (int j = 0; j != N; ++j) for (int k = 0; k != N; ++k) ret[i][j] += lhs[i][k] * rhs[j][k]; return ret; } Vec operator+(const Vec& lhs, const Vec& rhs) { Vec ret(N); for (int i = 0; i != N; ++i) ret[i] = lhs[i] + rhs[i]; return ret; } Vec operator-(const Vec& lhs, const Vec& rhs) { Vec ret(N); for (int i = 0; i != N; ++i) ret[i] = lhs[i] - rhs[i]; return ret; } Vec operator*(const Vec& lhs, const Fp& rhs) { Vec ret(N); for (int i = 0; i != N; ++i) ret[i] = lhs[i] * rhs; return ret; } struct Basis { std::vector vectors; Matrix reduced, coefficients; Basis() : reduced(N), coefficients(N) {} Basis(const Basis& basis) : vectors(basis.vectors), reduced(basis.reduced), coefficients(basis.coefficients) {} Poly insert(Vec vec) { int id = vectors.size(); Vec coefficient(N); vectors.push_back(vec); for (int i = 0; i != N; ++i) { if (vec[i] == 0) continue; if (!reduced[i].empty()) { Fp c = vec[i]; vec = vec - reduced[i] * c; coefficient = coefficient - coefficients[i] * c; } else { Fp nv = vec[i].inv(); coefficient[id] = 1; reduced[i] = vec * nv; coefficients[i] = coefficient * nv; return Poly(); } } coefficient.resize(id + 1); coefficient[id] = 1; return coefficient; } Matrix inv() { for (int i = N - 1; i; --i) for (int j = 0; j != i; ++j) { Fp c = reduced[j][i]; reduced[j] = reduced[j] - reduced[i] * c; coefficients[j] = coefficients[j] - coefficients[i] * c; } return coefficients; } }; Vec operator*(const Matrix& mat, const Vec& vec) { Vec ret(N); for (int i = 0; i != N; ++i) for (int j = 0; j != N; ++j) ret[i] += mat[i][j] * vec[j]; return ret; } Poly div(Poly a, Poly b) { int n = a.size() - 1, m = b.size() - 1; Poly ret(n - m + 1); for (int i = n; i >= m; --i) { ret[i - m] = a[i]; Fp c = -a[i]; for (int j = 0; j <= m; ++j) { a[i - m + j] += c * b[j]; } } for (int i = 0; i != m; ++i) assert(a[i] == 0); return ret; } Poly mod(Poly a, Poly b) { int n = b.size() - 1; if (a.size() < n) a.resize(n); int m = a.size() - 1; for (int i = m; i >= n; --i) for (int j = 1; j <= n; ++j) a[i - j] -= a[i] * b[n - j]; a.resize(n); return a; } Poly powmod(Poly modulo, u64 K) { int n = modulo.size() - 1; if (K == 0) { Poly ret(n); ret[0] = 1; return ret; } Poly half = powmod(modulo, K >> 1); Poly ret(n * 2 - 1); for (int i = 0; i != n; ++i) for (int j = 0; j != n; ++j) ret[i + j] += half[i] * half[j]; if (K & 1) ret.insert(ret.begin(), 0); return mod(ret, modulo); } Matrix Calc(Matrix a, int N, u64 K) { std::vector elementaryDivisors; Basis basis = Basis(); while (basis.vectors.size() < N) { // std::cerr << basis.vectors.size() << '\n'; Vec initVector(N); for (int i = 0; i != N; ++i) initVector[i].v = uid(rng); Vec iterVector = initVector; Basis test = basis; Poly coefficient; while (true) { coefficient = test.insert(iterVector); if (!coefficient.empty()) break; iterVector = a * iterVector; } Poly minimalPolynomial(coefficient.begin() + basis.vectors.size(), coefficient.end()); int minPolyDegree = minimalPolynomial.size() - 1; int pre = 0; for (int i = 0; i != elementaryDivisors.size(); ++i) { int degree = elementaryDivisors[i].size() - 1; if (degree <= minPolyDegree) { pre += degree; continue; } // std::cerr << degree << ' ' << minPolyDegree << '\n'; // std::cerr << "COEFF "; // for (int j = 0; j != degree; ++j) // std::cerr << coefficient[pre + j].v << ' '; Poly res = div(Poly(coefficient.begin() + pre, coefficient.begin() + pre + degree), minimalPolynomial); // std::cerr << "SIZ " << res.size() << '\n'; // std::cerr << "RES: " << res[0] << '\n'; for (int j = 0; j != degree - minPolyDegree; ++j) initVector = initVector + basis.vectors[pre + j] * res[j]; pre += degree; } elementaryDivisors.push_back(minimalPolynomial); for (int rep = 0; rep != minPolyDegree; ++rep) { basis.insert(initVector); initVector = a * initVector; } } Matrix b = transpose(basis.vectors); Matrix inv = transpose(basis.inv()); Matrix canonicalFormPower(N, Vec(N)); int pre = 0; for (Poly poly : elementaryDivisors) { int degree = poly.size() - 1; Poly res = powmod(poly, K); for (int i = 0; i != degree; ++i) { for (int j = 0; j != degree; ++j) canonicalFormPower[pre + j][pre + i] = res[j]; res.insert(res.begin(), 0); res = mod(res, poly); } pre += degree; } return canonicalFormPower; } int main() { N = 2; std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); Matrix A(2, Vec(2)); Matrix B(2, Vec(2)); REP(i, 2) REP(j, 2) { cin >> A[i][j].v; } REP(i, 2) REP(j, 2) { cin >> B[i][j].v; } dbg(A); dbg(B); auto ca = Calc(A, 2, 1); dbg(ca); auto cb = Calc(B, 2, 1); dbg(cb); if (ca == cb) { puts("Yes"); } else { puts("No"); } // std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); // u64 K; // std::cin >> N >> K; // Matrix a(N, Vec(N)); // for (int i = 0; i != N; ++i) // for (int j = 0; j != N; ++j) // std::cin >> a[i][j].v; // Matrix power = b * canonicalFormPower * inv; // for (int i = 0; i != N; ++i) { // for (int j = 0; j != N; ++j) // std::cout << power[i][j].v << " \n"[j == N - 1]; // } // return 0; }