xuanquang1999's blog

How to count the number of subsequence in an array with 'and' operator sum equal to 0?
By xuanquang1999, history, 8 years ago, In English

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.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by xuanquang1999 (previous revision, new revision, compare).

→ Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it -13 Vote: I do not like it

Ignore.

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +18 Vote: I do not like it

Here is the same task on codeforces : 449D - Jzzhu and Numbers. 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.

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

That was wrong, ignore it

→ Reply