HDU 5288 OO's Sequence 詳細解析與代碼實現

題目大意

給定 n 個數，對於每個區間 [l, r]，統計區間內「不能被該區間其他任意數整除」的數的個數 f(l, r)。求所有區間的 f(l, r) 之和，模 1e9+7。

解題關鍵

對於每個位置 i，找出其能成為「非倍數元素」的最大區間 [l[i], r[i]]。則包含 i 且使 a[i] 滿足條件的區間數為 (i - l[i] + 1) * (r[i] - i + 1)。總答案為所有 i 的此值之和。

求邊界的方法

• 右邊界 r[i]：正向遍歷。維護 pre[v] 為值 v 最後出現的位置。對於 a[i]，枚舉其倍數 j，若 pre[j] 存在且 r[pre[j]] 仍為初始值 n，則更新 r[pre[j]] = i - 1。最後設 pre[a[i]] = i。
• 左邊界 l[i]：反向遍歷。維護 last[v]，邏輯對稱：枚舉倍數 j，若 last[j] 存在且 l[last[j]] == 1，則 l[last[j]] = i + 1。設 last[a[i]] = i。

完整代碼 (C++)

#include <cstdio>
#include <cstring>
using namespace std;
const int mod = 1e9+7;
#define ll long long
#define N 111111
ll l[N], r[N];
int pre[N], last[N], a[N];

int main() {
    int n;
    while (scanf("%d", &n) == 1) {
        for (int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            l[i] = 1; r[i] = n;
        }
        memset(pre, 0, sizeof(pre));
        memset(last, 0, sizeof(last));
        for (int i = 1; i <= n; i++) {
            for (int j = a[i]; j <= 10000; j += a[i])
                if (pre[j] != 0 && r[pre[j]] == n)
                    r[pre[j]] = i - 1;
            pre[a[i]] = i;
        }
        for (int i = n; i > 0; i--) {
            for (int j = a[i]; j <= 10000; j += a[i])
                if (last[j] != 0 && l[last[j]] == 1)
                    l[last[j]] = i + 1;
            last[a[i]] = i;
        }
        ll ans = 0;
        for (int i = 1; i <= n; i++)
            ans = (ans % mod + (ll)(i - l[i] + 1) * (r[i] - i + 1) % mod) % mod;
        printf("%lld\n", ans);
    }
    return 0;
}

複雜度與優化

倍數枚舉上限為 10000，總操作數約 10000 * H_10000 ≈ 10^5，極快。空間 O(n + MAX_A)。