Good sequence is defined as a non-empty sequence such that the sum of the elements in each of its non-empty subsequences is divisible by m.
For {1,2}
Its non-empty subsequences are {1},{2},{1,2}
for a good sequence all of the subsequences should divisible by m but {1},{2} are not divisible by 3.
Alright! “in each”, got it.
[1,2] is a good subsequence since 1+2 is divisible by 3. The problem statement mentions a good subsequence if its sum is divisible by 3, and by not parting the subsequence into another subsequence as you have done by parting [1,2] into [1], [2], [1,2]. The original [1,2] is already a subsequence. Please correct me if I am wrong. Thank you!
whats wrong with this?
no question is wrong.
I am getting partial correct answer with this can anyone tell me whats the issue is?
int main(void){
long int t;
cin>>t;
while(t–){//cout<<t<<"\n";
long long int n,m,x,cnt=0;
cin>>n>>m;
while(n–){
cin>>x;
if(x%m==0)cnt++;
}
cout<<(pow(2,cnt)-1)<<"\n";
}
return 0;
}
When you are directly doing cout << pow(2, freq)-1 it will output it as it is which means pow(2, freq) is outputting answers in double format which can make answers wrong for bigger constraints. But when you are putting it in int sum = pow(2, freq)-1 it converts/casts itself to int and then outputting the ans will give AC even for bigger constraints.
If you directly want to output the answer then you have to do like this cout << (int)pow(2, freq)-1;
which is casting the double to int.
/* package codechef; // don’t place package name! */
import java.util.;
import java.lang.;
import java.io.*;
/* Name of the class has to be “Main” only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
try{
//Your Solve
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] res = new int[n];
for(int i=0;i<n;i++)
{
int a = sc.nextInt();
int[] t = new int[a];
int k = sc.nextInt();
for(int j=0;j<a;j++)
{
t[j] = sc.nextInt();
}
for(int i1=0;i1<t.length;i1++)
{
int count = 0;
int sum = t[i1];
if(sum%k == 0)
{
count++;
}
for(int j1=i1+1;j1<t.length;j1++)
{
sum = sum+t[j1];
if(sum%k == 0)
{
count++;
}
}
res[i1]=count;
}
}
for(int i=0;i<n;i++)
{
System.out.println(res[i]);
}
}catch(Exception e){
return;
}
}
}
this is my code i guess this will work please check this code and please say if i am wrong
Sir can you prove why the answer will be 2^k-1 ? please 
Sir can you prove why the answer will be 2^k-1 ? please
can you prove why the answer will be 2^k-1 ?
its a deep request
Sir can you prove why the answer will be 2^k-1 ? please sir help me
If there are k candidate elements that can be used, we have two options for each of them- either we can include it or not and thus pow(2,k) and we subtract 1 for the case when we decide to not include all k elements.
Include them in a good subsequence.
For second query, read the definition of good subsequence in the problem.
pow(2,k) -1 will give the answer can you describe it in more details
i have understand little but if you explain more it would be more helpful
In good sequence each elements must be divisible by m
A set of k elements has 2^k subsets (or subsequences, in this case), including the empty subsequence.
So we subtract one (representing the empty sequence) from 2^k.
In Good Sequence, sum of elements of every non-empty Subsequence should be divisible by m.
Consider seq=[2,4,3,6] and m=2. There are 3 elements divisible by m but one isn’t. So, I can give you some sub sequences of seq such that sum of elements of the sub sequence isn’t divisible by m. Examples of such sub sequences are [2,3], [3], [2,3,6] ... and more. So, we can prove if a sequence has atleast 1 element that isn’t divisible by m, the seq definitely isn’t a good one.
Now can we prove the reverse? Consider a seq having all elements divisible by m. Is it always a good one? Yes! If a \% m=0 and b \% m=0 , then (a+b) \% m=0.
Now Question asks how many Sub sequence of a given sequence are good. A Sub sequence of a given seq will be good iff it has all the elements divisible by m. Take all the elements of the seq divisible by m. and we can either put or not put it in the Sub sequence.
seq=[2,4,3,6] and m=2
k=3
Candidate elements - [2,4,6] in order as they appear in the seq.
Notice the sub sequences will be 2^k (Notice the leaves of the tree). Since good seq has positive number of elements, ans will be 2^k-1.
Thanks a lot sir. It help me a lot to understand the problem and concept . 
Thanks a lot sir, in helping me to understand POWER SET concept.
