题解：CF1515E Phoenix and Computers
_xm_
·
·
个人记录
最后手动打开的电脑一定是若干连续段，中间隔一个自动打开的电脑。
对于长为 l 的段，标号的方案是 \sum_{i = 0}^{l - 1} \binom{l - 1}{i} = 2^{l - 1}。
单个段的 EGF 为：
G(x) = \sum_{n = 1}^{+\infin} \dfrac{2^{i - 1} x^n}{n!} = \frac{e^{2x} - 1}{2}
枚举有 k 个段，则答案是：
\sum_{k = 1}^{\left\lceil \frac{n}{2} \right\rceil} \left[\frac{x^{n - k + 1}}{(n - k + 1)!}\right] G^k(x)
二项式展开系数：
\begin{align*}
\left[\frac{x^n}{n!}\right]G^k(x) &= \left[\frac{x^n}{n!}\right]\left(\frac{e^{2x} - 1}{2}\right)^k = \left[\frac{x^n}{n!}\right]\frac{1}{2^k} (e^{2x} - 1)^k \\
&= \frac{1}{2^k} \sum_{i = 0}^{k} \binom{k}{i} \left[\frac{x^n}{n!}\right]\left(e^{2x}\right)^{i} (-1)^{k - i} \\
&= \frac{1}{2^k} \sum_{i = 0}^{k} \binom{k}{i} (2i)^n (-1)^{k - i}
\end{align*}
时间复杂度 O(n^2)，代码 link。