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.
↵
"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$
↵
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.
