原题等价于，反转 01 串的一段后缀，使得 01 串的 popcnt 最小。

证明：因为没有子串 10，最后一定是 00000...11111 。

于是把原串分为左右两段：

• 左边一段删去所有的 1，操作次数即 popcnt。
• 右边一段删去所有的 0，操作次数即反串的 popcnt。

注意到反转后缀对 popcnt 的增减量是后缀和（0 为 1，1 为 -1），

考虑增量构造，设 $r$ 为当前情况下原串的 popcnt，$m$ 为当前情况下的答案。

• 若往后添加一个 $1$（概率 $1-p_n$），$m$ 不变，$r++$。
• 若往后添加一个 $0$（概率 $p_n$），
  • 如果 $r=m,r,m$ 均不变。（不反转是最优的）
  • 否则 $r$ 不变，$m++$。（反转会多产生 $1$ 的代价）

于是设 $l=r-m$，则设 $f_{n,l,m}$ 即可得到 $\Theta(n^3)$ 的 dp。

注意到期望满足线性性，于是设 $f_{n,l}$ 表示期望，$g_{n,l}$ 表示概率，即可得到 $\Theta(n^2)$ 的 dp：

$$f_{0,0}=0,g_{0,0}=1$$ $$f_{n,l}=p_n(f_{n-1,l+1}+g_{n-1,l+1})+(1-p_n)f_{n-1,l-1}\quad(l\not=0)$$ $$g_{n,l}=p_ng_{n-1,l+1}+(1-p_n)g_{n-1,l-1}\quad(l\not=0)$$ $$f_{n,0}=p_n(f_{n-1,0}+f_{n-1,1}+g_{n-1,1})$$ $$g_{n,0}=p_n(g_{n-1,0}+g_{n-1,1})$$

接下来考虑怎么多项式搞这玩意。

这玩意很毒瘤，不是倍增也不是分治，而是倍僧套分治。。。

显然往末尾填 $p_n=0$ 对最终答案没有影响，把 $n$ 填充为 $2$ 的幂次。

注意到 $l\le n$，因此 dp 状态相当于一个等腰直角三角形

显然这玩意适合倍增

于是我们只要考虑如下直角梯形的转移

卷积允许我们作如下等腰梯形的转移

于是把梯形分成左右两段，上面就可以卷积转移

下面的转移可以分治

于是直角梯形的转移就可以分治 FFT $\Theta(n\log^2 n)$ 解决。

等腰直角三角形的转移就倍增套上直角梯形的转移就行了，

总复杂度 $T(n)=T\left(\dfrac{n}{2}\right)+\Theta(n\log^2 n)=\Theta(n\log^2 n)$