题解：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)

。

文章操作