题意理解

我们有一个无限长的 Thue-Morse 序列，定义：

• $T_0 = 0$
• $T_{2n} = T_n$
• $T_{2n+1} = 1 - T_n$

给定一个 01 字符串 $S$ 和整数 $k$，问有多少个 Thue-Morse 序列的连续子序列 $T$ 满足：

• $S$ 是 $T$ 的前缀
• $T$ 的长度 = $|S| + k$

---

核心难点

1. Thue-Morse 序列的结构特殊：具有自相似性
2. $k$ 极大：最大 $10^{18}$，需要对数算法
3. 需要高效判断和计数：哪些扩展是合法的连续子序列

---

关键观察：Thue-Morse 序列的性质

自相似性

Thue-Morse 序列可以递归生成：

• 从 $0$ 开始
• 每次替换：$0 \to 01$, $1 \to 10$

也就是说：

• 位置 $2n$ 和 $n$ 相同
• 位置 $2n+1$ 和 $n$ 相反

---

问题转化

我们有一个前缀 $S$，要在后面添加 $k$ 位，使得整个串是 Thue-Morse 序列的连续子序列。

关键思路：从某个起始位置 $p$ 开始，取长度为 $|S|+k$ 的子串，这个子串的前 $|S|$ 位等于 $S$。

---

递归求解框架

基础想法

设 $f(S, k)$ 表示以 $S$ 为前缀，后面添加 $k$ 位的方案数。

由于 Thue-Morse 序列的递归结构，我们可以将问题分解：

1. 如果 $S$ 能匹配序列中从偶数位置开始的一段：

   • 那么 $S$ 的每个字符 $S[i]$ 必须等于 $T_{2n+i} = T_{n + i/2}$（当 $i$ 为偶数时）
   • 这实际上要求 $S$ 的偶数位和奇数位分别满足某种关系

2. 更直接的方法：考虑 $S$ 在序列中的出现位置

---

关键性质：递推关系

通过分析 Thue-Morse 序列的结构，可以发现：

对于字符串 $S$ 和整数 $k$，$f(S, k)$ 满足：

• 基本情况：

  • 如果 $S$ 不是 Thue-Morse 序列的子序列：$f(S, k) = 0$
  • 如果 $k = 0$：检查 $S$ 本身是否是连续子序列

• 递归情况：

  • 如果 $S$ 以 $0$ 开头，考虑两种可能：
    • 从某个偶数位置开始：$f(S, k) = f(S', \lfloor k/2 \rfloor)$，其中 $S'$ 是 $S$ 的某种变换
    • 从某个奇数位置开始：类似处理
  • 实际上更精确的递推是：

---

核心递推式

设 $S$ 是当前模式，$k$ 是要添加的长度。

我们可以将 $S$ 按位分解，利用 Thue-Morse 序列的生成规则：

规则：$T_n$ 和 $T_{\lfloor n/2 \rfloor}$ 有关系：

• 如果 $n$ 是偶数：$T_n = T_{n/2}$
• 如果 $n$ 是奇数：$T_n = 1 - T_{\lfloor n/2 \rfloor}$

因此，如果我们知道 $S$ 匹配从位置 $p$ 开始的子串，那么：

• $S[0] = T_p$
• $S[1]$ 必须等于 $T_{p+1}$，而 $T_{p+1}$ 由 $T_{\lfloor (p+1)/2 \rfloor}$ 决定

---

实际算法：记忆化搜索

定义 $dp(S, k)$：

1. 边界情况：

   • 如果 $|S| = 1$ 且 $k = 0$：返回 1（只有 $S$ 本身）
   • 如果 $|S| = 1$ 且 $k > 0$：考虑两种扩展方式

2. 递归分解：

   • 将 $S$ 分成两部分：$S = A + B$，其中 $|A| = 1$ 或 $|A| = 2$
   • 检查 $A$ 是否是合法的 Thue-Morse 模式
   • 如果能匹配，问题转化为 $dp(B, \lfloor k/2 \rfloor)$ 等子问题

---

具体递推关系

经过推导，可以得到：

对于 $S$ 和 $k$，设：

• $S_0$ = $S$ 去掉第一个字符后，根据 $S[0]$ 的值可能需要对剩余字符取反
• $S_1$ = $S$ 去掉前两个字符后，根据前两个字符的值进行变换

那么：

$$f(S, k) = f(S_0, \lfloor k/2 \rfloor) + f(S_1, \lfloor (k-1)/2 \rfloor) $$

其中 $S_0$ 和 $S_1$ 是根据 Thue-Morse 生成规则得到的子问题。

---

处理大 $k$

由于 $k$ 可达 $10^{18}$，递归深度只有 $O(\log k)$，但 $S$ 的长度不超过 $100$。

我们可以用记忆化搜索：

• 状态：$(S, k)$
• 但 $k$ 很大，实际上我们只需要记录 $S$ 和递归深度

因为每次 $k$ 会除以 2，所以最多 $O(\log k)$ 层递归。

---

算法框架（伪代码）

map<pair<string, ll>, int> memo;

int solve(string S, ll k) {
    if (memo.count({S, k})) return memo[{S, k}];
    
    int n = S.length();
    
    // 边界情况
    if (n == 0) return 1;  // 空串可以任意扩展
    if (k == 0) return check(S) ? 1 : 0;  // 检查S本身是否合法
    
    // 递归分解
    int res = 0;
    
    // 情况1：匹配第一个字符
    string S0 = transform(S, 1);  // 根据Thue-Morse规则变换剩余字符串
    if (S0 != "INVALID") {
        res += solve(S0, k / 2);
    }
    
    // 情况2：匹配前两个字符  
    if (n >= 2) {
        string S1 = transform(S, 2);  // 根据前两个字符变换
        if (S1 != "INVALID") {
            res += solve(S1, (k - 1) / 2);
        }
    }
    
    return memo[{S, k}] = res % MOD;
}

---

复杂度分析

• 状态数：$O(|S| \cdot \log k)$
• 每个状态处理时间：$O(|S|)$
• 总复杂度：$O(T \cdot |S|^2 \cdot \log k)$，可以接受

---

总结

这道题的核心在于：

1. 理解 Thue-Morse 序列的递归结构
2. 将匹配问题分解为子问题：每次处理 1-2 个字符
3. 利用记忆化搜索处理大 $k$：递归深度只有对数级别
4. 设计正确的状态转移：根据序列生成规则变换剩余字符串

通过这种分解，我们就能在 $k$ 极大时高效求解。