Minor submask dp optimisation
source link: http://codeforces.com/blog/entry/97222
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
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 aa and for each number xx in [1,106][1,106] you want to know how many aiai have the property aiai & x=xx=x.
Standard approach
You can use the standard submask iteration to do it in O(3n)O(3n). For the example type problem the initial value for each xx is the number of times it appears in the array and these counts get added to all submasks.
Slight speed up
You can speed this up slightly by using a lazy prop style technique. You iterate through all masks in decreasing order and remove a bit in the original mask. This becomes your new mask call it mask2. You then add the value of mask to the value of mask2. Next you iterate through all submasks of mask2 and add the value to the submask with bit removed added back.
Example implementation
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK