FattyLovesMangoes's blog

How to solve this?
By FattyLovesMangoes, history, 22 months ago, In English

Given an array a (0 <= a[i] <= 2^22) of length N(<=1e5). For every i, you need to find the number of j such that a[i]&a[j] = a[j].

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
22 months ago, # |
  Vote: I like it +42 Vote: I do not like it 
for(int i = 0; i < n; i ++)
    f[a[i]] ++;
for(int j = 0; j < 22; j ++) 
    for(int i = 0; i < (1 << 22); i ++)
        if(i >> j & 1) f[i] += f[i ^ (1 << j)];

f[a[i]] is the answer

→ Reply