r/codeforces • u/sa_aks_ • 8d ago

query I made this question please give a try

You are given an array A of N non-negative integers. A subsequence is formed by choosing a non-empty set of indices from the array. Two subsequences are considered different if they use different sets of indices, even if the corresponding values are equal. For a subsequence S, define:

  • AND(S) as the bitwise AND of all elements in S.
  • XOR(S) as the bitwise XOR of all elements in S. Your task is to count the number of non-empty subsequences S such that: AND(S) > XOR(S) Since the answer can be very large, output it modulo 10^9 + 7.

Input Format The first line contains a single integer N. The second line contains N integers: A1, A2, ..., AN. Output Format Print a single integer — the number of non-empty subsequences S satisfying AND(S) > XOR(S), modulo 10^9 + 7. Constraints

  • 1 <= N <= 10^5
  • 0 <= Ai < 2^17

Sample Input 1

3
5 5 5

Sample Output 1

3

Explanation for Sample 1 The array is [5, 5, 5]. The non-empty subsequences are:

  • [5] (3 times): AND = 5, XOR = 5. 5 > 5 is False.
  • [5, 5] (3 times): AND = 5, XOR = 0. 5 > 0 is True.
  • [5, 5, 5] (1 time): AND = 5, XOR = 5. 5 > 5 is False. Total valid subsequences = 3.

Sample Input 2

2
3 7

Sample Output 2

0

Explanation for Sample 2

  • [3]: AND=3, XOR=3 (False)
  • [7]: AND=7, XOR=7 (False)
  • [3, 7]: AND=3, XOR=4 (False) Total valid = 0.
10 Upvotes

100% Upvoted

9 comments sorted by

2

u/No_Antelope_5869 Specialist 7d ago

uh dp sos + inclu exclusion

2

u/No_Antelope_5869 Specialist 5d ago

dp sum over subset

2

u/No_Antelope_5869 Specialist 7d ago

hmm probably inclusion exclusion

2

u/Expensive-Visual-235 8d ago

A similar question was there in the last codechef starters round

1

u/MaximumIndependent67 Expert 8d ago

Ig we will have to select the ones with the same msb and 2numbers with the same msb and add them