题解：P14973 『GTOI - 2D』木棍
CuteGielHina · · 题解
特以此题解纪念首次在 Div.2 场切 D。虽然没过 C 题。
Problem.
给定长度为
-
1 l r：翻转区间[l, r] 内的字符（0 变1 ，1 变0 ）； -
2 l r：查询区间[l, r] 组成的子串T 的价值V(T) \mod 998244353 。
具体定义：
Solution.
核心知识：组合数学 + 线段树。
一、核心性质推导：
要计算
-
-
$V(T) = \left( \binom{L}{d} - \binom{L}{d-1} \right) \mod 998244353 该式源于卡特兰数变形，本质是排除非法消去情况（可理解为“不跨越对角线”的路径计数修正）。
:::info[证明]{close}
-
前置性质：
-
消去“01”对后，剩余串
f(T) 必为1^a0^b 结构（a+b=k ）。 -
合法串需满足
L = k + 2d （d 为消去对数），否则V(T)=0 ，公式可自然适配该边界条件。
-
-
组合计数基础（总候选串数）:
合法串含
a+d 个1 、b+d 个0 （消去d 个1 和0 后，剩余a 个1 、b 个0 ）。总候选数为从L 个位置中选b+d 个位置放置 0 的组合数\binom{L}{d} ，因a+b=k ，两种选法数量等价。需注意，此计数包含消去后结构非1^a0^b 的非法串，需进一步剔除。 -
反射原理剔除非法串
非法串的核心特征的是消去过程中存在“
0 剩余数 >1 剩余数”的情况，导致最终结构不合法。通过反射变换构造双射：取首个出现该非法情况的位置，翻转该位置及前缀字符，变换后串的消去对数变为d-1 ，对应\binom{L}{d-1} 种选法。由于每个非法串与
\binom{L}{d-1} 中的串一一对应，故非法串总数为\binom{L}{d-1} )。 -
最终公式
合法串数量 = 总候选串数 - 非法串数，代入得
V(T) = \binom{L}{d} - \binom{L}{d-1} ，公式得证。 :::
二、代码实现：
-
因为模数
998244353 是质数，所以我们可以用费马小定理预处理阶乘与逆元阶乘，实现O(1) 计算\binom{n}{k} （太菜了，费马小定理不会证，大家可以看这篇）。 -
线段树维护区间信息：需要高效维护“区间消去 01 后的剩余 1 / 0 数量”，且支持区间翻转，因此设计线段树节点存储：
-
cnt1/cnt0：原区间剩余的1 /0 数量； -
r1/r0：区间翻转后剩余的1 /0 数量； -
flip：翻转延迟标记。
核心操作：节点合并（合并左右区间时消去跨区间的 01 对）、翻转标记下推、区间更新 / 查询。
-
各项操作复杂度：
-
预处理：
O(MAXN) ，MAXN=1\times10^6 ，可快速通过； -
建树：
O(n) ，线性遍历所有节点； -
单次操作：线段树更新与查询均为
O(\log n) 。
总复杂度大概是
贴个代码。