By usernameson, history, 6 days ago,

## Overview

Assume you are doing bitmask dp where each mask starts with a value and for every mask you want to add this value to all its submasks.

## Example Type problem

You have an array $a$ and for each number $x$ in $[1,10^{6}]$ you want to know how many $a_{i}$ have the property $a_{i}$ & $x = x$.

## Standard approach

You can use the standard submask iteration to do it in $O(3^n)$. For the example type problem the initial value for each $x$ is the number of times it appears in the array and these counts get added to all submasks.

## Example implementation

Code
Problem Application

• +8

 » 6 days ago, # |   0 Auto comment: topic has been updated by usernameson (previous revision, new revision, compare).
 » 6 days ago, # |   +24 The actual standard approach for this is a simple $O(k \cdot 2^k)$ loop on $k$-bit numbers. If you view the bitmasks $[0 \ldots 2^k - 1]$ as a $k$-dimensional array with length 2 in each dimension, this amounts to taking suffix sums along each axis in turn. Alternatively, you can view this process as a DP as is described in this blog. Or, you can view it as a factorization of the linear operator that performs this transform, as is described in this blog.
•  » » 5 days ago, # ^ |   0 Thanks. That's a much a better approach. I need to read those blogs.
 » 4 days ago, # |   +1 This is not SOS DP? https://codeforces.com/blog/entry/45223