Problem Link : https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1557

Solution Idea:

This is a knapsack problem where the given numbers are objects. we have to count how many set is there of size m whose sum is divisible by d.

Now here we have a three state dp. where idx indicates the current index of objects, cnt indicates how many objects we have taken till now and we can’t take more than m element and this is a base case. and 3rd parameter is sum, which indicates the sum of the objects we have taken till now.

Now the sum can be very large and we can’t store the original sum in our dp array because we can’t declare such large array. So we can store the (sum%d) in the array because (sum%d) < 20  so we can easily store that. so in every step we have two call one is by taking current object and another is without taking that object. and the base case is when we have taken m elements then the sum value is either 0 or not. if it is a zero then we can say that it is divisible by d.

Now the most tricky part in this problem is the numbers can be negative and we have to consider how to mod the negative numbers. Lets see a example-

-12 % 7 = ??

If we calculate through computer or calculator the output will be -5. but is this correct??

Normally a%b = (a-x)

Where x is the greatest element which is divisible by b and which is less than or equal to a.

So we can say that x%b==0 and x<=a.

Now lets find the number x for -12 . we can see that -14 is the greatest element which is divisible by 7 and which is less than or equal to -12.

So the correct ans for -12%7 = (-12-(-14))= -12+14=2 😛

We can calculate the modulus result easily in this way.

if the operation is a%b and a<0. then the correct modulus value will be (a%b)+b.

-12%7= (-12%7)+7=-5+7=2 😀

So in this problem we have to consider the modulus of negative numbers.

/*
         +-+ +-+ +-+
         |R| |.| |S|
         +-+ +-+ +-+
 */

#include <bits/stdc++.h>

#define pii             pair <int,int>
#define sc              scanf
#define pf              printf
#define Pi              2*acos(0.0)
#define ms(a,b)         memset(a, b, sizeof(a))
#define pb(a)           push_back(a)
#define MP              make_pair
#define db              double
#define ll              long long
#define EPS             10E-10
#define ff              first
#define ss              second
#define sqr(x)          (x)*(x)
#define D(x)            cout<<#x " = "<<(x)<<endl
#define VI              vector <int>
#define DBG             pf("Hi\n")
#define MOD             100007
#define MAX             10000
#define CIN             ios_base::sync_with_stdio(0); cin.tie(0)
#define SZ(a)           (int)a.size()
#define sf(a)           scanf("%d",&a)
#define sfl(a)          scanf("%lld",&a)
#define sff(a,b)        scanf("%d %d",&a,&b)
#define sffl(a,b)       scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)     scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)    scanf("%lld %lld %lld",&a,&b,&c)
#define loop(i,n)       for(int i=0;i<n;i++)
#define REP(i,a,b)      for(int i=a;i<b;i++)
#define TEST_CASE(t)    for(int z=1;z<=t;z++)
#define PRINT_CASE      printf("Case %d: ",z)
#define all(a)          a.begin(),a.end()
#define intlim          2147483648
#define inf             1000000
#define ull             unsigned long long

using namespace std;


/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/

int n, q,d,m;
int ara[300];
ll dp[210][11][22];

ll func(int idx, int cnt, int sum)
{

    if(cnt==m)
    {
        if(sum==0) return 1;
        return 0;
    }
    if(idx>=n) return 0;

    ll &ret=dp[idx][cnt][sum];

    if(ret!=-1) return ret;


    ll xx=0,yy=0;

    ll temp=sum+ara[idx];
    temp%=d;
    if(temp<0) temp+=d;

    xx=func(idx+1,cnt+1,temp);

    yy=func(idx+1,cnt,(sum)%d);

    return ret=xx+yy;
}

int main()
{
    ///freopen("in.txt","r",stdin);
    ///freopen("out.txt","w",stdout);

    int z=0;

    while(sff(n,q)==2 && (n && q))
    {
        z++;
        pf("SET %d:\n",z);
        loop(i,n) sf(ara[i]);
        loop(i,q)
        {

            sff(d,m);
            ms(dp,-1);
            printf("QUERY %d: %lld\n",i+1,func(0,0,0));
        }
    }

    return 0;
}