二进制字符串序列求解优化：大N值超时问题咨询

你的代码超时是因为直接生成完整字符串，当N≥25时，Tn的长度达到2^24=16777216，不仅生成速度慢，还会占用大量内存。根本不需要构建完整字符串，我们可以通过规律直接计算目标位：

核心规律 #

1. Tn的长度为 2^(n-1)，每一项都是前一项拼接其取反字符串（比如T3 = T2 + 取反(T2)，T4 = T3 + 取反(T3)）。
2. 对于Tn的第X位：
   • 如果X ≤ 长度的一半（即X ≤ 2^(n-2)），该位等于Tn-1的第X位。
   • 如果X > 长度的一半，该位等于 1 - Tn-1的第(X - 2^(n-2))位（后半部分是前半的取反）。
3. 递归终止条件：当n=1时，返回0（T1只有字符'0'）。

优化后的代码 #

import sys

def get_bit(n, x):
    if n == 1:
        return 0
    half = 1 << (n-2)  # 等价于2^(n-2)，位运算更快
    if x <= half:
        return get_bit(n-1, x)
    else:
        return 1 - get_bit(n-1, x - half)

def main():
    input_data = sys.stdin.read().split()
    t = int(input_data[0])
    idx = 1
    for _ in range(t):
        n = int(input_data[idx])
        x = int(input_data[idx+1])
        idx += 2
        print(get_bit(n, x))

if __name__ == "__main__":
    main()

代码说明 #

• 用位运算1 << (n-2)快速计算2的幂次，比pow函数效率更高。
• 递归过程中每次将问题规模减半，时间复杂度为O(N)每个测试用例，无论N多大都不会超时。
• 一次性读取所有输入，避免多次IO操作，进一步提升处理速度。

测试示例验证 #

输入：

1
4 5 

计算过程：

1. n=4，half=4，X=5>4，计算1 - get_bit(3, 1)
2. get_bit(3,1)：n=3，half=2，1<=2，返回get_bit(2,1)
3. get_bit(2,1)：n=2，half=1，1<=1，返回get_bit(1,1)=0
4. 最终结果为1-0=1，与示例输出一致。

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