题解：P12840 [蓝桥杯 2025 国 A] OCR 校正

xhxxwcr · 2025-06-16 15:30:12 · 题解

笑死，被管理员认为是 AI 写的题解，美醉了哈。。。

第一次操作：选择位置 k（1 \leq k \leq 2023），将第 k 个 O 替换为 0。

后续操作：
对于每一个位置，我们分析他的两个区间以及其情况数：

左区间：从位置 1 到 k-1，长度为 L = k-1。那么，有 C_{2022}^{k-1} 中可能选在这个区间内，并且有靠左（离第一个 0 更近）和靠右（离 k 更近）两种情况，所以顺序数为 \max(2^{k - 2},1)。
右区间：从位置 k+1 到 2023，长度为 R = 2023 - k。那么，在不分配在左区间的所有情况里，顺序数为 2^{2022 - k}。

总方案数：对 k 求和：

S = \sum_{k=1}^{2023} f(k)

f(k) = C_{2022}^{k-1} \cdot g(L) \cdot g(R)

g(x) = \begin{cases} 1 & \text{if } x = 0 \\ 2^{x-1} & \text{if } x > 0 \end{cases}

公式化简:
通过组合数的基本性质（不会自己去学好吧，~自己推导不难~），总方案数简化为：

S = 2^{4042} + 2^{2021}

那就直接快速幂不就完事了

~不会吧不会吧，不会还有人不会快速幂吧？~
P1266，自己学去。