TLE问题求助：含通配符的01字符串总价值计算优化

你的递归枚举思路虽然直观，但当字符串中问号数量较多时，时间复杂度会达到O(2^k * n)（k为问号数），指数级增长必然导致超时。我们可以换个思路：计算每个相邻字符对在所有可能字符串中的总贡献，再将所有贡献相加，时间复杂度降为O(n)，完全避免超时。

核心逻辑 #

字符串的总价值是所有可能字符串中「连续不同字符对」的数量之和。我们可以把这个总和拆分成每个相邻位置(i, i+1)的贡献之和——每个位置的贡献等于该位置在所有可能替换中，两个字符不同的情况数。

具体来说：

1. 先统计字符串中问号的总数total_q，预计算2^total_q % MOD的幂次数组（MOD=10^9），用于快速计算剩余问号的组合数。
2. 对每个相邻字符对(left, right)：
   • 计算left为0/1的可能数，right为0/1的可能数（比如left是'?'则为0和1各1种可能，是'0'则仅0有1种可能）。
   • 计算该对字符不同的组合数：left0*right1 + left1*right0。
   • 乘以剩余问号的组合数（即2^(total_q - 当前对的问号数)），得到该位置的总贡献。
3. 将所有位置的贡献累加，最终结果取模10^9。

代码实现 #

MOD = 10**9

s = input().strip()
n = len(s)
if n < 2:
    print(0)
    exit()

# 统计总问号数
total_q = s.count('?')

# 预计算2的幂次，pow2[i] = 2^i mod MOD
pow2 = [1] * (total_q + 1)
for i in range(1, total_q + 1):
    pow2[i] = (pow2[i-1] * 2) % MOD

ans = 0
for i in range(n-1):
    left = s[i]
    right = s[i+1]
    
    # 计算left为0/1的可能数
    cnt_l0 = 1 if left in ('0', '?') else 0
    cnt_l1 = 1 if left in ('1', '?') else 0
    
    # 计算right为0/1的可能数
    cnt_r0 = 1 if right in ('0', '?') else 0
    cnt_r1 = 1 if right in ('1', '?') else 0
    
    # 不同组合的数量
    different = cnt_l0 * cnt_r1 + cnt_l1 * cnt_r0
    
    # 当前对的问号数
    curr_q = (1 if left == '?' else 0) + (1 if right == '?' else 0)
    
    # 该位置的总贡献
    contribution = (different * pow2[total_q - curr_q]) % MOD
    ans = (ans + contribution) % MOD

print(ans)

示例验证 #

比如输入字符串"??"：

• total_q=2，pow2[2]=4
• 相邻对的different=11 +11=2，curr_q=2，贡献=2pow2[0]=21=2
• 总结果为2，对应所有可能字符串的价值总和：00(0)+01(1)+10(1)+11(0)=2，正确。

内容的提问来源于stack exchange，提问作者99Orc