题解：P3352 [ZJOI2016] 线段树

· · 题解

我从来不相信注定 不能只是做个手下败兵

考虑 0/1 怎么做，一次操作相当于区间变成按位或的结果。我们计数一个位置为 0 的方案数，考虑一个位置之和跟其左边和右边的第一个 1 有关，更具体的，我们可以把 0 连续段放在一起做。

设 f_{i,l,r} 表示做了 i 次操作，连续段 [l,r] 的方案数。转移有：

f_{i,l,r}=f_{i-1,l,r}\times\frac{l(l-1)+(n-r+1)(n-r)+(r-l+2)(r-l+1)}{2}+\sum_{j=1}^{l-1} f_{i-1,j,r}\times (j-1)+\sum_{j=r+1}^{n} f_{i-1,l,j}\times(n-j).

后面两项可以前缀和优化，时间复杂度 O(n^2mV)，其中 V 是值域。

由于对于每个值统计答案和转移方式一模一样，可以把这 V 次 dp 放在一起转移，时间复杂度 O(n^2m)。