UVA 10479：找規律遞歸求序列第 n 項

題目簡介

序列生成規則：初始為 0。每一步將上一步的每個數字 x 替換為 x 個 0 後接 x+1。序列前幾項：0, 1, 0, 2, 1, 0, 0, 3, 0, 2, 1, 1, 0, 0, 0, 4... 求第 n 項（n < 2^63）。

規律分析

• 第 2^k 項一定是 k。
• 從第 2^k 項向前看：緊接 k-1 個 0，再前 k-2 個 1，再前 k-3 個序列 (0,2)，以此類推，直到長度為 1 的塊。
• 可將 n 定位到某個塊中，遞歸求解。

代碼實現

#include <cstdio>
#include <cmath>
#define ll unsigned long long
ll n, f[65];

void dfs(int r, ll cur, ll len) {
    if (cur >= len - (r - 1)) { puts("0"); return; }
    len -= (r - 1);
    for (int i = 1, j = r - 2; j > 0; i++, j--) {
        if (cur >= len - j * f[i-1]) {
            cur = (cur - (len - j * f[i-1])) % f[i-1] + 1;
            len = f[i-1];
            if (cur == len) printf("%d\n", i);
            else dfs(i, cur, len);
            return;
        }
        len -= j * f[i-1];
    }
}

int main() {
    f[0] = 1;
    for (int i = 1; i < 64; i++) f[i] = f[i-1] * 2;
    while (scanf("%llu", &n) == 1 && n) {
        int l = 0;
        for (int i = 0; i < 64; i++) if (n < f[i]) { l = i-1; break; }
        if (f[l] == n) printf("%d\n", l);
        else { int r = l + 1; dfs(r, n, f[r]); }
    }
    return 0;
}

複雜度分析

遞歸深度 ≤ 64，每層常數操作，時間 O(log n)，極快。