riano君の移動は、赤色と他の任意の色の位置をswapする操作と同一視できます。 ここで、赤、青、黄、緑にそれぞれ という数を当てはめて考えます。

まず、色の配置として取りうる状態は全部で 通りしかあり得ません。 したがって、実行時間が許すのならば 個の状態を出発点とした連立漸化式を組み、その通りに DP を行うことで解くことが出来ます。 また、各ステップの遷移は同じ形ですので、行列累乗による高速化も可能です。

しかしながら、最大 個のテストケースについて、毎回 程度の行列累乗計算を行うことは出来ません。 そこで、考えられる状態の数を削減することを考えます。 riano君の移動を数列のswap操作と考えると、 回のswapによって転倒数の偶奇が反転していることが分かります。 したがって、 通りのうち、奇数ステップ目にしかあり得ない状態と、偶数ステップ目にしかあり得ない状態があることが分かります。 元通りの状態は、転倒数が ですので、偶数回目にしかあり得ません。よって、 を偶数に限って解くことを考えます。 さらに、上記の事実を用い、 回おきの遷移で漸化式を組むことを考えると、考えるべき状態数は半分になり、行列累乗の計算時間は になります(が、まだ不十分です)。

この設定の最大の性質は、赤以外の色、および初めに赤だった面以外の面の位置に対する対称性です。 最初の状態で、赤の面の中心を通る軸のまわりに回転させておくことを考えます。 (これはすなわち、最初に緑に移っていた経路を、最初に黄色に移り、そこから先の相対的な移動を同じとする経路を考えることと等価です。) これによって変換される終状態は、数列の上では を順に置換し、同時に 項目を 項目に、 項目を 項目に、 項目を 項目に移動させる操作と対応します。 そして、この操作によって移り変わる状態は、スタート時に正四面体を適切に回転させておくことで、同じ移動経路によってたどり着くことが可能であると分かります。 したがって、このようにまとめられる状態について同一視して確率を求めてよいです。

このような対称性を用いると、例えば転倒数が奇数である数列によって表現される状態は、以下の つの系列に分類できます。

このうち、 つめおよび つめの系列は、実はさらなる対称性(正四面体の赤でない 面を入れ替える鏡映)によって相互に移り変わるため、まとめることができます。 よって、最終的には、転倒数が奇数である状態は以下の パターンに分類されることになります。 これらは以下に記すように、正四面体上の色の様子から見ても、対称であることを確認することができます。

①:赤と他の一色のみ入れ替わった状態:

②:赤以外の二色が入れ替わった状態:

③:②から赤を含む 色を一つずつずらした状態:

これらの間の遷移を表す行列は、手計算またはプログラムによるシミュレーションで求められ、

となります。(上記の 分類の経路数をこの順に並べたベクトルに作用させる行列として表現しています。)

これにより 回目の移動後から 回目の移動後までの遷移を計算することができ、 また 回目の移動後には確実に①の状態であること(すなわち、①の状態のみ 通りの状態からスタートすること)、 回目に元に戻るのは、 回目に①の状態であり、さらにそこから 通りの適切な移動が必要であることも用いると、 条件を満たす移動経路の数を求めることができています。

なお、転倒数が偶数の状態に着目すると、最終的には パターンの分類になり、やや手間と実行時間が増えますが、ほぼ同様にできます。 この場合は上記のような両端の処理の考察は不要になります。

以上のように行列のサイズを削減することで、計算量が となり、制限時間内に答えを求めることができます。