HDU 3450：Counting Sequences（計數序列，DP + 樹狀數組）

一、題目大意

給定序列 a[1..n] 和整數 d，求滿足相鄰元素差值不超過 d 的非空子序列個數，模 9901。

二、解題思路

DP 定義：dp[i] 表示以 a[i] 結尾的合法子序列數。
轉移：dp[i] = 1 + sum(dp[j]) (j < i 且 |a[j]-a[i]| ≤ d)。
直接 O(n^2) 會超時。觀察到求和區間為 [a[i]-d, a[i]+d]，且只涉及 j < i 的元素，符合樹狀數組（BIT）特性：單點更新、區間查詢。
步驟：
1. 離散化數值（排序去重映射到 1..m）。
2. 遍歷 i=1..n：
- 查詢 BIT 區間和得 sum，dp[i] = (sum + 1) % mod。
- 在 BIT 中 a[i] 位置加上 dp[i]。
3. 答案為所有 dp[i] 之和模 mod。

三、代碼實現（C++）

#include <cstdio>
#include <algorithm>
using namespace std;

const int MOD = 9901;
const int MAXN = 100010;
int n, d;
int a[MAXN], b[MAXN];
int dp[MAXN], bit[MAXN];

int sum(int x) {
    int ans = 0;
    while (x > 0) { ans = (ans + bit[x]) % MOD; x -= x & -x; }
    return ans;
}
void add(int x, int v) {
    while (x <= n) { bit[x] = (bit[x] + v) % MOD; x += x & -x; }
}

int main() {
    while (~scanf("%d%d", &n, &d)) {
        for (int i = 1; i <= n; ++i) {
            scanf("%d", &a[i]);
            b[i] = a[i];
        }
        sort(b+1, b+n+1);
        int m = unique(b+1, b+n+1) - b - 1; // 離散化後大小
        memset(bit, 0, sizeof(int)*(m+2));
        int ans = 0;
        for (int i = 1; i <= n; ++i) {
            int l = lower_bound(b+1, b+m+1, a[i]-d) - b;
            int r = upper_bound(b+1, b+m+1, a[i]+d) - b - 1;
            int pos = lower_bound(b+1, b+m+1, a[i]) - b;
            int s = (sum(r) - sum(l-1) + MOD) % MOD;
            dp[i] = (s + 1) % MOD;
            add(pos, dp[i]);
            ans = (ans + dp[i]) % MOD;
        }
        printf("%d\n", ans);
    }
    return 0;
}

四、複雜度分析

• 時間：O(n log n) (排序 + n 次 BIT 操作)
• 空間：O(n)

關鍵點：離散化處理大數值，BIT 維護區間和實現 DP 優化。