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.

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

	for(int mask=1000000; mask; mask--){
	    int pos=0;
	    while(!(mask&(1<<pos))) pos++;
	    int m2=mask^(1<<pos);
	    cts2[m2]+=cts2[mask];
	    for(int s=m2; s; s=(s-1)&m2){
	        dp2[s|(1<<pos)]+=cts2[mask];
	    }
	    dp2[(1<<pos)]+=cts2[mask];
	    
	    ans+=(tp[dp2[mask]]-1)*(__builtin_popcount(mask)%2?-1:1);
	    ans%=MOD;
	    if(ans<0) ans+=MOD;
	
	}