E. 完美切割 题解

---

一、题意理解

给定一个由 0、1、? 组成的字符串 $s$。将每个 ? 独立替换为 0 或 1 后，得到一个二进制字符串。

一个二进制字符串是完美的，当且仅当存在一个切割位置，将字符串分为非空前缀 $a$ 和非空后缀 $b$，使得对于每个 $i$（从 $1$ 到 $\min(|a|, |b|)$），都有 $a_i \geq b_i$。

即前缀的每一位都不小于后缀对应位置的每一位。

目标是计算能生成完美字符串的替换方案总数，对 $998244353$ 取模。

---

二、完美字符串的充要条件

2.1 必要条件分析

逐位比较前缀 $a$ 和后缀 $b$，要求 $a_i \geq b_i$。由于字符只有 0 和 1，不等关系只能是 $1 \geq 0$、$1 \geq 1$ 或 $0 \geq 0$，绝不能出现 $0 \geq 1$（即前缀为 0 且后缀为 1）。

考虑切割位置。设前缀长度为 $p$，后缀长度为 $|s| - p$，其中 $1 \leq p \leq |s| - 1$。

2.2 分类讨论

情况一：$s$ 以 1 开头

若 $s_1 = 1$，取 $p = 1$，前缀为 "1"，后缀从 $s_2$ 开始。

比较时只需比较 $a_1 = 1$ 和 $b_1 = s_2$：

• 无论 $b_1$ 是 0 还是 1，都有 $1 \geq b_1$。

因此以 1 开头的任何二进制字符串都是完美的。

---

情况二：$s$ 以 0 开头

若 $s_1 = 0$，则切割位置 $p \geq 1$ 时，$a_1 = 0$。

必须保证 $a_1 \geq b_1$，即 $0 \geq b_1$，这要求 $b_1 = 0$。

因此后缀也必须以 0 开头，即字符串中必须存在第二个 0（位置 $> 1$）。

进一步，若存在第二个 0，可构造如下切割方案：

• 令前缀包含第一个 0 到第二个 0 之前的所有字符（即前缀形如 0111...1，以 0 开头、后接若干 1，最后一位是第二个 0 前的一个 1）；
• 后缀从第二个 0 开始。

比较时：

• 前缀的每一位要么是 0（第一位），要么是 1（其余位）；
• 后缀的第一位是 0，其余位任意。

由于前缀第一位是 0，后缀第一位也是 0，满足 $0 \geq 0$；前缀其余位都是 1，后缀对应位置无论是 0 还是 1 都有 $1 \geq 0$ 或 $1 \geq 1$。

因此该字符串是完美的。

---

情况三：唯一的 0 在开头

若 $s$ 以 0 开头，且后面所有字符都是 1（即形如 0111...1），则：

• 无论怎么切割，后缀必然以 1 开头（因为只有第一个字符是 0）；
• 但前缀第一位是 0，需要 $0 \geq b_1 = 1$，不可能满足。

因此形如 0111...1（一个 0 后全是 1）的字符串是不完美的。

---

2.3 充要条件总结

$$\boxed{ s \text{ 是完美的} \iff \begin{cases} s_1 = 1, & \text{或} \\[4pt] s_1 = 0 \ \text{且} \ \exists j > 1 \text{ 使得 } s_j = 0 \end{cases} } $$

等价地：不完美的字符串只有一种——以 0 开头且后面全为 1。

---

三、计数方法

设字符串总长度为 $n$，问号总数为 $q$。

方法：分类讨论第一个字符

情况一：第一个字符最终为 1

若 $s_1$ 为 1 或 ?（替换为 1），则无论其余位置如何，字符串必然完美。

此时：

• 第一个字符已被确定（若是 ? 则只有一种选择：变为 1）；
• 剩余 $n-1$ 个位置中的问号可以任意替换（每个 ? 有 $2$ 种选择）。

设除第一个字符外有 $q'$ 个问号，则方案数为：

$$2^{q'}$$

---

情况二：第一个字符最终为 0

若 $s_1$ 为 0 或 ?（替换为 0），则还需保证字符串不是 0111...1 的形式。

即除第一个字符外，不能全为 1。

• 若后面已经有一个确定的 0（非 ? 的 0），则无论如何替换 ?，字符串都不是 0111...1，方案数为 $2^{q'}$；
• 若后面没有确定的 0（即所有 ? 替换为 1 就会变成 0111...1），则需排除全替换为 1 的那一种方案，方案数为 $2^{q'} - 1$。

---

四、最终公式

设 $pw = 2^{q'}$，其中 $q'$ 为除第一个字符外的问号数量。

$$\boxed{ \text{ans} = \begin{cases} 0, & \text{若 } s_1 \text{ 确定为 } 0 \text{ 且后面无任何 } 0 \text{（此时无法形成完美字符串，但这种情况} \\[2pt] & \quad \text{已包含在情况二的公式中} \\[6pt] pw, & \text{若 } s_1 = 1 \\[4pt] pw, & \text{若 } s_1 = 0 \text{ 且 } \exists j > 1, s_j = 0 \text{（确定的 } 0 \text{）} \\[4pt] pw - 1, & \text{若 } s_1 = 0 \text{ 且 } \forall j > 1, s_j \neq 0 \text{（没有确定的 } 0 \text{）} \end{cases} } $$

用 $s_1$ 可能为 ? 的统一表达式：

令 pw 为除第一位外问号的任意替换方案数。

$$\text{ans} = \begin{cases} pw, & \text{若第一位取 } 1 \\[4pt] pw - (1 \text{ 如果后面没有确定的 } 0 \text{ 否则 } 0), & \text{若第一位取 } 0 \end{cases} $$

最终答案为两种情况之和（若第一位是 ?，两种情况都合法；若第一位确定，则只取对应情况）。

---

五、标程解析

const val MOD = 998244353;

fun main() = repeat(readln().toInt()) {
    val s = readln()
    // 计算 2^{q'}，q' 为除第一个字符外的问号数量
    var pw = 1
    repeat(s.drop(1).count { it == '?' }) {
        pw = pw * 2 % MOD
    }
    
    var ans = 0
    
    // 情况一：第一个字符为 1
    if (s[0] == '1' || s[0] == '?') {
        ans = (ans + pw) % MOD
    }
    
    // 情况二：第一个字符为 0
    if (s[0] == '0' || s[0] == '?') {
        // 检查后面是否有确定的 0
        val x = if (s.indexOf('0', 1) == -1) 1 else 0
        ans = (ans + pw - x) % MOD
    }
    
    println((ans + MOD) % MOD)
}

步骤解析：

1. 计算 $pw = 2^{q'}$，其中 $q'$ 是 s[1..n-1] 中 ? 的数量。
2. 若第一位可以是 1，累加 $pw$。
3. 若第一位可以是 0：
   • 在 s[1..n-1] 中查找是否有确定的 0。
   • 若无（indexOf('0', 1) == -1），则需排除全 1 的情况，累加 $pw - 1$；
   • 若有，累加 $pw$。
4. 输出答案（注意取模可能产生负数，加 MOD 再取模）。

---

六、样例验证

样例 1：$s =$ "0?1"

• $n = 3$，第一位后有两个字符：? 和 1，$q' = 1$，$pw = 2^1 = 2$。
• 第一位 0，可取 0。
• 后面有确定的 0 吗？s.indexOf('0', 1)：位置 $1$ 是 ?，位置 $2$ 是 1，没有确定的 0 → $x = 1$。
• 第一位取 0 的方案：$pw - x = 2 - 1 = 1$。
• 第一位取 1：$s[0]$ 为 0，无法取 1。
• 答案 $= 1$ ✅

样例 2：$s =$ "011"

• $q' = 0$，$pw = 1$。
• 第一位 0，可取 0。
• 后面有确定的 0 吗？位置 $1$ 是 1，位置 $2$ 是 1，没有 → $x = 1$。
• 答案 $= 1 - 1 = 0$ ✅

样例 3：$s =$ "????"

• $q' = 3$，$pw = 2^3 = 8$。
• 第一位 ?：可取 1（$+8$）或 0（后面无确定的 0，$+8-1=7$）。
• 答案 $= 8 + 7 = 15$ ✅

样例 4：$s =$ "110?0"

• $q'$：第一位后字符 "10?0" 中 ? 的数量 $= 1$，$pw = 2$。
• 第一位 1，可取 1：$+2$。
• 第一位不能取 0。
• 答案 $= 2$ ✅

样例 5：$s =$ "0?1?"

• $q'$：第一位后 "?1?" 中 ? 数量 $= 2$，$pw = 4$。
• 第一位 0，可取 0。后面有确定的 0 吗？位置 $1$ 是 ?，位置 $2$ 是 1，位置 $3$ 是 ?，没有 → $x = 1$。
• 第一位取 0 方案：$4 - 1 = 3$。
• 答案 $= 3$ ✅

---

七、代码实现（C++）

#include <bits/stdc++.h>
using namespace std;

const int MOD = 998244353;

void solve() {
    string s;
    cin >> s;
    int n = s.size();
    
    // 计算 2^{q'}，q' 为除第一个字符外的问号数
    long long pw = 1;
    for (int i = 1; i < n; i++) {
        if (s[i] == '?') {
            pw = pw * 2 % MOD;
        }
    }
    
    long long ans = 0;
    
    // 情况一：第一位为 1
    if (s[0] == '1' || s[0] == '?') {
        ans = (ans + pw) % MOD;
    }
    
    // 情况二：第一位为 0
    if (s[0] == '0' || s[0] == '?') {
        // 查找后面是否有确定的 0
        bool has_zero = false;
        for (int i = 1; i < n; i++) {
            if (s[i] == '0') {
                has_zero = true;
                break;
            }
        }
        int x = has_zero ? 0 : 1;
        ans = (ans + pw - x + MOD) % MOD;
    }
    
    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

---

八、复杂度分析

• 每个测试用例需遍历字符串一次（计算 $q'$ 和查找 0），时间复杂度 $O(n)$。
• 所有测试用例的字符串总长 $\leq 2 \times 10^5$，整体可行。
• 空间复杂度 $O(1)$ 额外空间。