Advertisement
Guest User

Untitled

a guest
May 23rd, 2018
71
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.27 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define lli int long long
  5. #define llu unsigned long long
  6. #define pb push_back
  7. #define mp make_pair
  8. #define READ freopen("in.txt","r",stdin);
  9. #define WRITE freopen("outer.txt","w",stdout);
  10. //#define sort(v) sort(v.begin(),v.end())
  11. #define M 100000007
  12.  
  13. lli n,q,d,m,ar[204],dp[12][223][22];
  14. lli dfs(lli cnt,lli pos,lli sum)
  15. {
  16. if(pos==n+1)
  17. {
  18. if(cnt==m)
  19. {
  20. if(sum%d==0) return 1;
  21. else return 0;
  22. }
  23. return 0;
  24. }
  25. lli k=sum%d;
  26. if(dp[cnt][pos][k]!=-1) return dp[cnt][pos][k];
  27. lli pp=d+ar[pos]%d;
  28. lli c=0;
  29. pp=(k+pp%d)%d;
  30. c+=dfs(cnt+1,pos+1,pp);
  31. c+=dfs(cnt,pos+1,k);
  32. return dp[cnt][pos][k]=c;
  33. }
  34.  
  35. int main()
  36. {
  37. lli t;
  38. scanf("%lld",&t);
  39. for(lli t1=1; t1<=t; t1++)
  40. {
  41. scanf("%lld %lld",&n,&q);
  42. for(lli i=1; i<=n; i++)
  43. {
  44. scanf("%lld",&ar[i]);
  45. }
  46. printf("Case %lld:\n",t1);
  47. for(lli i=1; i<=q; i++)
  48. {
  49. memset(dp,-1,sizeof dp);
  50. scanf("%lld %lld",&d,&m);
  51. lli p=dfs(0,1,0);
  52. printf("%lld\n",p);
  53. }
  54. }
  55. return 0;
  56.  
  57. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement