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
5. 以此類推

定義 f(n) = 數字 n 在序列中**最後一次出現的位置**。
求 f(f(n)) mod 1,000,000,007。

規律分析

設序列為 a[1], a[2], ...

• f(n) 即前 n 項和：f(n) = Σ_{i=1}^n a[i]
• 因為數字 i 出現 a[i] 次，最後出現位置 = 所有 ≤i 的數的出現次數之和

序列結構：

值:  1  2  2  3  3  4  4  4  5  5  5  6  6  6  6 ...
出現次數: 1  2  2  3  3  4  4  4  5  5  5  6  6  6  6 ...

觀察出現次數本身就是原序列！即 a[i] = 數字 i 的出現次數。

前綴和陣列構建

定義：

• a[k]：第 k 組結尾的數字值
• b[k]：數字 k 的出現次數（即 a[k]）
• s[k]：前 k 組的位置總和（即 f(a[k])）

遞推構建：

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;

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] + kk * (a[k-1] + 1 + a[k]) / 2; // 等差數列求和
    }
    pre = k;
    kk++;
}

查詢 f(f(n))

1. 二分查找 n 所在組：找最大 mid 使 a[mid-1] < n ≤ a[mid]
2. 該組數字值 = mid，組內偏移 = n - a[mid-1]
3. f(n) = s[mid-1] + mid * (首項 + 末項) * 項數 / 2 = s[mid-1] + mid * (a[mid-1]+1 + n) * (n - a[mid-1]) / 2
4. 對結果取模 1e9+7

完整程式碼

#include 
using namespace std;

const int N = 450010;
const long long MOD = 1000000007LL;

long long a[N]; // 組結尾值
int b[N];       // 組內數字出現次數
long long s[N]; // 組前綴和

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // 初始化
    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;
            long long cnt = a[k] - a[k-1];
            long long first = a[k-1] + 1;
            long long last = a[k];
            s[k] = (s[k-1] + kk * (first + last) / 2 * cnt) % MOD;
        }
        pre = k;
        kk++;
    }
    int maxK = k-1;

    int T; cin >> T;
    while (T--) {
        long long n; cin >> n;
        // 二分查找 n 所在組
        int l = 1, r = maxK, mid;
        while (l <= r) {
            mid = (l + r) >> 1;
            if (n > a[mid]) l = mid + 1;
            else if (n <= a[mid-1]) r = mid - 1;
            else break;
        }
        // mid 為目標組
        long long cnt = n - a[mid-1];
        long long first = a[mid-1] + 1;
        long long sum = (s[mid-1] + mid * (first + n) / 2 * cnt) % MOD;
        cout << sum << '\n';
    }
    return 0;
}

關鍵公式推導

第 mid 組對應數字值 mid，包含數字 a[mid-1]+1 ... a[mid]，每個出現 mid 次。
前 mid-1 組總位置和 = s[mid-1]。
第 mid 組中，前 cnt = n - a[mid-1] 個數字的位置和：
mid * Σ_{x = a[mid-1]+1}^n x = mid * (first + n) * cnt / 2

複雜度

• 預處理：O(K)，K ≈ 45000（因 a[K] ~ K²/2 > 1e9）
• 單次查詢：O(log K)
• 空間：O(K)

易錯點

1. 模運算順序：除法 /2 需在取模前進行，或用模逆元（此處數值較小可先算再模）
2. 二分邊界：找 a[mid-1] < n ≤ a[mid]，注意 a[0] 未定義，l 從 1 開始
3. long long：中間乘積超 1e18 需 __int128 或分步取模

總結

本題核心是發現序列的「自我描述」特性：a[i] 既是數字值也是出現次數。構建分組前綴和陣列，將查詢轉化為二分 + 等差數列求和。預處理 O(√n)，查詢 O(log n)，極其高效。