题解 P5388 【[Cnoi2019]最终幻想】

yamengxi

2019-10-15 17:13:20

Solution

这道题我推出来一个优美的公式：

ans= \begin{cases} 2^k,\ \ k \le n \\ C_k^n+2^k-\sum_{i=0}^{k-n}C_{i+n-1}^{n-1}\cdot2^{k-n-i},\ \ k>n \end{cases}

我有一个极为巧妙的证明方法，可惜这里地方太小，写不下。