HDU 5086 Revenge of Segment Tree - 數論公式計算所有子段和

問題描述

給定長度 n (n ≤ 10⁶) 的數組 a[1..n]。求所有連續子段和的總和模 1e9+7。即計算：
Σ_{1≤i≤j≤n} (a[i] + a[i+1] + ... + a[j])

數學推導

元素 a[i] 出現在多少個子段中？
左端點可選 1..i (共 i 種)，右端點可選 i..n (共 n-i+1 種)。
故 a[i] 被加 i * (n - i + 1) 次。
總和 = Σ_{i=1}^n a[i] * i * (n - i + 1)。

模運算注意

模 MOD = 1,000,000,007。中間乘積 a[i] * i * (n-i+1) 可能超過 64 位 (a[i] 可能大)。需用 int64 分步取模：

ans = (ans + (a[i] % MOD) * i % MOD * (n - i + 1) % MOD) % MOD;

參考代碼

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
const int MAXN = 1000005;

ll a[MAXN];

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int n; scanf("%d", &n);
        for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
        ll ans = 0;
        for (int i = 1; i <= n; i++) {
            ll term = a[i] % MOD;
            term = term * i % MOD;
            term = term * (n - i + 1) % MOD;
            ans = (ans + term) % MOD;
        }
        printf("%lld\n", ans);
    }
    return 0;
}

複雜度

• 時間 O(n) 每測試案例，n=10⁶ 極快。
• 空間 O(n) 存數組。
• 無需線段樹，純數學公式 O(1) 每元素。

題目名稱誤導

標題含 "Segment Tree" 實為誤導，實際為簡單數學題。類似 HDU 5086、HDU 5089 等 "Revenge of Segment Tree" 系列常考察數學洞察而非數據結構。