UVa 10036 Divisibility

10036.cpp

#include <bits/stdc++.h>
using namespace std;

#define F first
#define S second
#define PB push_back
#define endl '\n'

template <class T> T smod(T a, T b) {
    return (a % b + b) % b; }

typedef long long ll;
typedef vector<ll> vll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;

const int MX = 10007;

int A[MX], k, n;
int dp[MX][100];

int f(int i, int sum) {
    if(i == n) return !sum;
    if(~dp[i][sum]) return dp[i][sum];

    dp[i][sum]  = f(i + 1, smod(sum + A[i], k));
    dp[i][sum] |= f(i + 1, smod(sum - A[i], k));

    return dp[i][sum];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;

    while(t--) {
        cin >> n >> k;
        memset(dp, -1, sizeof dp);
        for(int i=0; i<n; i++) cin >> A[i];
        if(f( 0, 0 )) cout << "Divisible" << endl;
        else cout << "Not divisible" << endl;
    }

    return 0;
}