专栏文章

题解：CF2077C Binary Subsequence Value Sum

wwishapig许愿中
CF2077C题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mipw7oe0
此快照首次捕获于
2025/12/03 18:57
3 个月前
此快照最后确认于
2025/12/03 18:57
3 个月前
查看原文

题目大意

对一个 0,10,1 串 vv，记
f(v)=max⁡i=0∣v∣{F(v,1,i)×F(v,i+1,∣v∣)}F(v,l,r)=r−l+1−2×zero(v,l,r)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)
给出一个长为 nn 的 0,10,1 串 ss，支持：
  • 将一个位置 0/10/1 翻转
  • 求出 ss 所有子序列的 ff 值之和，输出答案对 998244353998244353 取模的结果
1≤T≤104,1≤n,q,∑n,∑q≤2×1051\le T\le 10^4,1\le n,q,\sum n,\sum q\le 2\times 10^5
显然这个 FF 代表的就是区间内 11 个数减去 00 个数，因此可以前缀和，用 pr−pl−1p_r-p_{l-1} 来表示
那么来看一下一个长度为 nn 的字符串如何求出其 ff 值：
f(v)=max⁡i=1n−1{(pi−p0)(pn−pi)}=max⁡i=1n−1{−pi2+pnpi}\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}
这个二次函数的最大值在对称轴 pn2\dfrac{p_n}{2} 处取到，而这不一定是整数，因此还要分情况讨论一下：
  • 若 pnp_n 为偶数，那么对称轴位置为整数，可以发现，由于 ∣pi−pi−1∣=1|p_i-p_{i-1}|=1，因此在 1∼n1\sim n 中一定有一个 pi=pn2p_i=\dfrac{p_n}{2}，于是 f(v)=pn24f(v)=\dfrac{p_n^2}{4}
  • 若 pnp_n 为奇数，那么最优位置应当为 pn−12\dfrac{p_n-1}{2}，与上面的分析相同，一定存在一个 pip_i 可以取到这个位置，此时有 f(v)=pn2−14=pn24−14f(v)=\dfrac{p_n^2-1}{4}=\dfrac{p_n^2}{4}-\dfrac{1}{4}
发现 pn24\dfrac{p_n^2}{4} 这个部分是相同的，于是可以对所有子序列求出 pn24\dfrac{p_n^2}{4}，再求出所有 pnp_n 为奇数的子序列个数 cc，减去 c4\dfrac{c}{4} 即可
同时容易发现 pnp_n 的奇偶性与 nn 相同，因此 c=(n1)+(n3)+(n5)+⋯c=\binom{n}{1}+\binom{n}{3}+\binom{n}{5}+\cdots
于是问题就变成了求前面这个部分
由于有单点修改，因此考虑使用数据结构进行维护，可以使用线段树，每个节点维护区间长度 ll，区间内所有子序列的 s1=∑p,s2=∑p2s_1=\sum p,s_2=\sum p^2 即可
合并与修改都是容易的
CPP
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

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...