题意分析

题目描述了一个数字变换过程：初始序列为 "1"，每一步将序列中的每个 "0" 替换为 "10"，每个 "1" 替换为 "01"。需要计算经过 n 步变换后，序列中连续两个 0（即 "00"）的出现次数。

关键观察

1. 变换规则：
   • "0" → "10"
   • "1" → "01"
   • 每步变换使序列长度翻倍
2. "00"的出现规律：
   • "00" 只能由相邻的两个数字扩展后的边界形成
   • 当左侧数字是 "0" 且右侧数字是 "1" 时，在它们扩展后的边界会形成 "00"
3. 递推关系：
   • 设 a(n) 为第 n 步序列中 "00" 的对数
   • 初值：a(1) = 0，a(2) = 1
   • 递推式：a(n) = 2 × a(n-1) + (-1)^n

高精度处理原因

当 n 较大时（最大 1000），a(n) 的值可能达到 2^999 级别（约 300 位数字），远超标准整数范围，需要高精度计算。

解题思路

1. 预处理递推公式：

   a(1) = 0
   a(2) = 1
   a(n) = 2 * a(n-1) + (1 if n even else -1)  # n ≥ 3
   

2. 高精度实现：
   • 使用 10^8 进制（每个单元存储 8 位数字）
   • 预计算 a(2) 到 a(1000) 的值
3. 处理步骤：
   • 乘以 2：每位数字加倍
   • 奇偶修正：偶数加 1，奇数减 1
   • 进位/借位处理：确保每位数字在 [0, 10^8) 范围内
4. 输入输出：
   • 输入：多组测试数据，每行一个 n (1 ≤ n ≤ 1000)
   • 输出：a(n) 的高精度表示

示例解析

1. n=2：
   • 序列："1001"
   • "00" 出现位置：索引 1-2
   • 输出：1
2. n=3：
   • 序列："01101001"
   • "00" 出现位置：索引 5-6
   • 输出：1
3. n=4：
   • 序列：由 n=3 序列变换而来
   • 计算：a(4) = 2a(3) + 1 = 21 + 1 = 3
   • 输出：3

代码实现

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

#define UNIT 100000000 // 10^8进制
int a[1010][40]; // a[i][j]：第i步结果的第j个单元

int main() {
    memset(a, 0, sizeof(a));
    
    // 预处理：计算a(2)到a(1000)
    a[2][0] = 1; // a(2)=1
    for (int i = 3; i <= 1000; i++) {
        // 每位乘以2
        for (int j = 0; j < 40; j++) 
            a[i][j] = a[i-1][j] * 2;
        
        // 奇偶修正：偶数加1，奇数减1
        if (i & 1) {
            a[i][0]--; // 奇数减1
            // 借位处理
            for (int j = 0; j < 40; j++) {
                if (a[i][j] >= 0) break;
                a[i][j] += UNIT;
                a[i][j+1]--;
            }
        } else {
            a[i][0]++; // 偶数加1
        }
        
        // 进位处理
        for (int j = 0; j < 40; j++) {
            if (a[i][j] < UNIT) continue;
            a[i][j+1] += a[i][j] / UNIT;
            a[i][j] %= UNIT;
        }
    }

    // 处理输入
    int n;
    while (scanf("%d", &n) != EOF) {
        if (n == 1) {
            printf("0\n");
            continue;
        }
        
        // 查找最高非零位
        int j = 39;
        while (j >= 0 && a[n][j] == 0) j--;
        
        if (j < 0) {
            printf("0\n");
        } else {
            printf("%d", a[n][j--]); // 最高位无前导零
            while (j >= 0) 
                printf("%08d", a[n][j--]); // 后续位补零
            printf("\n");
        }
    }
    return 0;
}

复杂度分析

• 时间复杂度：预处理 O(1000*40) = O(40,000)，查询 O(1)
• 空间复杂度：O(1000*40) = O(40,000)