\(A,B\) をソートします。すると、\(f(P)\) は \(P=(1,2,\dots,N)\) の時に最小値を取ります。証明として、\(a < b,k > 0\) ならば \(a + \lfloor \frac{b}{2^k} \rfloor \le \lfloor \frac{a}{2^k} \rfloor + b\) を言えばよいですが、これは \(x - \lfloor \frac{x}{2^k} \rfloor\) の単調増加性により分かります。

基本的に解の形としてはほとんど \(A,B\) をそのまま対応させるものしかありませんが、\((a,b) = (3,0),(4,1)\) を \((a,b) = (3,1),(4,0)\) などと組み替えることが出来ます。

具体的に、\(B\) に含まれる \(0\) をどの \(A\) の要素に対応させるかを考えます。\(B\) に \(0\) が \(k\) 個含まれるとすると、基本的には \(A\) の小さい方から \(k\) 個と対応させるべきです。ですが、\((a,b) = (2k-1,0),(2k,1)\) というペアを \((a,b)=(2k-1,1),(2k,0)\) と組み替えることが出来ます。この組み換えを複数回行ったのち、\(0\) とマッチした \(A\) の要素を全て削除し、残った要素を全て \(2\) で割り再帰を行います。

途中に現れる \(A\) の状態としては、「\(A\) の suffix を \(2^i\) で割り、かつ \(A\) の \(k\) がいくつか \(k-1\) になっている」という形をしています。更に、\(k\) は \(A\) の最小値か \(2\) 番目に小さい値を取ります。この時、\(k-1\) になった個数分今後コストを得する必要があります。(直前のステップで \(k\) を \(B\) の \(0\) と対応させた分のコストを帳消しにする必要があるため)

しかも、\(B\) の \(x\) を対応させる \(A\) の要素を選ぶタイミングで組み換えが出来るペアの値は常に一定であることも分かります。これを元に遷移を行うことが出来ます。例として、\(k\) が奇数であり、今回組み換え出来るペアが \((k,k+1)\) であるときの遷移を具体的に説明します。\(k\) が \(i\) 個 \(k-1\) になっているような場合の数を \(dp[i]\) とし、組み換えによって次の \(\frac{k+1}{2}\) が \(j\) 個 \(\frac{k+1}{2}-1\) になっている場合の数を \(dp2[j]\) とします。また、\(k,k+1\) の個数をそれぞれ \(x,y\) とし、\(B\) に含まれる \(0\) の個数を \(z\) とし、\(w = x+y-z\) とします。

\(k\) が \(k-1\) になっているものは組み換えが出来ないことに注意すると、遷移は以下のようになります。

• \(dp2[j] = \sum_{i}^{} dp[i] \binom{x-i}{j} \binom{y}{w-j}\)

他にも \(k+1 < x\) に対して \((x,x+1)\) が組み換え出来る場合と、\((k-1,k)\) が組み換え出来る場合と、\((k-2,k-1)\) が組み換え出来る場合がありますが、全て同じような遷移になります。あとはこの遷移を畳み込みで高速化すれば計算量が \(\mathrm{O}(B N \log N)\) となり十分高速です。