# Tag Info

This can be done in $O(n2^n)$, where $n$ is the number of variables (naive expansion would take $O(2^{2n})$ in the worst case). This is a standard technique called "sum over subsets/supersets/submasks/supermasks". A usual example is the ANF computation, which does it in $GF(2)$ so it uses the XOR operation. Here it is basically the same but since ...