Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

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 a 1, a 2, ..., a n, (1 ≤ n ≤ 105, 1 ≤ a i ≤ 106), count the number of subsequence a p 1, a p 2, ..., a p k that a p 1&a p 2&...&a p k = 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.


  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)