CHow to count the number of subsequence in an array with 'and' operator sum equal to 0?
Difference between en1 and en2, changed 237 character(s)
I have recently encountered this problem:↵

"Given an array $a_1,a_2,...,a_n$, ($1 \leq n \leq 10^5$, $1 \leq a_i \leq 10^6$), 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$ t(print the remain of division of that number by $10^9+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)