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의 증가 횟수를 제어하지 못해서 레가 오랫동안 걸려서 정말 어이가 없어서 죽을 지경이다...
코드:

#include <cstdio>
#include <cstring>

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:
", ++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
", i + 1, dp(0, 0, 0));
        }
    }
    return 0;
}