HDU 5439 Aggregated Counting：序列規律與二分查找求雙重末位置

HDU 5439 Aggregated Counting：序列規律與二分查找求雙重末位置

序列生成規則

1. 寫下 1, 2。
2. 第 2 個數是 2 → 再寫 2 個 2 → 1, 2, 2。
3. 第 3 個數是 2 → 再寫 2 個 3 → 1, 2, 2, 3, 3。
4. 第 4 個數是 3 → 再寫 3 個 4 → 1, 2, 2, 3, 3, 4, 4, 4。
以此類推：1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, ...

問題定義

設 f(n) 為數 n 在序列中最後一次出現的位置（1-indexed）。
例：f(3)=5, f(4)=8。
求 f(f(n))，即「最後位置的最後位置」。答案對 1,000,000,007 取模。

規律分析

觀察可得：
- f(n) = 序列前 n 項和。
- 數 k 在序列中出現次數 = f(k) - f(k-1) （令 f(0)=0）。
- 這正是「每個數 k 出現 f(k)-f(k-1) 次」的自指序列（Golomb-like）。

推導 f(f(n)) 計算公式：
f(f(n)) = Σ_i=1..n i × (f(i) - f(i-1))
但直接算 f(n) 需知道前 n 項和，循環定義。實際上可預計算 f 值直到超過 10⁹（n 最大值），利用 f(n) 遞增特性二分查找。

預計算策略

• `a[i]`：第 i 段結尾的數值（即 f(i) 位置處的數）。
• `b[i]`：數 i 出現的次數。
• `s[i]`：前 i 段的 f(f) 累積和（即 Σ j × b[j]）。

構造過程：
a[1]=1, a[2]=3, a[3]=5（對應 f(1)=1, f(2)=3, f(3)=5）
b[1]=1, b[2]=2, b[3]=2
s[1]=1, s[2]=11, s[3]=38
之後迭代：下一段數值 kk，長度 b[kk]，更新 a、b、s 直到 a[k-1] > 1e9。

查詢算法

給定 n，二分找到最大的 `mid` 使得 `a[mid-1] < n ≤ a[mid]`。
則 f(n) = f(a[mid-1]) + mid × (n - a[mid-1])。
f(f(n)) = s[mid-1] + mid × ( (a[mid-1]+1 + n) × (n - a[mid-1]) / 2 )。
取模 1e9+7 輸出。

參考代碼 (C++)

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

#define N 450010
const int MOD = 1000000007;
long long a[N]; // a[i] = f(i) 位置處的數值（段結尾值）
int b[N];       // b[i] = 數 i 出現次數
long long s[N]; // s[i] = 前 i 段 f(f) 累積和

int main() {
    a[1]=1; a[2]=3; a[3]=5;
    b[1]=1; b[2]=2; b[3]=2;
    s[1]=1; s[2]=11; s[3]=38;
    int k=4, pre=4, kk=3;
    while (a[k-1] <= 1e9) {
        for (k = pre; k < pre + b[kk]; k++) {
            a[k] = a[k-1] + kk;
            b[k] = kk;
            s[k] = (s[k-1] + (long long)kk * k) % MOD;
        }
        pre = k;
        kk++;
    }
    int T; scanf("%d", &T);
    while (T--) {
        long long n; scanf("%lld", &n);
        int l = 1, r = k-1, mid;
        while (l <= r) {
            mid = (l + r) >> 1;
            if (n <= a[mid-1]) r = mid - 1;
            else if (n > a[mid]) l = mid + 1;
            else break;
        }
        long long ans = (s[mid-1] + (long long)mid * ((a[mid-1] + 1 + n) * (n - a[mid-1]) / 2)) % MOD;
        printf("%lld\n", ans);
    }
    return 0;
}

複雜度

• 預計算：O(√n_max) ≈ 45000 步，極快。
• 單次查詢：O(log K) 二分，K≈45000。
• 空間：O(K)。