TopCoder SRM 632 Div2 題解：250/500/1000 全解析與 C++ 代碼

250 分：RunningAroundPark - 圈數計算

題意：給定跑道標記點序列 d，每次經過標記點記錄距離。當距離不增時視為完成一圈。求總圈數。

邏輯：遍歷數組，維護 last，若 d[i] <= last 則 ans++。

class RunningAroundPark {
public:
    int numberOfLap(int N, vector d) {
        int ans = 1, last = -1;
        for (int x : d) {
            if (x <= last) ++ans;
            last = x;
        }
        return ans;
    }
};

500 分：PotentialGeometricSequence - 等差子序列計數

題意：求數組中連續等差子序列個數（長度 ≥ 2）。等差定義：相鄰差值恆定。

規律：長度為 L 的等差段包含 (L+1)*L/2 - 1 個合法子序列（減去長度 1 的）。遍歷維護當前等差段長度 last，差值變化時結算。

class PotentialGeometricSequence {
public:
    int numberOfSubsequences(vector d) {
        int n = d.size();
        if (n == 1) return 1;
        long long ans = 0, last = 1, slope = d[1] - d[0];
        for (int i = 2; i < n; ++i) {
            int ns = d[i] - d[i-1];
            if (ns == slope) { ++last; }
            else {
                ++last;
                ans += (last + 1) * last / 2 - (ans ? 1 : 0);
                last = 1; slope = ns;
            }
        }
        ++last;
        ans += (last + 1) * last / 2 - (ans ? 1 : 0);
        return ans;
    }
};

1000 分：GoodSubset - 背包 DP 求子集乘積

題意：給定目標值 goodValue 和數組 d，求乘積恰好為 goodValue 的非空子集數量，模 1e9+7。

轉換：只考慮能整除 goodValue 的元素。狀態 dp[v] 表示乘積為 v 的方案數。逆序遍歷數組，對每個 x 更新所有因子狀態。

class GoodSubset {
    const long long MOD = 1000000007LL;
public:
    int numberOfSubsets(int goodValue, vector d) {
        unordered_map mp;
        mp[1] = 1;
        for (int x : d) {
            if (goodValue % x) continue;
            auto snapshot = mp; // 避免同輪疊加
            for (auto [val, cnt] : snapshot) {
                long long nv = val * x;
                if (goodValue % nv == 0) {
                    mp[nv] = (mp[nv] + cnt) % MOD;
                }
            }
        }
        mp[1] = (mp[1] - 1 + MOD) % MOD; // 排除空集
        return mp[goodValue];
    }
};

總結

SRM 632 Div2 三道題分別考察：簡單模擬、等差段組合計數、因子背包 DP。關鍵在於抽象出正確數學模型並處理邊界（空集、重複計數）。