Magic Set - Codechef Problem

[closed account oG3kizwU]

Can anyone tell why in the sample input 1 it is given output 0 saying no good subsequences,although we can have subsequence (1,2) whose sum is divisible by 3?

Katya has a sequence of integers a1,a2,…,an and an integer m.

She defines a good sequence of integers as a non-empty sequence such that the sums of all its non-empty subsequences are divisible by m.

Katya wants to know the number of good subsequences of the sequence a. Can you help her?

Input
The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains two space-separated integers n and m.
The second line contains n space-separated integers a1,a2,…,an.
Output
For each test case, print a single line containing one integer — the number of good subsequences.

Constraints
1≤T≤1,000
1≤n≤30
1≤m≤1,000
1≤ai≤1,000 for each valid i

Example Input
2
2 3
1 2
2 3
1 3
Example Output
0
1
Explanation
Example case 1: There are no good subsequences.

Example case 2: There is exactly one good subsequence of a: [3].

[himanshusainie97]

not getting it what to do i have applied pigeonhole principle here is my code it's not accepted on codechef:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a[1000],prefixsum[1000];
int main(){
ll int t;
cin>>t;
while(t--){
int n;
ll int m;
cin>>n>>m;
ll sum=0;
memset(prefixsum,0,sizeof prefixsum);
prefixsum[0]=1;
for(int i=0;i<n;i++){
cin>>a[i];
sum+=a[i];
sum%=m;
sum=(sum+m)%m;
prefixsum[sum]++;
}
ll ans=0;
for(int i=0;i<n;i++){
ll no=prefixsum[i];
ans+=((no)*(no-1))/2;
}
cout<<ans<<endl;
}
return 0;
}

[Repeater]

You sure have picked some awful, awful, awful names for your variables. Names so bad that anyone reading the code has no idea what you're trying to do.