A and B are getting bored so they decide to play a game with an array X of n elements with A starting the game. In each turn : A player selects some or all elements from array X with the same value and removes them from array X - The player whose turn makes array X becomes empty wins the game.
B being clever, modifies the game. He decides to select some distinct elements (among those present in array X[]) and deletes all other elements which are not selected from X. The game is then played using this modified array. For example, consider X=[1,2,1,3,4,8,6,2]. If B chooses values (3,4,2), then the modified array with which the game is played is [1,1,8,6,2].
Both A and B play optimally. Find the number of possible subsets of elements that B can select to modify X[] such that B is bound to win.
Print the answer modulo 10^9+7,since the number of possible subsets can be large.Consider an empty subset as a valid answer.
Input Format
• First line contains an integer t denoting the number of test cases.
• Second line contains an integer n.
• Next line contains n elements of X[].
Constraints
• 1 <= t <= 10
• 1 <= N <= 2*10^5
• 1 <= X[i] <= 10^18
Output Format
Print the number of possible subsets B can choose in a new line. Print the ans modulo 10^9+7.
My code works for small test cases but with large ones, it gives timeout. I am creating a frequency array i.e after sorting the given array, I count all the occurrences of a single number and put that count in another array. Then I generate a bit mask for the frequency array. We can only remove distinct elements (only one from each frequency). If bit is 1 - decrease its frequency by one and if it 0 then leave it.
Ex:- arr = {1,1 ,2,2,3}
then frequency arr = { 2, 2, 1}
if bit mask is 011 then frequency arr becomes {2,1,0}
then with recursion , I decide whether B will win , if he wins increment the ans by 1.
My Code:-
long long int exp(long long int x, long long int n)
{
long long int res = 1;
while (n != 0)
{
if (n & 1)
{
res = (res * 1LL * x);
}
x = (x * 1LL * x);
n = n >> 1;
}
return res;
}
bool func(int arr[], int &n, int &count)
{
if (count == 0)
{
return false;
}
if (count == 1)
{
return true;
}
bool ans = 0;
for (int i = 0; i < n; i++)
{
int x = arr[i];
for (int j = 1; j <= x; j++)
{
arr[i] -= j;
count -= j;
ans = ans || !func(arr, n, count);
arr[i] += j;
count += j;
}
}
return ans;
}
int main()
{
int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
long long int arr[n];
for (int i = 0; i < n; i++)
{
cin >> arr[i];
}
sort(arr, arr + n);
vector<int> v;
v.reserve(200000);
v.push_back(1);
for (int i = 1; i < n; i++)
{
if (arr[i - 1] == arr[i])
{
v[v.size() - 1]++;
}
else
{
v.push_back(1);
}
}
ll ans = 0;
int temp[v.size()];
for (int i = 0; i < v.size(); i++)
{
temp[i] = v[i];
}
int count = 0;
for (int i : v)
{
count += i;
}
int count_temp = count;
for (long long int i = 0; i < exp(2, v.size()); i++)
{
long long int t = i;
int mul = 0;
while (t != 0)
{
if (t & 1)
{
temp[mul]--;
count_temp--;
}
t = t >> 1;
mul++;
}
if (!func(temp, n, count_temp))
{
ans++;
}
for (int j = 0; j < v.size(); j++)
{
temp[j] = v[j];
}
count_temp = count;
}
cout << ans%std_modulo << "\n";
}
}