AtCoder Grand Contest 044 C - Strange Dance

想定解とは異なる解法で通しました。計算量は想定解の方がよいです。

問題

AtCoder Grand Contest 044 C - Strange Dance

解法

$ i , j \in \{ 0 , \ldots , 3 ^ N - 1 \} $ に関して、$i$ と $j$ の下位 $k$ trit が等しいならば、$P_i$ と $P_j$ の下位 $k$ trit も等しくなります。そこで、添字を上位 $\left\lfloor \dfrac{N}{2}\right\rfloor$ trit と下位 $N - \left\lfloor \dfrac{N}{2}\right\rfloor$ trit に分けて考えます。

下位 $N - \left\lfloor \dfrac{N}{2}\right\rfloor$ trit に関しては、愚直にシミュレートすることですべての $i \in \{ 0,\ldots, 3 ^ N - 1\} $ に対する $P_i$ の下位 $N - \left\lfloor \dfrac{N}{2}\right\rfloor$ trit を求めます。このパートの計算量は $O( N \cdot 3 ^ {N/2} \cdot | T | )$ です。

続いて、上位 $\left\lfloor \dfrac{N}{2}\right\rfloor$ trit について考えます。難しいのは、下位の桁からの繰上りがあることです。下位 $N - \left\lfloor \dfrac{N}{2}\right\rfloor$ trit を固定すると上位 trit の値に関わらず繰上りが起こるタイミングが等しいことに注目し、下位 trit を固定します。各繰上りの間にサルサが偶数回流れたか、奇数回流れたかを $O(1)$ で求められるように適切な前計算 1 をしておくことで、下位 trit を $\mathrm{lower}$ で固定したときの上位 trit の行先を $O(N \cdot 3^{N/2} \cdot \mathrm{carry}(\mathrm{lower}))$ でシミュレートできます。ここで、 $\mathrm{carry}(\mathrm{lower})$ は下位 trit を$\mathrm{lower}$ で固定したときの繰上りの回数です。$C_R(T)$ を $T$ に含まれる R の数として、$\displaystyle \sum_{\mathrm{lower} = 0 } ^ { 3 ^ {N - \lfloor N/2 \rfloor} - 1} \mathrm{carry}(\mathrm{lower}) = C_R(T) \leq |T| $ よりこのパートも全体 $O( N \cdot 3 ^ {N/2} \cdot | T | )$ で計算できます。

上位 trit の結果と下位 trit の結果をマージすることで答えが得られますが、このパートは $O(3 ^ N)$ で計算できるので、全体の計算量は $O(3 ^ N + N\cdot 3 ^ {N / 2} \cdot | T | )$ となります。

制約を考えるとかなりやばそうなんですが、250 ms くらいで通りました


  1. 例えば、$T$ に対して R を $0$ に、S を $1$ に書き換えて得られる数列の累積 xor を計算しておくとよいです