#line 1 "main.cpp" // 提出時にassertはオフ #ifndef DEBUG #ifndef NDEBUG #define NDEBUG #endif #endif #include #line 2 "/home/cocojapanpan/Procon_CPP/proconLibrary/lib/string/rollinghash.hpp" #line 4 "/home/cocojapanpan/Procon_CPP/proconLibrary/lib/string/rollinghash.hpp" struct rolhash_mod { using u128 = __uint128_t; using u64 = uint64_t; public: constexpr rolhash_mod(u64 x = 0) noexcept : value(calcMod(x)) {} constexpr u64 val() const noexcept { return value; } constexpr rolhash_mod &operator+=(const rolhash_mod &a) noexcept { if ((value += a.value) >= MOD) value -= MOD; return *this; } constexpr rolhash_mod &operator-=(const rolhash_mod &a) noexcept { *this += (MOD - a.value); return *this; } constexpr rolhash_mod &operator*=(const rolhash_mod &a) noexcept { u128 product = (u128)value * a.value; product = (product >> 61) + (product & MOD); if (product >= MOD) product -= MOD; value = product; return *this; } constexpr rolhash_mod operator+(const rolhash_mod &a) const noexcept { rolhash_mod cpy(*this); return cpy += a; } constexpr rolhash_mod operator-(const rolhash_mod &a) const noexcept { rolhash_mod cpy(*this); return cpy -= a; } constexpr rolhash_mod operator*(const rolhash_mod &a) const noexcept { rolhash_mod cpy(*this); return cpy *= a; } constexpr bool operator==(const rolhash_mod &a) const noexcept { return value == a.value; } constexpr bool operator!=(const rolhash_mod &a) const noexcept { return value != a.value; } // べき乗のmod(tableを用意せずその場でやってるのでlog(beki)かかる) constexpr static u64 power(u64 base, u64 beki) noexcept { rolhash_mod curbekiMod(base); rolhash_mod ret(1); while (beki > 0) { if (beki & 1) ret *= curbekiMod; curbekiMod *= curbekiMod; beki >>= 1; } return ret.val(); } private: u64 value; // 中で保持しておくmod constexpr static u64 MOD = (1ULL << 61) - 1; constexpr static u64 calcMod(const u64 &x) noexcept { u64 cur = x >> 61; if ((cur += (x & MOD)) >= MOD) cur -= MOD; return cur; } }; // 部分文字列[l,r)のhash値を返すqueryを定数時間で struct rolhash { using u64 = uint64_t; public: template explicit rolhash(const std::vector &input) : base(genBase()), N(input.size()) { basebeki_table.resize(N + 1); basebeki_table[0] = 1; for (int i = 1; i <= N; i++) { basebeki_table[i] = basebeki_table[i - 1] * base; } front_table.resize(N + 1); for (int i = 1; i <= N; i++) { front_table[i] = front_table[i - 1] * base + input[i - 1]; } } explicit rolhash(const std::string &input_string) : rolhash(std::vector(input_string.begin(), input_string.end())) { } // 部分列[l,r)のhash値を返す l==rのときは0を返す rolhash_mod query(int l, int r) const { assert(l <= r); if (l == r) return rolhash_mod(0); return (front_table[r] - front_table[l] * basebeki_table[r - l]); } // baseのbeki乗を返す rolhash_mod get_basebeki(int beki) const { return basebeki_table[beki]; } // queryで足りないとき用 // 部分列[0,i)のhash値を返す rolhash_mod get_front(int i) const { return front_table[i]; } // queryで足りないとき用 // [2, MOD - 2]のbaseを乱数として生成 static u64 genBase() { auto rand_time = std::chrono::duration_cast( std::chrono::high_resolution_clock::now().time_since_epoch()) .count(); // 非決定的な乱数 std::mt19937_64 mt(rand_time); // メルセンヌ・ツイスタ 64bit std::uniform_int_distribution randbase(2ULL, MOD - 2); return randbase(mt); } private: constexpr static u64 MOD = (1ULL << 61) - 1; const u64 base; const int N; // baseの0乗からN乗を記録 std::vector basebeki_table; // [0,i)の部分列のhash値を記録 std::vector front_table; }; #line 10 "main.cpp" using namespace std; using ll = long long; #define ALL(x) (x).begin(), (x).end() template using vec = vector; int N, k; // 多重集合一致判定 bool isSameSet(const vec &A_, const vec &B_) { vec A = A_, B = B_; if(A.size() != B.size()) { return false; } sort(ALL(A)); sort(ALL(B)); for(int i = 0; i < (int)A.size(); i++) { if(A[i] != B[i]) return false; } return true; } bool isTotallySame(const vec &A, const vec &B) { if(A.size() != B.size()) return false; for(int i = 0; i < (int)A.size(); i++) { if(A[i] != B[i]) return false; } return true; } bool solve(const vec &A, const vec &B) { if(!isSameSet(A, B)) return false; int size = A.size(); if(k > N) { return isTotallySame(A, B); } if(k == N) { vec rev_A = A; reverse(ALL(rev_A)); return (isTotallySame(A, B) || isTotallySame(rev_A, B)); } if(k == N - 1) { rolhash_mod base = rolhash::genBase(); vec bekiTable(size + 1, 1); for(int i = 1; i <= size; i++) { bekiTable[i] = bekiTable[i - 1] * base; } rolhash_mod A_hash, B_hash; for(int i = 0; i < size; i++) { A_hash += bekiTable[i] * A[i]; B_hash += bekiTable[i] * B[i]; } if(A_hash == B_hash) return true; for(int i = 1; i < size; i++) { A_hash = A_hash * base - (bekiTable[size] - 1) * A[size - i]; if(A_hash == B_hash) return true; } rolhash_mod rev_A_hash; for(int i = 0; i < size; i++) { rev_A_hash += bekiTable[i] * A[size - 1 - i]; } if(rev_A_hash == B_hash) return true; for(int i = 1; i < size; i++){ rev_A_hash = rev_A_hash * base - (bekiTable[size] - 1) * A[i - 1]; if(rev_A_hash == B_hash) return true; } return false; } // k <= N - 2 return true; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> N >> k; vec A(N), B(N); for(int &a : A) cin >> a; for(int &b : B) cin >> b; cout << (solve(A, B) ? "Yes" : "No") << "\n"; }