Minor submask dp optimisation

Revision en1, by usernameson, 2021-11-25 08:42:59

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)$$$.

Slight speed up

You can speed this up slightly by using a lazy prop style technique. Remove a bit in the original mask

Tags dp, bitmask

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English usernameson 2021-11-25 09:13:01 1019 Tiny change: 'n\n~~~~~\nfor(int ma' -> 'n\n~~~~~\n for(int ma' (published)
en1 English usernameson 2021-11-25 08:42:59 624 Initial revision (saved to drafts)