We have $n$ non-negative integers $a_1, a_2, \dots, a_n$. We will call a sequence of indexes $i_1, i_2, \dots, i_k$ such that $1\le i_1 < i_2 < \dots< i_k\le n$ a group of size $k$.
How many groups exists such that
$$a_{i_1}\mathbin{\&} a_{i_2}\mathbin{\&}\ldots\mathbin{\&} a_{i_k} = 0\;,$$
where $1\le k\le n$.
Operation $x\mathbin{\&} y$ denotes bitwise AND operation of two numbers.
Approach:
Use inclusion-exclusion principle in this problem.
Let $f(x)$ be the count of numbers $i$ where $A_i\mathbin{\&}x = x$.
Let $g(x)$ be the number of $1$s in the binary respresentation of $x$. Then the answer is equal to
$$(-1)^{g(x)}\cdot 2^{f(x)}$$
But I could not understand the correctness and working intuition of this.
For calculating f(x)
if Number are in range 0 to 10^6 so bit required to represent them is 20.
for(int i=0;i<20;i++) {
for(int j=0;j<(1<<20);j++) {
if(0 == (j & (1<<i))) {
f[j | (1<<i)] += f[j];
}
}
}
Please Help.
For Example:
0 1 2 3
Ans: 10
8 group with zero
one group with1 and 2
and finally ` 1 and 2 and 3` $\endgroup$ – Sunny Jul 24 '15 at 9:56