Блог пользователя FattyLovesMangoes

How to solve this?
Автор FattyLovesMangoes, история, 2 года назад, По-английски

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].

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
2 года назад, # |
  Проголосовать: нравится +42 Проголосовать: не нравится 
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

→ Ответить