import{_ as i,c as a,a as n,o as t}from"./app-CyezZKiD.js";const e={};function l(p,s){return t(),a("div",null,[...s[0]||(s[0]=[n(`子序列是从原字符串中选择任意数量的字符（可以是 0 个、1 个、...、所有字符），且保持这些字符的原始顺序形成的字符串。
例如：原字符串 "abc" 的子序列包括 "a", "b", "c", "ab", "ac", "bc", "abc" 和空字符串 ""（共 23=8 种可能性）。
假设字符串长度为 n，我们可以用一个 n 位的二进制数来表示是否选择某个字符：
- 二进制数的每一位对应原字符串的一个字符。
- 如果某一位是
1，表示选择对应的字符；如果是 0，表示不选择。
例如，对于字符串 "abc"（n=3）：
| 二进制数 | 十进制 | 选择情况 | 生成子序列 |
|---|
101 | 5 | 选择第 1 个字符 "a" 和第 3 个字符 "c" | "ac" |
010 | 2 | 选择第 2 个字符 "b" | "b" |
所有可能的二进制数范围是 0（全 0）到 2n−1（全 1）。例如，n=3 时：
- 范围是
000 (0) 到 111 (7)，共 23=8 种可能。 - 每个二进制数对应一种子序列选择方式。
- 如果包含
000 (0)，对应空字符串 ""。若不需要空字符串，可以从 1 开始遍历。
对于 n=3，遍历 1 (001) 到 7 (111)。
- 对于每个二进制数
mask，遍历其每一位 i（从 0 到 n-1）。 - 如果
mask 的第 i 位是 1（即 mask & (1 << i) 为真），则将原字符串的第 i 个字符加入子序列。
def get_all_subsequences(s):
n = len(s)
subsequences = []
# 遍历 1 到 2^n - 1 (排除空字符串)
for mask in range(1, 1 << n):
subseq = []
for i in range(n):
# 检查 mask 的第 i 位是否为 1
if mask & (1 << i):
subseq.append(s[i])
subsequences.append(''.join(subseq))
return subsequences
# 测试
print(get_all_subsequences("abc"))
# 输出: ['a', 'b', 'ab', 'c', 'ac', 'bc', 'abc']
在处理类似 X 质数 的问题时，我们需要检查一个数字的所有数字子序列。通过这种位运算的方式，可以非常高效地生成所有组合并进行判断。
def solve_x_prime(num):
s = str(num)
n = len(s)
for mask in range(1, 1 << n):
subseq_str = ""
for i in range(n):
if mask & (1 << i):
subseq_str += s[i]
# 将生成的子序列转换为整数并判断是否为质数
p = int(subseq_str)
if is_prime(p):
return True
return False