cf 1515E. Phoenix and Computers (dp計數|分段合并)

給定若幹計算機1~n，每次操作可以選擇一台計算機\(i\)，并将其打開。若計算機\(i+1\)和\(i-1\)已經被打開，那麼\(i\)會自動打開。問有多少種操作序列，使得n台計算機全部打開。

[]: ​​https://codeforces.com/contest/1515/problem/E​​ "傳送門"

計算機1~n的最終狀态一定是：一段計算機手動打開+一台計算機自動打開+一段計算機手動打開+...+一段手動+一台自動+一段手動。

考慮全部手動打開一段計算機的方案數，假設這一段共有k台計算機，對其分别進行編号 1~k 。

設第一台手動開啟的計算機為\(i（i∈[1,k]）\)， 對于區間\([i+1,k]\)的計算機的打開順序必然是 \(i+1,i+2,..,k\) ，否則必然會在中間産生一個自動打開的計算機，同理，對于區間\([1,i-1]\)的計算機的打開順序必然是 \(i-1,i-2,..,1\) ，而這兩個區間的打開順序在保證各自的相對順序的前提下，是可以互相穿插的，方案數為\(C_{k-1}^{i-1}\)（考慮穿插結果，共有k-1為位置，選擇i-1個位置放置序列 \(i-1,i-2,..,1\),剩下放置 \(i+1,i+2,..,k\) ）。

那麼手動打開一段計算機的總方案數為\(C_{k-1}^{0}+C_{k-1}^{1}+C_{k-1}^{2}+...+C_{k-1}^{k-2}+C_{k-1}^{k-1} = 2^{k-1}（二項式定理）\);

接下來考慮如何計算"一段計算機手動打開+一台計算機自動打開+一段計算機手動打開"，可以先計算出前幾段的方案數，再合并新的一段手動打開的計算機，

定義\(f(i,j)\)表示前\(i\)個計算機中有\(j\)個計算機是手動打開的方案數，

轉移方程：\(f(i+1+k,j+k) ~=~f(i,j) \times 2^{k-1} \times C^k_{j+k} ~~~~\),\(k\)為要合并的下一段手動打開計算機的數量，\(2^{k-1}\)為下一段計算機内部的方案數，\(C^k_{j+k}\)為将下一段計算機與之前手動打開的計算機互相穿插并保證各自的相對順序不變的方案數；

最終答案 = \(\sum _{i=0}^nf(n,i)\)

​