I have recently encountered this problem:

"Given an array *a* _{1}, *a* _{2}, ..., *a* _{ n}, (1 ≤ *n* ≤ 10^{5}, 1 ≤ *a* _{ i} ≤ 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 (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.

Auto comment: topic has been updated by xuanquang1999 (previous revision, new revision, compare).I'm not sure about this soultion.

Let's count all subsequences — 2^n. Now let count all subsequences with their and greater than 0. For all masks save count of numbers, that the mask is their submask. So using inclusion-exclusion principle we can calculate the answer.

UPD: OK

Ignore.

Here is the same task on codeforces : 449D - Jzzhu и числа. Maybe it will be helpful.

We were doing it on extra classes before a few days, but I do not know part with calculating function

ffrom editorial.This blog will surely help. SOS DP.

It can also be solved using this FFT-like transform (see transform for AND). My AC: 22102892 (though it required an optimization because it is )

That was wrong, ignore it

Isn't this solution for substring not subsequence?

Yes, you are right.