HDU 5139 遞推公式離線處理：前綴乘積模 1e9+7 大數據範圍優化

題目大意

定義 f(n) = (∏_{i=1}^n (i+1)) % 1,000,000,007。多組查詢 n (≤ 10⁷)，輸出 f(n)。內存限制較小，無法直接打表存 10⁷ 個答案。

遞推關係推導

寫出前幾項：

f(1) = 2
f(2) = 2 * 3 = 6
f(3) = 6 * 4 = 24
f(4) = 24 * 5 = 120
...
f(n) = f(n-1) * (n+1) % MOD

設 sum = n+1 (下一個乘數)，則：

f[1] = 1; // 題目定義從 1 開始？實際樣例需核對
sum = 2;
for i = 2..N:
    f[i] = f[i-1] * sum % MOD;
    sum = sum * (i+1) % MOD;

離線處理技巧：排序查詢 + 線性推進

因無法存完整表，但查詢可離線：

1. 讀入所有查詢，記錄 (n, id)
2. 按 n 升序排序
3. 維護 cur_n、cur_f、cur_sum，從小到大推進計算
4. 對每個查詢，推進到其 n，記錄答案
5. 按原順序輸出

時間複雜度：O(max_n + Q log Q)，空間：O(Q)。

完整代碼

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1000000007;
const int MAXQ = 100005;

struct Query {
    int n, id;
    bool operator<(const Query& other) const { return n < other.n; }
} queries[MAXQ];

int ans[MAXQ];

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

    int n, cnt = 0;
    while (cin >> n) {
        queries[cnt++] = {n, cnt};
    }
    if (cnt == 0) return 0;

    sort(queries, queries + cnt);

    long long f = 1;   // f(1) = 1? 依題目實際定義
    long long sum = 1; // 累積乘數
    int cur = 1;       // 當前已計算到的 n

    for (int i = 0; i < cnt; ++i) {
        int target = queries[i].n;
        while (cur <= target) {
            f = f * sum % MOD;
            sum = sum * (cur + 1) % MOD;
            ++cur;
        }
        ans[queries[i].id] = f;
    }

    for (int i = 1; i <= cnt; ++i) {
        cout << ans[i] << '\n';
    }
    return 0;
}

關鍵點總結

遞推式驗證

題目給 f(n) = (∏_{i=1}^n (i+1)) % MOD = (n+1)! / 1! % MOD = (n+1)! % MOD。
代碼中 f = f * sum，sum = ∏_{j=1}^{cur} (j+1)？需仔細核對初始值。
實際樣例若無，建議按 f(1)=2, f(2)=6 調試初始 f=1, sum=2, cur=1：

cur=1: f=1*2=2, sum=2*2=4
cur=2: f=2*4=8? 應為 6。說明遞推式需修正。

正確遞推：f(n) = f(n-1) * (n+1)，f(1)=2。
即 sum 直接取 n+1，無需累積：

f = 2; // f(1)
for (int i = 2; i <= target; ++i) {
    f = f * (i + 1) % MOD;
}

修正後核心循環

long long f = 1; // f(0) = 1 (空積)
int cur = 0;
for (int i = 0; i < cnt; ++i) {
    int target = queries[i].n;
    while (cur < target) {
        ++cur;
        f = f * (cur + 1) % MOD; // 乘以 (cur+1)
    }
    ans[queries[i].id] = f;
}

總結

本題核心是離線查詢 + 線性遞推，將 O(Q × max_n) 降為 O(max_n + Q log Q)。關鍵在於識別遞推關係、正確處理初始值、利用排序將隨機訪問轉為順序計算。此技巧廣泛適用於「大範圍、可遞推、查詢離線」的問題。