HDU 5464 Clarke and problem：DP 計算子集和模 p 為 0 的方案數

題目大意

給定 n (≤ 1000) 個整數 a_i（絕對值 ≤ 1e9）和模數 p (≤ 1000)。從中任選若干個數（可選 0 個），求其和模 p 等於 0 的方案數，模 1e9+7。

動態規劃

定義 dp[i][j] 為考慮前 i 個數，和模 p 為 j 的方案數。初始 dp[0][0] = 1（選 0 個）。轉移：

for i = 1..n:
    v = (a[i] % p + p) % p; // 修正負數
    for j = 0..p-1:
        dp[i][j] = (dp[i-1][j] + dp[i-1][(j - v + p) % p]) % MOD;

答案為 dp[n][0]。可用滾動數組優化空間至 O(p)。

參考代碼 (滾動數組)

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9+7;
int dp[2][1005];

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int n, p; scanf("%d%d", &n, &p);
        memset(dp, 0, sizeof(dp));
        dp[0][0] = 1;
        int cur = 0, nxt = 1;
        for (int i = 1; i <= n; ++i) {
            int x; scanf("%d", &x);
            x = (x % p + p) % p;
            memcpy(dp[nxt], dp[cur], sizeof(dp[0]));
            for (int j = 0; j < p; ++j) {
                int nj = (j + x) % p;
                dp[nxt][nj] = (dp[nxt][nj] + dp[cur][j]) % MOD;
            }
            swap(cur, nxt);
        }
        printf("%d\n", dp[cur][0]);
    }
    return 0;
}

複雜度

時間 O(n·p)（≤ 1e6），空間 O(p)，輕鬆通過。