NOMURA プログラミングコンテスト 2021(ARC121) C - Odd Even Sort

AtCoder公式の解説とは若干異なる手法で解いたので記事化。

問題

$(1, 2, ...N)$の順列$p$がある(1-indexed)。

隣り合う要素$p_n$と$p_{n+1}$を入れ替えて昇順に並び替える。ただし、奇数回目の操作では$n$は奇数、偶数回目の操作では$n$は偶数でなければならない。

$p$を昇順に並べ替える操作列であって、操作回数が$N^2$回以内であるものを1つ求めよ。

注記:

$1$番から$N$番までのコンピュータが1列に並んでいます。

最初全てのコンピュータはOFFになっており、コンピュータの電源を任意の順番でONにしていきます。

ここで、両隣のコンピュータがONならば、真ん中のコンピュータも自動的にONになります。

全てのコンピュータをONにする方法は何通りあるでしょうか？素数$M\　$で割った余りを求めてください。

$0$ から $2^n-1$ までの番号がついた星があります。

$i\oplus j$が $A_1, A_2, ..., A_M $のいずれにも含まれないような星 $i$と $j$を選んで、相互に移動可能なワープホールを作ることができます。

$N-1$個のワープホールを作ることで、任意の2つの星の間をワープホールで移動できるようにしたいです。

この目標が可能であるか判定し、可能ならばワープホールの作り方の一例を示してください。

暇なときに競技プログラミングの考察や解法などを書くブログ。

をテーマに解説記事を書いていきたいと思っています。