\(f(P)\) の計算に際して、操作による \(X\) の変化が一見複雑に見えますが、実は末尾への移動回数については単純な構造をしています。

たとえば \(P_N=1\) のとき \(f(P)\) はどうなるでしょうか？実は常に \(f(P)=(0,1,2\dots,N-1)\) となります。このことを示しましょう。まず \(X_N=1\) が先頭に来るまでの動作を考えると、 \(X_1,X_2,\dots,X_{N-1}\) はかならず \(1\) 回だけ末尾に移動させられます。また、このうち \(2\) は \((2,1,\dots,)\) という形になるまで末尾に回されないため、先頭が \(1\) になったとき、末尾の値は必ず \(2\) になっています。以降の動作を考える際は先頭の \(1\) は明らかに無視してよいことを考えると、 \(X\) は末尾が最小値の順列になっています。よって帰納法からしめすことができました。

以上の事柄を一般化すると、 \(f(P)\) の計算方法について以下が成り立ちます。

$(1,2,\dots,k)$ が $P$ の部分列であるような $k$ の最大値を $K$ とし、 $P_{A_i}=i\ (i=1,2,\dots,K)$ が成り立つものとする。また、便宜上 $A_0=0,A_{K+1}=N+1$ とする。 このとき、各 $i$ に対する $P$ の $A_i+1$ 項目から $A_{i+1}-1$ 項目の値の $P$ における順序は $f(P)$ に影響を与えない。

これも操作過程で \(1\) が先頭に来るまでに \(A_1-1\) 項目までは必ず末尾に \(1\) 回移動されることと、 \(1\) が初めて先頭に来た時、 \(P\) の末尾の値は必ず \(A_1-1\) 項目までの値の最小値であることから帰納法で示すことができます。

これを踏まえると \(f(P)\) を計算するアルゴリズムとして以下が考えられます。

1. \((1,2,\dots,k)\) が \(P\) の部分列であるような \(k\) の最大値を \(K\) とし、 \(P_{A_i}=i\ (i=1,2,\dots,K)\) が成り立つものとする。また、便宜上 \(A_0=0,A_{K+1}=N+1\) とする。
2. \(i=1,2,\dots,K+1\) に対し、集合 \(S_i\) を \(P\) の \(A_{i-1}+1\) 項目から \(A_i\) 項目までの値からなる集合とし、 \(S_1,S_2,\dots,S_{K+1}\) の順で queue にいれる。
3. \(x=1,2,\dots,N\) の順に以下を行う。
   • queue の先頭から \(x\) が含まれる集合が pop されるまで pop する。 pop した集合の和集合から \(x\) を取り除いた集合を queue の末尾に追加する。

すると \(f(P)\) としてありうるものの生成を考える際は queue 内の集合の要素を考える必要は無く、 \(x\) がどの集合に属しているかを後付けで決めればいいです。そのため、集合については何回末尾に回された要素からなるかだけを考えればよく、動作を観察すると先頭から順に \(t,t,\dots,t,(t\) または \(t+1),t+1,\dots,t+1\) という形になっていることが分かります（ \(t\) または \(t+1\) 回末尾に回された要素からなる集合は \(x=K+1\) のときの集合の合併で生じます）。以上をまとめると \(f(P)\) としてありうるもののうち、 \((0,0,\dots,0)\) 以外を生成するアルゴリズムは以下のようになります。

1. \(1\) 以上 \(N-1\) 以下の整数 \(K\) を選び、 \(C=(0,0,\dots,0,1), Q=((1,1),(1,1),\dots,(1,1),(1,2))\) で初期化する。ここで、 \(C\) に含まれる \(0\) の数や \(Q\) に含まれる \((1,1)\) の数は \(K\) 個である。
2. 以下を \(C\) の長さが \(N\) になるまで繰り返す
   • 適当な整数 \(k\) を選ぶ。\(Q\) の \(1,k\) 項目が \((a,b),(c,d)\) であるものとする。 \(C\) に \(c,d\) のいずれかを追加する。その後、 \(Q\) の \(k\) 項目までを pop し、 末尾に \((a+1,d+1)\) を追加する。

\(Q\) の状態は \(((t,t),(t,t),\dots,(t,t+1),(t+1,t+1),\dots,(t+1,t+1))\) という形になっています。 \((t,t),(t+1,t+1)\) がそれぞれ \(n,m\) 個である状態を状態 \([t,n,m]\) と表現することにします。

状態 \([t,k,0]\) から \(n\) 項生成するとき、生成されるものの種類数を求めることを考えましょう。初項について \(t+1\) にする場合は明らかに \((t,t+1)\) を選ぶのが貪欲です。先頭 \(i\) 項を \(t\) にする場合を考えます。まず \(i-1\) 個分については先頭の \((t,t)\) を選ぶのが貪欲です。問題は \(i\) 項目の生成において、先頭の \((t,t)\) と \((t,t+1)\) の \(t\) のどちらを選ぶべきかです。ここでは基本的に \((t,t+1)\) の \(t\) を選ぶものとして（第一の選択肢）、 \((t,t)\) の \(t\) を選んだ場合（第二の選択肢）にのみ生成できる \(C\) について考えます。

まず \(t\) を \(i\) 個追加した後、 \(Q\) の状態は \([t,k-i,i]\) になっており、 \(t\) 以外には \(t+1\) を追加するしかありません。状態 \([val,x,0]\) から生成できる \(C\) の種類数は \(x\) について明らかに単調なので \((t,t+1)\) の \(t+1\) を選ぶのが貪欲で、状態は \([t+1,i,0]\) に移行します。この状態から \(t+1\) を何回追加するかで場合分けして考えると、

• \(i-2\) 個以下の場合：この場合 \([t+1,i,0]\) から \([t+2,j-1,0]\) か \([t+1,i-j,j]\rightarrow [t+2,j,0]\) と移行しますが、 \([t,k,0]\rightarrow [t+1,i-1,0] \rightarrow [t+1,i-2,0]\) というようにして、 \(j \leq i-2\) よりここからどちらの状態にも移行できます。よってこれにより生成できる \(C\) はすべて第一の選択肢を選んだ場合も生成できます。

• \(i-1\) 個の場合：この場合 \([t+1,i,0]\) から \([t+2,i-2,0]\) か \([t+1,1,i-1]\rightarrow [t+2,i-1,0]\) に移行できますが、前者の状態には第一の選択肢からでも移行できるので後者のみを考えることにします。この状態から \(t+2\) を \(i-2\) 個以下追加する場合は上記の議論と同じように第一の選択肢からも可能であるため考えなくていいです。 \(i\) 個追加する場合は第一の選択肢からは不可能であることが確定します。 \(i-1\) 個追加する場合は先ほどの議論と同じで \([t+2,0,i-1]\rightarrow [t+3,i-1,0]\) という状態以降のみを考えることになり、これは先の状況と同じです。以上より第二の選択肢からのみ生成される \(C\) は \(t+1,t+2,\dots,t+a-1\) を \(i\) 項ずつ追加し、 \(t+a\) を \(i+1\) 項追加したあと、生成アルゴリズムを続けたものと特徴付けられ、これを行った後状態は \([t+a+1,i-1,0]\) に移行します。

• \(i,i+1\) 個の場合；この場合第一の選択肢によって生成できない \(C\) であることが確定します。状態は \(i+1\) 個の場合は必ず \([t+2,i,0]\) に移行しますが、 \(i\) 個の場合は再び第一・第二の選択肢の選択を考える必要がでてきます

以上より

\(dp[0][k][n]:\) 状態 \([t,k,0]\) から \(n\) 項生成するときの種類数

\(dp[1][k][n]:\) 第二の選択肢を選んだあと状態 \([t,k,0]\) から \(n\) 項生成するときの種類数

とおくと \(0 < k\) のとき、

\[\displaystyle dp[0][k][n] = dp[0][0][n-1] + \sum_{i=1}^{k+1} dp[0][i-1][n-i] + \sum_{i=1}^{k}dp[1][i][n-i-1] \]

\[\displaystyle dp[1][k][n] = \left(\sum_{2\leq i} dp[0][k-1][n-ik]\right) + (dp[0][k-1][n-k] + dp[1][k][n-k-1]) + dp[0][k][n-k-1]\]

が成り立ち、これは \(O(N^3)\) 時間で計算することができ、問題の制約下では十分高速です。

ところで階差を取ると

\[dp[0][k][n] = dp[0][k-1][n] + dp[0][k][n-k-1] + dp[1][k][n-k-1]\]

\[\displaystyle dp[1][k][n] = (dp[1][k][n-k] - dp[1][k][n-2k-1] - dp[0][k][n-2k-1] + dp[0][k-1][n-k]) + dp[1][k][n-k-1] + dp[0][k][n-k-1]\]

が成り立ちます。

このような漸化式で計算できる値について、最終的に \(\sum_{i}dp[0][i][N-2-i]\) が求めたい値です。この計算は分割数のdpと同じような高速化（参考: https://degwer.hatenablog.com/entry/20170829 ）ができ、 \(B=\lceil \sqrt{N} \rceil\) としたとき \(sdp[p][t][s] = \sum_{B\leq x} dp[p][x][s-tx]\) とおくと \(t \leq B\) の範囲だけ考えればよく、これは \(dp[p][k][n]\) が \(k\leq B\) の範囲で計算されていれば計算できるので \(O(N\sqrt{N})\) 時間で計算できます。