包除原理することを考えます。

人 \(2, 3, \dots , 2^{N}\) を \(N\) 個のグループ \(G_{0}, G_{1}, \dots , G_{N - 1}\) に分けます。グループ \(G_{i}\) のサイズは \(2^{i}\) です。

この分け方のうち、任意の \(i\) に対して、\(\min(G_{i})\notin A\) が成り立つような分け方に対して、適切な係数 (\(2^{N}\cdot 2^{0}! \cdot 2^{1}! \cdot \cdots \cdot 2^{N - 1}!\)) をかけたものが答えです。

以下の補題を考えます。

\((A_{1}, A_{2}, \dots , A_{M})\) の(連続とは限らない)部分列 \(S\) と \((0, 1, \dots , N - 1)\) の(連続とは限らない)部分列 \(T\) が与えられます。ここで、\(|S| = |T|\) です。

このとき、\(1 \leq i \leq |S|\) 全てに対して、\(S_{i} = \min(G_{T_{i}})\) が成り立つようなグループの分け方は何通りありますか。

この補題は、\(i = |S|, |S| - 1, \dots , 1\) の順に、グループ \(G_{T_{i}}\) の中身を決めることを考えることで答えが以下のように求まります。

\[\dfrac{(2^{N} - 1 - \sum_{k = 1}^{|T|} 2^{T_{k}})!}{\prod_{k \notin T} 2^{k}!}\prod_{i = 1}^{|S|}\dbinom{2^{N}-A_{i}-\sum_{k = i + 1}^{|T|}2^{T_{k}}}{2^{T_{i}} - 1}\]

これを dp することを考えます。

以下の答えを \(dp[a][b]\) とします。

\((A_{a}, A_{a + 1}, \dots , A_{M})\) の(連続とは限らない)部分列 \(S\) と \((0, 1, \dots , N - 1)\) の(連続とは限らない)部分列 \(T\) が与えられます。ここで、\(|S| = |T|\) です。

また、\(b = \sum_{k \in T} 2^{k}\) です。

このとき、\(1 \leq i \leq |S|\) 全てに対して、\(S_{i} = \min(G_{T_{i}})\) が成り立つようなグループの分け方は何通りありますか。

上記の式は dp できる形なので、その式を用いて dp すれば良いです。

計算量は \(O(NM2^{N})\) です。

より整理した式で実装したのが以下の実装例です。

実装例 c++