POJ 1745 Divisibility：線性 DP 判斷加減號組合能否被 K 整除

題目大意

給 n (≤ 10000) 個整數，在其間填 + 或 -，使表達式結果能被 k (≤ 100) 整除。輸出 "Divisible" 或 "Not divisible"。

DP 狀態定義

`dp[i][j]` = 前 i 個數能否構造出模 k 餘 j 的值。i=1..n, j=0..k-1。
初始：`dp[1][(a[1]%k+k)%k] = true`。
轉移：對第 i 個數 `x = (a[i]%k+k)%k`，
`dp[i][(j+x)%k] |= dp[i-1][j]` (加)
`dp[i][(j-x+k)%k] |= dp[i-1][j]` (減)
答案：`dp[n][0]`。

空間優化：滾動數組

只需 `dp[2][k]`，當前行 `cur = i&1`，上一行 `pre = (i-1)&1`。每輪清空 `cur` 行再轉移。

代碼

#include 
#include 
const int MAXN = 10005;
bool dp[2][105];
int a[MAXN];

int main() {
    int n, k;
    while (~scanf("%d%d", &n, &k)) {
        for (int i = 1; i <= n; ++i) {
            scanf("%d", &a[i]);
            a[i] = (a[i] % k + k) % k; // 規範到 [0, k-1]
        }
        memset(dp, 0, sizeof(dp));
        dp[1][a[1]] = true;
        for (int i = 2; i <= n; ++i) {
            int cur = i & 1, pre = (i-1) & 1;
            memset(dp[cur], 0, sizeof(dp[cur]));
            for (int j = 0; j < k; ++j) if (dp[pre][j]) {
                dp[cur][(j + a[i]) % k] = true;
                dp[cur][(j - a[i] + k) % k] = true;
            }
        }
        puts(dp[n&1][0] ? "Divisible" : "Not divisible");
    }
    return 0;
}

複雜度

• 時間：O(n × k) = 10⁴ × 100 = 10⁶，極快。
• 空間：O(k) = 100。

關鍵點

• **模 k 預處理** 將所有數轉為 [0, k-1]，簡化轉移。
• **減法取模** 用 `(j - x + k) % k` 保證非負。
• **滾動數組** 節省空間，注意每輪清空當前行。

總結

POJ 1745 是「模 k 線性 DP」的標準模板題。狀態為模 k 餘數，轉移為加減當前數。滾動數組優化空間，預處理模 k 簡化邏輯。掌握此模板，可解決所有「加減號組合整除性」問題。