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)\)

​