import static java.lang.System.err; import java.util.Arrays; import java.util.Random; import java.util.function.LongBinaryOperator; import java.util.function.LongUnaryOperator; import java.util.stream.IntStream; public class Main { public static void main(String[] args) { java.io.PrintWriter out = new java.io.PrintWriter(System.out); new Main(out); out.flush(); err.flush(); } /* * 1. k=Nのとき: 2択 * 2. k> 1; ++i) { A[i] ^= A[N - i - 1]; A[N - i - 1] ^= A[i]; A[i] ^= A[N - i - 1]; } yes |= Arrays.equals(A, B); out.println(yes ? "Yes" : "No"); } else if (N == k + 1) { int[] A2 = Arrays.copyOf(A, A.length * 2); System.arraycopy(A, 0, A2, A.length, A.length); RollingHash BHash = RollingHash.create(B); long base = BHash.base(); RollingHash A2Hash = RollingHash.create(A2, base); for (int i = 0; i < A.length; ++i) { if (A2Hash.subList(i, i + A.length).equals(BHash)) { out.println("Yes"); return; } } for (int i = 0; i < N >> 1; ++i) { A[i] ^= A[N - i - 1]; A[N - i - 1] ^= A[i]; A[i] ^= A[N - i - 1]; } A2 = Arrays.copyOf(A, A.length * 2); System.arraycopy(A, 0, A2, A.length, A.length); A2Hash = RollingHash.create(A2, base); for (int i = 0; i < A.length; ++i) { if (A2Hash.subList(i, i + A.length).equals(BHash)) { out.println("Yes"); return; } } out.println("No"); } else { Arrays.sort(A); Arrays.sort(B); out.println(Arrays.equals(A, B) ? "Yes" : "No"); } } } } /** * 数列に対するローリングハッシュを求めます。 *

* ローリングハッシュとは、基数{@code base}と法{@code mod}が与えられたとき、数列{@code S}に対して以下のように定義される値です。 *

hash = sum[i=1, |S|]S_i * base^(i-1) (modulo mod)
* これは、数列{@code S}を{@code base}進数で表して{@code mod}で余りを取ったものと考えることができます。 *

* @author 31536000 * */ interface RollingHash extends Comparable { /** * このローリングハッシュで用いられている基数を返します。 * @return 基数 */ long base(); /** * このローリングハッシュで用いられている法を返します。 * @return 法 */ long mod(); /** * この数列全体のハッシュを返します。 * @return 数列のハッシュ値 */ long hash(); /** * この数列の先頭からindex番目までのハッシュ値を返します。 * @param index ハッシュ値を求めたい区間 * @return 数列の先頭からn番目までのハッシュ値 * @exception IllegalArgumentException {@code 0 > index || index > size()} */ default long hash(int index) { return hash(0, index); } /** * この数列のfromIndex番目からtoIndex番目までのハッシュ値を返します。 * @param fromIndex ハッシュ値を求める区間の左端(これを含む) * @param toIndex ハッシュ値を求める区間の右端(これを含まない) * @return 数列のfromIndex番目からtoIndex番目までのハッシュ値 * @exception IllegalArgumentException {@code 0 > fromIndex || fromIndex > toIndex || toIndex > size()} */ default long hash(int fromIndex, int toIndex) { if (0 > fromIndex || fromIndex > toIndex || toIndex > size()) throw new IllegalArgumentException("[" + fromIndex + ", " + toIndex + ") is illegal range"); return subList(fromIndex, toIndex).hash(); } /** * この数列の先頭からindex番目までのハッシュ値を返します。 * @param index ハッシュ値を求めたい区間 * @return 数列の先頭からn番目までのハッシュ値 * @exception IllegalArgumentException {@code 0 > index || index > size()} */ default RollingHash subList(int index) { return subList(0, index); } /** * この数列のfromIndex番目からtoIndex番目までのハッシュ値を返します。 * @param fromIndex ハッシュ値を求める区間の左端(これを含む) * @param toIndex ハッシュ値を求める区間の右端(これを含まない) * @return 数列のfromIndex番目からtoIndex番目までのハッシュ値 * @exception IllegalArgumentException {@code 0 > fromIndex || fromIndex > toIndex || toIndex > size()} */ RollingHash subList(int fromIndex, int toIndex); /** * 二つの数列をこの順に結合したときのハッシュ値を返します。 * @param l 左側の数列 * @param r 右側の数列 * @return 数列{@code l}, {@code r}をこの順に結合したときのハッシュ値 * @exception IllegalArgumentException {@code l.base() != r.base() || l.mod() != r.mod()} * @exception NullPointerException {@code l == null || r == null} */ RollingHash merge(RollingHash l, RollingHash r); /** * この数列の長さを返します。 * @return 数列長 */ int size(); /** * 二つの数列の最長共通接頭辞の長さを求めます。 * @param l 数列 * @param r 数列 * @return {@code l}と{@code r}の最長共通接頭辞 * @exception IllegalArgumentException {@code l.base() != r.base() || l.mod() != r.mod()} * @exception NullPointerException {@code l == null || r == null} */ static int lcp(RollingHash l, RollingHash r) { if (l == null || r == null) throw new NullPointerException(); if (l.base() != r.base() || l.mod() != r.mod()) throw new IllegalArgumentException(); int min = 0, max = Math.min(l.size(), r.size()) + 1; while (max - min > 1) { int mid = min + (max - min >> 1); if (l.hash(mid) == r.hash(mid)) min = mid; else max = mid; } return min; } /** * 二つの数列の最長共通接頭辞の長さを求めます。 * @param S 数列 * @return 自身と{@code S}の最長共通接頭辞 * @exception IllegalArgumentException {@code base() != S.base() || mod() != S.mod()} * @exception NullPointerException {@code S == null} */ default int lcp(RollingHash S) { return lcp(this, S); } @Override default int compareTo(RollingHash o) { int lcp = lcp(this, o); if (size() == lcp) { return o.size() == lcp ? 0 : -1; } if (o.size() == lcp) return 1; return Long.compare(hash(lcp, lcp + 1), o.hash(lcp, lcp + 1)); } /** * この数列の中に{@code s}を連続部分列として含む場合、その先頭のインデックスを返します。そのようなものが無い場合、{@code -1}を返します。 * @param s 調べる数列 * @return {@code s}を連続部分列として含む場合はその先頭のインデックス、無ければ{@code -1} * @exception IllegalArgumentException {@code base() != s.base() || mod() != s.mod()} * @exception NullPointerException {@code s == null} */ default int find(RollingHash s) { if (s == null) throw new NullPointerException(); if (base() != s.base() || mod() != s.mod()) throw new IllegalArgumentException(); int size = s.size(); long hash = s.hash(); for (int i = 0, l = size() - size; i <= l; ++i) { if (hash(i, i + size) == hash) return i; } return -1; } /** * 数列{@code S}に対して2^{61}-1を法とするローリングハッシュを計算します。 * @param S 各要素が0以上2^{61}-1未満の数列 * @return {@code S}のローリングハッシュ */ static RollingHash create(long[] S) { Random rnd = new Random(); long MOD = (1L << 61) - 1; long MASK0 = (1L << 30) - 1; long MASK1 = (1L << 31) - 1; LongUnaryOperator mod = x -> { final long xu = x >>> 61; final long xd = x & MOD; long res = xu + xd; if (res >= MOD) res -= MOD; return res; }; LongBinaryOperator mul = (a, b) -> { final long au = a >>> 31; final long ad = a & MASK1; final long bu = b >>> 31; final long bd = b & MASK1; final long mid = ad * bu + au * bd; final long midu = mid >>> 30; final long midd = mid & MASK0; return mod.applyAsLong((au * bu << 1) + midu + (midd << 31) + ad * bd); }; LongBinaryOperator gcd = (a, b) -> { while (a != 0) if ((b %= a) != 0) a %= b; else return a; return b; }; while (true) { long e = mod.applyAsLong(rnd.nextLong()); if (gcd.applyAsLong(e, MOD - 1) == 1) { long base = 1; for (long x = 37; e > 0; e >>= 1, x = mul.applyAsLong(x, x)) if ((e & 1) != 0) base = mul.applyAsLong(base, x); return create(S, base); } } } /** * 数列{@code S}に対して2^{61}-1を法とするローリングハッシュを計算します。 * @param S 数列 * @return {@code S}のローリングハッシュ */ static RollingHash create(int[] S) { return create(Arrays.stream(S).mapToLong(i -> i).toArray()); } /** * 文字列{@code S}に対して2^{61}-1を法とするローリングハッシュを計算します。 * @param S 文字列 * @return {@code S}のローリングハッシュ */ static RollingHash create(char[] S) { return create(IntStream.range(0, S.length).mapToLong(i -> S[i]).toArray()); } /** * 文字列{@code S}に対して2^{61}-1を法とするローリングハッシュを計算します。 * @param S 文字列 * @return {@code S}のローリングハッシュ */ static RollingHash create(String S) { return create(IntStream.range(0, S.length()).mapToLong(S::charAt).toArray()); } /** * 数列{@code S}に対して2^{61}-1を法とするローリングハッシュを計算します。 * @param S 各要素が0以上2^{61}-1未満の数列 * @param base 基数 * @return {@code S}のローリングハッシュ */ static RollingHash create(long[] S, long base) { long MOD = (1L << 61) - 1; class DefaultRollingHash implements RollingHash { final long[] hash; final long[] pow; static final long MASK0 = (1L << 30) - 1; static final long MASK1 = (1L << 31) - 1; final int len = S.length; long mod(final long x) { final long xu = x >>> 61; final long xd = x & MOD; long res = xu + xd; if (res >= MOD) res -= MOD; return res; } long mul(final long a, final long b) { final long au = a >>> 31; final long ad = a & MASK1; final long bu = b >>> 31; final long bd = b & MASK1; final long mid = ad * bu + au * bd; final long midu = mid >>> 30; final long midd = mid & MASK0; return mod((au * bu << 1) + midu + (midd << 31) + ad * bd); } DefaultRollingHash() { hash = new long[S.length + 1]; pow = new long[S.length + 1]; pow[0] = 1; for (int i = 0; i < S.length; ++i) { hash[i + 1] = mod(mul(hash[i], base) + S[i]); pow[i + 1] = mul(pow[i], base); } } @Override public long base() { return base; } @Override public long mod() { return MOD; } @Override public long hash() { return hash[hash.length - 1]; } @Override public long hash(int fromIndex, int toIndex) { return mod(hash[toIndex] - mul(hash[fromIndex], pow[toIndex - fromIndex]) + MOD); } @Override public RollingHash subList(int fromIndex, int toIndex) { class SubRollingHash implements RollingHash { final int l, r; final long hash; SubRollingHash(int l, int r) { this.l = l; this.r = r; hash = DefaultRollingHash.this.hash(l, r); } private void check(int from, int to) { if (0 > from || from > to || to > r - l) throw new IllegalArgumentException( "[" + from + ", " + to + ") is out of range: [0, " + (r - l) + ")"); } @Override public long base() { return base; } @Override public long mod() { return MOD; } @Override public long hash() { return hash; } @Override public long hash(int fromIndex, int toIndex) { check(fromIndex, toIndex); return DefaultRollingHash.this.hash(l + fromIndex, l + toIndex); } @Override public RollingHash subList(int fromIndex, int toIndex) { check(fromIndex, toIndex); return new SubRollingHash(l + fromIndex, l + toIndex); } @Override public RollingHash merge(RollingHash l, RollingHash r) { return merge(l, r); } @Override public int size() { return r - l; } @Override public int hashCode() { return Long.hashCode(hash()); } @Override public boolean equals(Object o) { if (o instanceof RollingHash) { RollingHash hash = (RollingHash) o; return hash() == hash.hash(); } return false; } } return new SubRollingHash(fromIndex, toIndex); } @Override public RollingHash merge(RollingHash l, RollingHash r) { class MergeRollingHash implements RollingHash { final RollingHash l, r; final long hash; final int size; MergeRollingHash(RollingHash l, RollingHash r) { this.l = l; this.r = r; hash = DefaultRollingHash.this.mod(mul(l.hash(), pow[r.size()]) + r.hash()); size = l.size() + r.size(); } @Override public long base() { return base; } @Override public long mod() { return MOD; } @Override public long hash() { return hash; } @Override public RollingHash subList(int fromIndex, int toIndex) { if (0 > fromIndex || fromIndex > toIndex || toIndex > size()) throw new IllegalArgumentException( "[" + fromIndex + ", " + toIndex + ") is out of range: [0, " + size() + ")"); if (toIndex <= l.size()) return l.subList(fromIndex, toIndex); if (fromIndex >= l.size()) return r.subList(fromIndex - l.size(), toIndex - l.size()); return merge(l.subList(fromIndex, l.size()), r.subList(0, toIndex - l.size())); } @Override public RollingHash merge(RollingHash l, RollingHash r) { return new MergeRollingHash(l, r); } @Override public int size() { return size; } @Override public int hashCode() { return Long.hashCode(hash()); } @Override public boolean equals(Object o) { if (o instanceof RollingHash) { RollingHash hash = (RollingHash) o; return hash() == hash.hash(); } return false; } } return new MergeRollingHash(l, r); } @Override public int size() { return len; } @Override public int hashCode() { return Long.hashCode(hash()); } @Override public boolean equals(Object o) { if (o instanceof RollingHash) { RollingHash hash = (RollingHash) o; return hash() == hash.hash(); } return false; } } return new DefaultRollingHash(); } /** * 数列{@code S}に対して2^{61}-1を法とするローリングハッシュを計算します。 * @param S 数列 * @param base 基数 * @return {@code S}のローリングハッシュ */ static RollingHash create(int[] S, long base) { return create(Arrays.stream(S).mapToLong(i -> i).toArray(), base); } /** * 文字列{@code S}に対して2^{61}-1を法とするローリングハッシュを計算します。 * @param S 文字列 * @param base 基数 * @return {@code S}のローリングハッシュ */ static RollingHash create(char[] S, long base) { return create(IntStream.range(0, S.length).mapToLong(i -> S[i]).toArray(), base); } /** * 文字列{@code S}に対して2^{61}-1を法とするローリングハッシュを計算します。 * @param S 文字列 * @param base 基数 * @return {@code S}のローリングハッシュ */ static RollingHash create(String S, long base) { return create(IntStream.range(0, S.length()).mapToLong(S::charAt).toArray(), base); } }