### xuanquang1999's blog

By xuanquang1999, history, 5 years ago,

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.

• 0

 » 5 years ago, # |   0 Auto comment: topic has been updated by xuanquang1999 (previous revision, new revision, compare).
 » 5 years ago, # | ← Rev. 3 →   0 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
 » 5 years ago, # | ← Rev. 2 →   -13 Ignore.
 » 5 years ago, # | ← Rev. 2 →   +18 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 f from editorial.
•  » » 5 years ago, # ^ |   +10 This blog will surely help. SOS DP.
•  » » 5 years ago, # ^ |   +5 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 )
 » 5 years ago, # | ← Rev. 2 →   0 That was wrong, ignore it
•  » » 5 years ago, # ^ |   +33 Isn't this solution for substring not subsequence?
•  » » » 5 years ago, # ^ |   0 Yes, you are right.