本解説において、問題文における \(2N+1\) のことを \(N\) と書きます。また、一部 \(N\geqq 3\) を仮定します。

いろいろ \(\pmod{N}\) で考えます。\(C_i\) からは、\(1\) を引いておきます。

操作の言い換え、問題の言い換え

次のように言い換えられます。

• 操作 1：\(x\) 番目に置かれているカードを、\(x - k\) 番目にうつす。
• 操作 2：\(x\) 番目に置かれているカードを、\(2x\) 番目にうつす。

操作1, 2 の合成の結果、ある \(a, b\) に対して \(x\) 番目に置かれたカードが \(ax-b\) 番目にうつることになります。このような \((a,b)\) を状態として持つと、

• \((a,b) = (1,0)\) から始める
• 操作 1：\((a,b)\) を \((a,b-k)\) にうつす
• 操作 2：\((a,b)\) を \((2a,2b)\) にうつす

となります。

目標の \((a, b)\) は存在すれば一意に定まる（\(x=0, 1\) に対する目標値から計算できます）ので、\((a,b)\) の存在判定・計算のあとには次の問題が残ります：

【問題】\((1,0)\) からはじめて操作 1, 2 により \((a,b)\) を得るための最小操作回数を求めよ。

最小操作回数の計算（操作 2 の回数固定）

操作 2 を行う回数 \(p\) を決め打ってみます。このような \(p\) は、\(2^p \equiv a\pmod{N}\) を満たすものに限定されます。

操作 2 の途中に操作 1 を挿入すると最終的な \(b\) の値に \(2^ik\) を加算することができます。したがって、\(p\) を固定した場合の計算対象には、次の部分和問題です。

• \(A = \{2^ik \mid k\in K, 0\leq i\leq p\}\) とおく。
• \(b\) を \(A\) の元の和で表すときの、最小要素数を求めよ。

まず、集合 \(A\) を求めます（\(O(Mp)\) 時間）。\(\pmod{N}\) で同一視することで、\(|A|\leq N\) となります。よって、部分和問題の dp を \(O(N^2)\) 時間で計算できます。

以上により、操作 2 の回数を決め打った場合には、最小回数が \(O(Np + N^2)\) 時間で計算できます。

最小操作回数の計算

操作 2 の回数 \(p\) については、2 通りしか考える必要がありません。\(2^n \pmod{N}\) の周期を超えた時点で、\(A = \{2^ik \mid k\in K, 0\leq i\leq p\}\) はそれ以上増えなくなるからです。

小さい方から \(2\) 番目の \(p\) は（あれば） \(p \leq 2N\) を満たします。これら \(2\) 通りの \(p\) に対して上述の計算を行うことで、全体として \(O(N^2)\) 時間で答を求めることが出来ます。