部分点解法

カードを食べる順番に関する純粋な bitDP （巡回セールスマン問題を解く際に用いられるものと同じようなものです）を適用することを考えます。すなわち、\(dp[bit][i]\) := 既に食べた集合が \(bit\) で、そのうち最後に食べたカードが \(i\) であるときの操作 \(1\) の最小値、と定義した DP を行います。

遷移を計算するためには、「既に食べているカードの集合が \(bit\) で、カード \(i\) の次にカード \(j\) を食べるために何回操作が必要か？」を高速に計算する必要があります。

これは、カード番号の \(3\) つ組 \((i, j, k)\) に対して、「\(i\) を食べた後に \(j\) を食べるために \(k\) が邪魔になるような山の数」を前計算することで、\(O(M)\) で計算できます。

計算量は \(O((N + 2^M)\) \(M^3)\) です。

---

満点解法

カードを食べる順番を固定（例えば、\(p_1, p_2, \ldots, p_M\) の順にカードを食べるとします）したときの状況について考えましょう。

ある一つの山に注目します。この時、この山を食べ終わるのに必要な操作回数に関して、以下の重要な事実を得ます。

事実 :（必要な操作 \(1\) の回数）\(=\) \(p_i\) が \(p_{i+1}\) よりもカードの山の下に位置するような \(i\) について、\(m - i - 1\) を合計した値

非厳密な証明

要するに、全部で何回カードが山の下に送られるかを求める必要があります。「\(p_i\) が \(p_{i+1}\) よりも下にある」ということは、そのタイミングで山札の”周回”が終わり、「その時点でまだ食べ終わってないカードが山札の下に送られていた」ということになります。よって、カードを山札の下に送るタイミングで加算する代わりに、この”周回”が終わるタイミングで加算します。

よって、カード番号の \(2\) つ組 \((i, j)\) について、「\(i\) が \(j\) より山札の下にあるような山はいくつあるか？」を前計算しておけば、遷移が \(O(1)\) で計算できます。

計算量は \(O((N + 2^M)\) \(M^2)\) です。

（部分点解法との実行時間の区別が厳しく、想定解と同じオーダーの解放がTLEするかもしれません。）