\(A_i\) の制約がない場合を解きます．

レシピが保存される順番が \(1,2,\cdots,N\) だと仮定して問題を解き，答えを \((N-1)!\) 倍すればよいです．

まず，次のような DP を考えます．

• \(dp[i][A][B][C]=\)以下の条件を満たす操作方法の数．
  • \(i\): サーバー \(1,2,\cdots,i\) にレシピが保存されており，それ以外のサーバーには保存されていない
  • \(A\): 整数の組 \((x,y)\) (\(1 \leq x<y\leq i\)) であって，まだ選ばれていないものの集合
  • \(B\): 整数の組 \((x,y)\) (\(1 \leq x \leq i\), \(i<y\leq N\)) であって，まだ選ばれていないものの集合
  • \(C\): 整数の組 \((x,y)\) (\(i < x<y\leq N\)) であって，まだ選ばれていないものの集合

このDPの状態数を減らすことを考えます． まず，\(A\) に関しては \(|A|\) だけを持てば良いです． \(A\) に関する状態数は \(O(N^2)\) になります．

次に \(C\) を考えます． DPの遷移を考えると，\(i,A,B\) と \(|C|\) を決め打った場合，\(C\) の中身によらず \(dp[i][A][B][C]\) の値が一定になることがわかります． つまり，\(|C_1|=|C_2|\) ならば，\(dp[i][A][B][C_1]=dp[i][A][B][C_2]\) が成立します． よって，\(C\) についても \(|C|\) だけを持てばよいです．\(C\) に関する状態数は \(O(N^2)\) になります．

最後に \(B\) を考えます． \(B\) も \(C\) と同様の考え方で状態数を減らせます． それぞれの \(x\) (\(1 \leq x \leq i\)) について，\((x,y) \in B\) なる \(y\) (\(i < y \leq N\)) の集合を \(Y(x)\) とすると，\(|Y(x)|\) だけが重要になります． よって必要なのは \(|Y(1)|,|Y(2)|,\cdots,|Y(i)|\) の値です． さらに，これらの順序も関係ないので，情報として必要なのは，長さ \(i\) で値域が \([0,N-i]\) の広義単調増加列 \((b_1,b_2,\cdots,b_i)\) です． 結局，\(B\) に関する状態数は \(O(2^N)\) になります．

以上で状態数を \(O(2^N N^4)\) にできました．

あとは遷移を考えます． \((x,i+1)\) (\(1 \leq x \leq i\)) を選ぶ遷移の処理で，\(B\) を変化させる部分に工夫が必要です． \((b_1,b_2,\cdots,b_i)\) のうち \(1\) つ以上の要素を \(1\) 減らす，といった遷移が必要になります． この遷移は \(i\) ステップかけて行うことにします．\(j\) ステップ目では，\(b_j\) を減らすか否か選択することにします． 減らすことを選択した場合，\((b_1,b_2,\cdots,b_j-1,\cdots,b_i)\) をソートした列に遷移させます． \(b\) がもともとソートされているので，この方法で遷移しても，同じ値を \(2\) 度減らすことは起きないので問題ありません．

以上を合わせると，\(O(2^N N^5)\) 時間でこの問題を解くことができます．

\(A_i\) の制約を考える場合は，最後に \((N-1)!\) 倍するのをやめます．代わりに，\(A_i\) 回の操作が終わった段階でレシピの保存されているサーバーの中から，サーバー \(i\) と名付けるものを選ぶ，という操作を考えればよいです．

解答例(c++)