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.