Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- #define lli int long long
- #define llu unsigned long long
- #define pb push_back
- #define mp make_pair
- #define READ freopen("in.txt","r",stdin);
- #define WRITE freopen("outer.txt","w",stdout);
- //#define sort(v) sort(v.begin(),v.end())
- #define M 100000007
- lli n,q,d,m,ar[204],dp[12][223][22];
- lli dfs(lli cnt,lli pos,lli sum)
- {
- if(pos==n+1)
- {
- if(cnt==m)
- {
- if(sum%d==0) return 1;
- else return 0;
- }
- return 0;
- }
- lli k=sum%d;
- if(dp[cnt][pos][k]!=-1) return dp[cnt][pos][k];
- lli pp=d+ar[pos]%d;
- lli c=0;
- pp=(k+pp%d)%d;
- c+=dfs(cnt+1,pos+1,pp);
- c+=dfs(cnt,pos+1,k);
- return dp[cnt][pos][k]=c;
- }
- int main()
- {
- lli t;
- scanf("%lld",&t);
- for(lli t1=1; t1<=t; t1++)
- {
- scanf("%lld %lld",&n,&q);
- for(lli i=1; i<=n; i++)
- {
- scanf("%lld",&ar[i]);
- }
- printf("Case %lld:\n",t1);
- for(lli i=1; i<=q; i++)
- {
- memset(dp,-1,sizeof dp);
- scanf("%lld %lld",&d,&m);
- lli p=dfs(0,1,0);
- printf("%lld\n",p);
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement