题解：CF2077C Binary Subsequence Value Sum

wishapig · 2025-03-17 13:09:20 · 题解

题目大意

对一个 0,1 串 v，记

f(v)=\max_{i=0}^{|v|}\{F(v,1,i)\times F(v,i+1,|v|)\}\\ F(v,l,r)=r-l+1-2\times zero(v,l,r)

给出一个长为 n 的 0,1 串 s，支持：

将一个位置 0/1 翻转
求出 s 所有子序列的 f 值之和，输出答案对 998244353 取模的结果

1\le T\le 10^4,1\le n,q,\sum n,\sum q\le 2\times 10^5

显然这个 F 代表的就是区间内 1 个数减去 0 个数，因此可以前缀和，用 p_r-p_{l-1} 来表示

那么来看一下一个长度为 n 的字符串如何求出其 f 值：

\begin{aligned} f(v)&=\max_{i=1}^{n-1}\{(p_i-p_0)(p_n-p_i)\}\\ &=\max_{i=1}^{n-1}\{-p_i^2+p_np_i\} \end{aligned}

这个二次函数的最大值在对称轴 \dfrac{p_n}{2} 处取到，而这不一定是整数，因此还要分情况讨论一下：

若 p_n 为偶数，那么对称轴位置为整数，可以发现，由于 |p_i-p_{i-1}|=1，因此在 1\sim n 中一定有一个 p_i=\dfrac{p_n}{2}，于是 f(v)=\dfrac{p_n^2}{4}
若 p_n 为奇数，那么最优位置应当为 \dfrac{p_n-1}{2}，与上面的分析相同，一定存在一个 p_i 可以取到这个位置，此时有 f(v)=\dfrac{p_n^2-1}{4}=\dfrac{p_n^2}{4}-\dfrac{1}{4}

发现 \dfrac{p_n^2}{4} 这个部分是相同的，于是可以对所有子序列求出 \dfrac{p_n^2}{4}，再求出所有 p_n 为奇数的子序列个数 c，减去 \dfrac{c}{4} 即可

同时容易发现 p_n 的奇偶性与 n 相同，因此 c=\binom{n}{1}+\binom{n}{3}+\binom{n}{5}+\cdots

于是问题就变成了求前面这个部分

由于有单点修改，因此考虑使用数据结构进行维护，可以使用线段树，每个节点维护区间长度 l，区间内所有子序列的 s_1=\sum p,s_2=\sum p^2 即可

合并与修改都是容易的

struct dat{
    int len;
    int ans1,ans2;
} tr[N<<2];
dat operator + (const dat& a, const dat& b){
    return {a.len+b.len,
            (a.ans1+b.ans1+1ll*a.ans1*pw[b.len]+1ll*b.ans1*pw[a.len])%mod,
            (a.ans2+b.ans2+1ll*a.ans2*pw[b.len]+2ll*a.ans1*b.ans1+1ll*b.ans2*pw[a.len])%mod};
}
//pw[i]=2^i-1