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

Правка en2, от 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. Язык Кто Когда Δ Комментарий
en2 Английский xuanquang1999 2017-01-01 16:13:12 237 (published)
en1 Английский xuanquang1999 2017-01-01 16:03:48 321 Initial revision (saved to drafts)