CF2077C Binary Subsequence Value Sum

原题链接
首先注意到 \(F(v, l, r)\) 其实就是 \(l \sim r\) 中 \(1\) 的数量减去 \(0\) 的数量。

接着考虑令 \(S = F(v, 1, n) = F(v, 1, i) + F(v, i + 1, n)\)，那么 \(F(v, 1, i) \times F(v, i + 1, n)\) 的最大值就是 \(\lfloor \frac{S}{2} \rfloor \lceil \frac{S}{2} \rceil\)。

这种形式不好处理，可以分 \(S\) 的奇偶性讨论。当 \(S\) 为奇数时就是 \(\frac{(S + 1)(S - 1)}{4}\)，即 \(\frac{S^2 - 1}{4}\)；当 \(S\) 为偶数时就是 \(\frac{S^2}{4}\)。所以我们可以把最大值记作 \(\frac{S^2 - S \bmod 2}{4}\)。

接下来要计算所有子序列的分数和（下文为了方便先不除以 \(4\)），可以发现对于所有长度为奇数的串都减一，一共要剪掉 \(2^{n - 1}\)。然后我们只需要算 \(\sum S^2\) 即可。

记 \(cnt_0\) 为一个子序列中 \(0\) 的数量，\(cnt_1\) 为一个子序列中 \(1\) 的数量，则 \(\sum S^2 = \sum(cnt_1 - cnt_0)^2 = \sum(cnt_0^2 + cnt_1 ^2 - 2cnt_0cnt_1)\)。

为了计算上面的式子，我们可以分别求出 \(\sum cnt_0^2、\sum cnt_1^2、\sum cnt_0cnt_1\)。

下文记 \(s_0\) 为整个序列中 \(0\) 的数量，\(s_1\) 同理。

先考虑 \(\sum cnt_0^2\)。为 \(1\) 的位可以任意取，然后枚举选多少个 \(0\)，答案是 \(2^{s_1}\sum_{i = 0}^{s_0} C_{s_0}^{i} \times i^2\)。

循环跑组合数显然烂完了，但是有一个组合数公式是 \(\sum_{i = 0}^{n}C_{n}^{i}i^2 = n(n+1)2^{n - 2}\)。原理是 \(i^2\) 可以看作 \(i(i - 1) + i\)，也就是 \(2C_{i}^{2} + C_{i}^{1}\)，那么原式就是 \(2\sum_{i = 0}^{n}C_{n}^{i}C_{i}^{2} + \sum_{i = 0}^{n}C_{n}^{i}C_{i}^{1}\)。对于右边的式子，是从 \(n\) 个数中选 \(i\) 个再从 \(i\) 个数中选 \(1\) 个，可以看作先选 \(1\) 个，再从剩下 \(n - 1\) 个中随便选，所以是 \(n\times 2^{n - 1}\)。左边的式子同理是 \(n(n-1)\times 2^{n - 2}\)，二者相加就得到了上述公式。

所以 \(\sum cnt_0^2 = 2^{s_1}s_0(s_0 + 1)2^{s_0 - 2} = s_0(s_0 + 1)2^{n - 2}\)，\(\sum cnt_1^2\) 同理可得等于 \(s_1(s_1 + 1)2^{n - 2}\)。

接着考虑 \(\sum cnt_0cnt_1\)，思考过程与上述类似，应该是 \(\sum_{i = 0}^{s_0} \sum_{j = 0}^{s_1}C_{s_0}^{i}C_{s_1}^{j} \times ij = \sum_{i = 0}^{s_0} C_{s_0}^{i} \times i \times (\sum_{j = 0}^{s_1} C_{s_1}^{j} \times j)\)。

公式的推导过程中我们其实也得到了 \(\sum_{i = 0}^{n}C_{n}^{i}i = n\times 2^{n - 1}\)，代入原式就是 \(s_0s_1 2^{n - 2}\)。

综上，\(\sum S^2 = s_0(s_0 + 1)2^{n - 2} + s_1(s_1 + 1)2^{n - 2} - s_0s_1 2^{n - 1}\)。

所以答案就是 \(\frac{\sum S^2 - 2^{n - 1}}{4} = \frac{2^{n - 2}[(s_0 - s_1) ^2 + s_0 + s_1 - 2]}{4}\)。我们动态维护 \(s_0\) 和 \(s_1\) 然后直接代入公式就做完了。