Unimodal Subsets |codechef |starters 81

Problem

You are given a multiset �A containing �N integers.
Your task is to count the number of distinct subsets of the multiset �A, that have a unique mode. Since this number can be huge, print it modulo 10000000071000000007.

Note that if two subsets form the same set of values, they are not counted as different subsets. For example, consider �=[1,1,2,1]A=[1,1,2,1], the distinct subsets of the multiset are {1},{2},{1,1},{1,2},{1,1,1},{1,1,2},{1,1,1,2}{1},{2},{1,1},{1,2},{1,1,1},{1,1,2},{1,1,1,2}.

Input Format

  • The first line of input will contain a single integer �T, denoting the number of test cases.
  • Each test case consists of multiple lines of input.
    • The first line of each test case contains an integer �N — the number of integers in the multiset.
    • The next line contains �N space-separated integers, denoting the elements of the multiset.

Output Format

For each test case, output on a new line, the number of distinct subsets of the multiset �A, that have a unique mode, modulo 109+7109+7.

Constraints

  • 1≤�≤2⋅1041≤T≤2⋅104
  • 1≤�≤1051≤N≤105
  • 1≤��≤1091≤Ai​≤109
  • The sum of �N over all test cases won’t exceed 2⋅1052⋅105.

Sample 1:

Input

Output

3
4
1 1 1 2
3
1 1 1
4
1 2 3 4
6
3
4

Explanation:

Test case 11: The distinct subsets of the multiset are: {1},{2},{1,1},{1,2},{1,1,1},{1,1,2},{1,1,1,2}{1},{2},{1,1},{1,2},{1,1,1},{1,1,2},{1,1,1,2}.
Subsets with unique mode are {1},{2},{1,1},{1,1,1},{1,1,2},{1,1,1,2}{1},{2},{1,1},{1,1,1},{1,1,2},{1,1,1,2}. Note that, in all these subsets, there is exactly one element having maximum frequency, and thus, there is a unique mode.

Test case 22: The distinct subsets of the multiset are: {1},{1,1},{1,1,1}{1},{1,1},{1,1,1}. Note that, all these subsets have unique mode.

Test case 33: The distinct subsets having unique mode are: {1},{2},{3},{4}{1},{2},{3},{4}. Some distinct subsets that do not have unique mode are {1,2},{2,3},{2,3,4},{1,3,4}{1,2},{2,3},{2,3,4},{1,3,4}.

click on below image to get the solution:

Leave a Reply

Your email address will not be published. Required fields are marked *

यकीन नहीं मानोगे! ये 9 जगहें हैं UP में जो ताजमहल को भी फीका कर देंगी! मेरठ: इतिहास, धर्म और खूबसूरती का संगम! घूमने के लिए ये हैं बेहतरीन जगहें रोज आंवला खाने के 10 धांसू फायदे जो आपको कर देंगे हेल्दी और फिट! Anjali Arora to play Maa Sita: रामायण फिल्म में सीता का रोल निभाएंगी अंजली अरोड़ा, तैयारियों में लगी? Rinku Singh : रिंकू सिंह ने अपने दाहिने हाथ पर बने टैटू का खोला राज, सुनकर हो जायेंगे दंग Panchayat Season 3 Release Date: फुलेरा में मचा भूचाल! क्या अभिषेक इस बार हार जाएगा?