CF294C Shaass and Lights

· · 题解

考虑 dp。不会。

然后考虑能否用组合数直接算。

容易想到根据 a_i 分段，分为若干 (a_i,a_{i+1}) 先不考虑每一段中的不同方案数，仅考虑整个操作序列第 i 次操作亮的灯属于哪个段有多少种不同的操作序列，这个就是 多重集排列数 答案是 \frac{(n-m)!}{\prod_{i=2}^{m} (a_i-a_{i-1}-1)!}。

然后考虑每一段内的方案数。

假设段长为 len，每段中必定是从 l 扩展 x 盏灯和从 r 拓展 len-x 盏灯，那么就是 \sum{ len\choose x} 就是 2^{len}。发现这样不对，因为假如段为 (1,5)，那么以下两种操作序列算一种。

(1\to 2),(2\to 3),(3\to 4) (1\to 2),(2\to 3),(5\to 4)

其中 (i,j) 表示意为从 i 拓展出 j。

发现对于每种情况会算 2 遍，最后一个点从左边拓展或者从右边拓展会重复算，所以除 2，每段方案数就是 2^{len-1}，所以最终答案就是 \frac{(n-m)!\prod_{i=2}^m 2^{a_i-a_{i-1}-2}}{\prod_{i=2}^{m} (a_i-a_{i-1}-1)!}。

时间复杂度 O(n\log n)，所以这题 n\le 1000 是啥意思。