UVA10616 - Divisible Group Sums(dp)

UVA10616 - Divisible Group Sums(dp)

UVA10616 - Divisible Group Sums(dp)

題目鏈接

題目大意：N個數，選擇m個數出來，問相加的和能夠整除MOD有多少種選擇方式。

解題思路：從1到N數選擇過去，每個數有選和不選兩種可能，並且（num + d） % MOD = num % MOD + d % MOD， 所以可以這麼做，最後判斷一下余數等於0麼。坑點是這題N個數會有負數，負數的取模 （num % MOD + MOD） % MOD.這一題因為沒有控制選擇的數目m的增加次數，導致re了好久，簡直無語死了。。。

代碼：

#include 
#include 

typedef long long ll;
const int maxn = 205;
const int maxm = 15;
const int maxd = 25;

int N, Q, MOD, M;
int num[maxn], tmp[maxn];
ll f[maxn][maxm][maxd];

void init () {

    for (int i = 0; i < N; i++)
        scanf ("%d", &num[i]);    
}

ll dp (int n, int m, int d) {

    ll& ans = f[n][m][d];
    if (ans != -1)
        return ans;

    if (n == N) {

        if (m == M && d == 0)
            return ans = 1;
        return ans = 0;
    }

    ans = 0;
    if (m < M)
        ans += dp(n + 1, m + 1, (d + tmp[n]) % MOD);
    ans += dp(n + 1, m, d); 
    return ans;
}

int main () {

    int cas = 0;
    while (scanf ("%d%d", &N, &Q) && (N || Q)) {

        init();

        printf ("SET %d:\n", ++cas);
        for (int i = 0; i < Q; i++) {
            scanf ("%d%d", &MOD, &M);

            memset (f, -1, sizeof (f));
            for (int j = 0; j < N; j++)
                tmp[j] = (num[j] % MOD + MOD) % MOD;

            printf ("QUERY %d: %lld\n", i + 1, dp(0, 0, 0));
        }
    }
    return 0;
}