How to count the number of subsequence in an array with 'and' operator sum equal to 0?

Revision en2, by xuanquang1999, 2017-01-01 16:13:12

I have recently encountered this problem:

"Given an array a1, a2, ..., an, (1 ≤ n ≤ 105, 1 ≤ ai ≤ 106), count the number of subsequence ap1, ap2, ..., apk that ap1&ap2&...&apk = 0 (print the remain of division of that number by 109 + 7"

The best solution that I can come up is a dynamic programming solution that is not fast enough to solve this problem. How to solve this problem?

Thanks in advance.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English xuanquang1999 2017-01-01 16:13:12 237 (published)
en1 English xuanquang1999 2017-01-01 16:03:48 321 Initial revision (saved to drafts)