Two Records

解説

操作ごとの $r$ の値を順に並べた列を $A$ とする。

$A$ を前半と後半に分け、それぞれの長さを $\left\lfloor\dfrac{N}{2}\right\rfloor, \left\lceil\dfrac{N}{2}\right\rceil$ とする。

前半の各項を $S, T$ に追加する組み合わせ $2^{\left\lfloor\frac{N}{2}\right\rfloor}$ 通りを全列挙する。前半の操作後の文字列をそれぞれ $S_1, T_1$ とする。すべての操作後に $S = T$ となるためには、 $S, T$ のうち短い方が長い方の接頭辞である必要がある。

$|T_1| \lt |S_1|$ の場合を考える。このとき、文字列 $U$ を用いて $S_1 = T_1 + U$ と表せる。

後半の操作で $S, T$ に追加される文字列をそれぞれ $S_2, T_2$ とすると、

$$S_1 + S_2 = T_1 + T_2 \iff U + S_2 = T_2$$

が成り立つ。 したがって、後半の操作では、 $U, S_2$ がそれぞれ $T_2$ の接頭辞、接尾辞であるようなものを探せば良い。

$|S_1| \le |T_1|$ のときも同じようにして考えることができる。

前半、後半で $2^{\left\lfloor\frac{N}{2}\right\rfloor}, 2^{\left\lceil\frac{N}{2}\right\rceil}$ 通り をそれぞれ半分全列挙し、map などを用いて出現回数を記録して $S=T$ となるような組を足し合わせることで答えが得られる。

$N = \left\lfloor\log_3{X}\right\rfloor + 1$ なので、計算量 $O\left(N^22^{\left\lfloor\frac{N}{2}\right\rfloor}\right) = O\left(X^{\log_3{\sqrt2}}(\log{X})^2\right)$ などでこの問題を解くことができる。なお、 $N \le 38$ である。