GIVAWAY - Editorial

editorial
, ,
1

This is a Giveaway!! - EDITORIAL

Practice

Contest

Author: kishen1912000
Editorialist: kishen1912000

DIFFICULTY:

Cakewalk

PREREQUISITES:

Implementation, Math

PROBLEM:

Given an array A, find the number of good subsequences in it.
A good sequence is defined as a non-empty sequence of integers such that the sum of elements in each and every of its sub-sequence is divisible by M.

EXPLANATION:

This question is actually a giveaway! If you notice, a sequence is good only if all of its elements are divisible by M. So, basically find the number of elements in the array A which are divisible by M (say K). Then the total number of good subsequences are 2^K-1.

SOLUTIONS:

Setter's Solution 
for _ in range(int(input())):
    n,m = [int(s) for s in input().split()]
    l = [int(s) for s in input().split()]
    num = 0
    for i in range(n):
        if l[i]%m==0:
            num+=1
    print(pow(2,num)-1)