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*_{p1}, *a*_{p2}, ..., *a*_{pk} that *a*_{p1}&*a*_{p2}&...&*a*_{pk} = 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.