AGC137B Count 1's

传送门

题目大意

给定长度为\(N\)的01序列\(A:(A_1,A_2,A_3...A_N)\)，你可以进行一次如下操作

• 选择一段连续区间对它进行区间XOR，即\(0\rightarrow 1,1\rightarrow 0\)

你的得分为操作后序列中\(1\)的数量，求最终共有多少种可能的得分

解法

考虑反转一个区间，得分的变化之为这个区间原序列中\(0\)的数量减去\(1\)的数量.

我们假设原序列的得分为\(0\)，则得分的变化量就是是它的得分.

设最大值为\(MAX\)，最小值为\(MIN\)，则所有在这之间的数都是可取的.

时间复杂度\(O(N)\)，可以通过.