POJ 1745 Divisibility：模 K 餘數 DP 判定可整除

問題描述

給定 N (≤10000) 個整數序列，在每兩個數之間填 + 或 -，問能否使最終結果能被 K (≤100) 整除。輸出 Divisible 或 Not divisible。

狀態定義：餘數 DP

dp[i][r] 表示前 i 個數能否構成模 K 餘數為 r 的表達式。r ∈ [0, K-1]。轉移：

dp[i][(r + a[i]) % K] |= dp[i-1][r]
dp[i][(r - a[i] % K + K) % K] |= dp[i-1][r]

初始 dp[1][ (a[1]%K+K)%K ] = true。最終檢查 dp[N][0]。

優化與細節

• 只需滾動數組 dp[2][K]，空間 O(K)。
• 數值可能為負，取模時統一調整為非負：(x%K+K)%K。
• 只需判斷可行性（布爾值），無需計數，避免溢出。

參考代碼 (C++)

#include 
using namespace std;
bool dp[2][105];
int a[10005];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, K;
    while (cin >> N >> K) {
        for (int i = 1; i <= N; ++i) {
            cin >> a[i];
            a[i] = (a[i] % K + K) % K;
        }
        memset(dp, 0, sizeof(dp));
        dp[1][a[1]] = true;
        for (int i = 2; i <= N; ++i) {
            int cur = i & 1, pre = cur ^ 1;
            memset(dp[cur], 0, sizeof(dp[cur]));
            for (int r = 0; r < K; ++r) if (dp[pre][r]) {
                dp[cur][(r + a[i]) % K] = true;
                dp[cur][(r - a[i] + K) % K] = true;
            }
        }
        cout << (dp[N&1][0] ? "Divisible" : "Not divisible") << '\n';
    }
    return 0;
}

複雜度

時間 O(N * K) = 10⁶，空間 O(K) = 100，極快。

核心思想

• 將「符號選擇」轉化為「餘數狀態轉移」。
• 模運算將無限大的數值空間壓縮到有限的 K 個狀態。
• 典型的「枚舉狀態」DP 範式：dp[i][state] = OR over transitions from dp[i-1][prev_state]。