HDU 5587 Array：數列構造與前綴和遞歸求解

問題描述

初始數列 {1}。每次操作：複製當前數列接在尾部，中間插入一個 0，然後從該 0 開始（含 0）所有數字 +1。操作若干次後，求前 M 項和，M ≤ 10¹⁶。

規律發現

• 第 n 次操作後數列長度：len[n] = 2^n - 1。
• 第 n 次操作後數列和：sum[n] = 2·sum[n-1] + 2^{n-1}。
• 預計算 len[] 和 sum[] 陣列，長度只需 60 左右即覆蓋 10¹⁶。

遞歸查詢

給定 M，在 len[] 中二分找到最大 len[k] ≤ M。答案累加 sum[k]，剩餘長度 L = M - len[k]。根據構造規則，剩餘部分整體 +1（加 L），中間隔一個 0（遞歸處理 L-1）。遞歸終止條件：L==0 返回累加和；L==1 返回累加和 +1。

核心代碼

long long A[109], B[109]; // A: 前綴和, B: 長度
long long dfs(long long x) {
    if (x == 0) return 0;
    int b = upper_bound(B+1, B+63, x) - B - 1; // 找最大 B[b] ≤ x
    long long ans = A[b];
    long long L = x - B[b];
    if (L == 0) return ans;
    if (L == 1) return ans + 1;
    return ans + dfs(L - 1) + L; // +L 為整體+1, 遞歸處理 L-1
}

int main() {
    A[1] = 1; B[1] = 1;
    long long m = 1;
    for (int i = 2; i <= 100; ++i) {
        A[i] = A[i-1]*2 + 2*m;
        m *= 2;
        B[i] = 2*B[i-1] + 1;
    }
    int T; cin >> T;
    while (T--) {
        long long M; cin >> M;
        cout << dfs(M) << endl;
    }
}

複雜度

預計算 O(60)，單次查詢遞歸深度 O(log M)，極快。