次のようなDPを考えます。

\(\mathrm{dp}[n][r][S]\) を以下で定めます。

• \(1\) 以上 \(N\) 以下の相異なる数からなる数列 \(A=(A_1,.\ldots,A_n)\) であって、以下の条件を全て満たすものの個数
  • すべての \(i\) で \(|A_i-i|\geq X\)
  • \(|A\cap\{t\mid t\geq n+X\}|=r\)、すなわち \(A\) は \(n+X\) 以上の数を \(r\) 個含む
  • \(A\cap\{t \mid n-X<t<n+X \}=S\)、すなわち \(A\) に含まれる \(n-X\) より大きく \(n+X\) 未満の数のなす集合は \(S\) に等しい

求める答えは \(\sum_S \mathrm{dp}[N][0][S]\) であることから、このDPテーブルを埋めることができればよいです。

\(\mathrm{dp}[n][r][S]\) から \(\mathrm{dp}[n+1][*][*]\) への遷移は、\(A\) に \(n+X\) が含まれているかどうかに応じて \(S\) を更新したのち、\(A_{n+1}\) として「\(n+1-X\) 以下の数」「\(n+1+X\) 以上の数」のどちらを割り当てるかで \(2\) つの遷移先があります。

この更新において「\(A\) に \(n+X\) が含まれているかどうか」の情報は、一見するとDPの状態だけから得られないように思えます。しかし、\(\mathrm{dp}[n][r][S]\) は \(n+X\) 以上の数はすべて”同じ”とみなしているので、対称性から、\(n+X\) 以上の数 \(N-(n+X-1)\) 個のうち \(r\) 個が \(A\) に含まれているということは、数列が \(n+X\) を含む “確率” が \(\displaystyle\frac{r}{N-(n+X-1)}\) であることを意味します。よってDPの状態から必要な情報を得られることがわかりました。

状態数 \(O(N^2 4^X)\)、遷移 \(O(1)\) であることから、計算量は \(O(N^2 4^X)\) です。

実装例(C)

この解法は「合計（数え上げ）」の問題を「期待値」の問題に読み替えるという典型の一種です。