神题，写篇题解学习一下。

学习 大犇的题解。

显然 $c_i$ 一定能写成 $a_ix+b_iy$ 的形式，考虑操作会对两部分有什么影响：

• 如果 $r_i=0$，那么 $a_i=a_{i-1}+1$。
• 如果 $r_i=1$，那么 $a_i=-a_{i-1},b_i=1-b_{i-1}$。

所以 $b_i \in [0,1]$。

对 $a_i,b_i$ 分开考虑，$f(r)=\sum_{i=1}^{n}a_ix+b_iy=x\sum_{i=1}^{n}a_i+y\sum_{i=1}^{n}b_i$，$b_i$ 对 $f(r)$ 的贡献是好算的，我们只需要知道 $1$ 到 $i$ 中 $r_i=1$ 的个数的奇偶性就可以了。

而 $a_i$​ 比较困难，简直就是神中神，画个图。

虚线表示水平或竖直辅助线，粉色和蓝色颜色内部互相抵消，和为 $0$。直接考虑 $\sum_{j=1}^{i}a_j$ 不好考虑，可以发现，$\sum_{j=1}^{i}a_j$ 只由绿色线段部分决定，设绿色线段尾部高度为 $h_i$，则有 $\sum_{j=1}^{i}a_j=\frac{h_i(h_i+1)}{2}$，于是我们再考虑这个 $h_i$ 的变化。

（动态地想一想 $h_i$ 随 $i$ 增大的变化，就像一条区在伸缩）

$\sum_{j=1}^{i} a_j\not=0$ 时转折点一定有 $r_i=1$，等于 $0$ 无所谓，取反没有用。

线段的斜率都是 $1$ 或 $-1$​，那么怎么求绿色线段尾端的高度呢？这就很天才了，把红色蓝色抵消的部分去掉，剩下的部分的横坐标等于纵坐标，不就是答案了吗？

（如果在 $\sum_{j=1}^{i} a_j=0$ 时来一大段 $1$ 怎么办？其实这也是一样的，自行画图）

于是我们可以设计出状态：设 $dp_{i,j,0/1}$ 为前 $i$ 个元素有 $j$ 个 $i$ 满足 $\sum_{j=1}^{i} r_j$ 为奇数，$r_i=1$ 的数量是否为奇数时是否是可行的。计算答案的时候，$n-2j$ 就是 $h_n$，$j$ 就是 $\sum_{k}^{n} b_k$，转移显然。

代码就不用放了吧（）