HDU 1041 Computer Transformation：找規律與大數運算求連續零對數

HDU 1041 Computer Transformation：找規律與大數運算求連續零對數

問題描述

初始序列 `1`。每步同時轉換：`0 → 1 0`，`1 → 0 1`。
第 1 步：`0 1`
第 2 步：`1 0 0 1`
第 3 步：`0 1 1 0 1 0 0 1`
求 n 步後序列中 連續兩個 0 的對數。n ≤ 1000，結果超大需大數處理。

規律推導

設：

• a[n]：第 n 步 1 的個數
• b[n]：第 n 步 `00` 對數
• c[n]：第 n 步 `01` 對數

觀察轉換規律：

• `00` 只能由 `01` 產生：`01 → 1001 → 00`
• `01` 由 `1` 和 `00` 產生：`1 → 01`，`00 → 1010 → 01`
• 每步 0 和 1 各產生一個 1 → a[n+1] = 2^n

遞推關係：

b[n+1] = c[n]
c[n+1] = a[n] + b[n]
→ b[n] = c[n-1] = a[n-2] + b[n-2] = 2^(n-3) + b[n-2]

進一步簡化得：b[n] = 2*b[n-2] + b[n-1]（n ≥ 3）

大數實現

用二維數組 s[n][digit] 存儲大數，每位存 5 位十進制（模 100000）。預計算 2 的冪數組 p[]。

完整 AC 代碼

#include <stdio.h>
#define max 1010
int s[max][max/2] = {{0},{0},{1},{1}};
int p[max] = {1};

void calculate() {
    for (int i = 4; i < max-1; i++) {
        // 計算 2^(i-1) 存入 p[]
        for (int c=0, j=0; j<=300; j++) {
            p[j] = p[j]*2 + c;
            c = p[j]/10; p[j] %= 10;
        }
        // b[i] = 2^(i-3) + b[i-2] （即 p[] + s[i-2][]）
        for (int c=0, j=0; j<=300; j++) {
            s[i][j] = p[j] + s[i-2][j] + c;
            c = s[i][j]/10; s[i][j] %= 10;
        }
    }
}

int main() {
    int n;
    calculate();
    while (~scanf("%d", &n)) {
        if (n == 1) { printf("0\n"); continue; }
        int flag = 0;
        for (int i = 300; i >= 0; i--) {
            if (s[n][i] || flag) { printf("%d", s[n][i]); flag = 1; }
        }
        printf("\n");
    }
    return 0;
}

Sample I/O

Input:  2 3
Output: 1 1

n=2 序列 `1001` 有 1 對 `00`；n=3 序列 `01101001` 有 1 對 `00`。