Advertisement
Ryuuk

Divisible Group Sums

Aug 18th, 2017
198
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.96 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int tab[201];
  6. int N,D,M;
  7. long long dp[201][201][21];
  8.  
  9. long long DGS(int indice,int value, int set_sz)
  10. {
  11.     if(value==0 && set_sz==M)
  12.         return 1;
  13.     if(indice>=N || (set_sz==M && value!=0))
  14.         return 0 ;
  15.     if(dp[indice][value][set_sz]!=-1)
  16.         return dp[indice][value][set_sz];
  17.     return dp[indice][value][set_sz]=DGS(indice+1,(value%D+tab[indice]%D)%D,set_sz+1)+ DGS(indice+1,value%D,set_sz) ;
  18. }
  19.  
  20. int main()
  21. {
  22.    // freopen("input.txt","r",stdin);
  23.   //  freopen("output.txt","w",stdout);
  24.     int Q;
  25.     for(int j=1;;j++)
  26.     {
  27.         cin>>N>>Q;
  28.         if(N==0 && Q==0)
  29.             return 0;
  30.         for(int i=0;i<N;i++)
  31.             cin>>tab[i];
  32.         cout<<"SET "<<j<<":"<<endl;
  33.         for(int i=1;i<=Q;i++)
  34.         {
  35.             memset(dp,-1,sizeof dp);
  36.             cin>>D>>M;
  37.             cout<<"QUERY "<<i<<": "<<DGS(0,0,0)<<endl;
  38.         }
  39.     }
  40.     return 0;
  41. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement