Introduction
Generally bitmasking is used to solve optimisation problems with the following procedure. Store all possible states then pick the best one. Doing this cleverly can sometimes reduce a brute force approach that takes O(N!) to something that takes O(2N). However, if you apply the standard bitmasking approach to counting problems you can run into issues.
A Simple Case
Let's consider a simple case where we have three balls, two are red and one is blue and there are two problems. For the first problem we have a function f that takes balls and spits out a value and we want to optimise f. For the second problem we want to count the number of selections of balls we can make where the order of the selection does not matter and the two red balls are indistinguishable. Bitmasking in the usual way works perfectly fine for the first problem. However if we encode each of the balls with its own bit and try to solve the second problem we will get an answer that is too large. Basically our encoding overlooks the fact that red balls are indistinguishable.
A Solution
To solve this problem we can still reserve the first two bits for a red ball. However instead of letting 010 and 001 denote the cases where the one red ball is selected or the other is selected we let 001 denote the case where 1 red ball is selected and 010 where 2 red balls are selected. Of course doing this means 011 will denote the case where three red balls are selected. This means the bitmask 011 will not be valid in our case since so for counting problems we will need to keep track of which bitmasks are valid and check for validity before doing things with them.
A real problem
I used the approach outlined to solve colorfulGardenHard from topcoder https://community.topcoder.com/stat?c=problem_statement&pm=14247. The basic idea of the question is you have two strings of length at most 15. You want to find how many distinct rearrangements of the the letters there are in the first string such that no two adjacent letters in the first string are the same and no letter in position i of the first string is the same as the letter in position i of the second string. Also because answers can get big we have to return our answer mod 1,000,000,007
My approach
First we start storing some basic results about the first string such as which characters appear and how many times they appear. With this information we figure out where to store the counts for each character in a selection in a bitmask. We also create a function called isValid to see check if a given bitmask represents a selection that exceeds the count for a given character. We also make isValid have a parameter n that checks if the number of elements in the selection represented by the bitmask is equal to n. This is useful later for the dynamic programming part.
Now we get to the dynamic programming part. We consider what happens when we have a character sequence of length n that is valid so far that takes a collection of elements represented by a bitmask k and ends in a character represented by j. If we have another character represented by j' if three conditions hold we can put j' at the end of j to give a sequence of length n+1 that is valid so far. Two of the conditions are given in the question namely j and j' cannot be equal and j' cannot correspond to the character given in n+1th position of the second string. The third condition is the new bitmask we get by appending j' is this manner must be valid. To get the new bitmask we take the previous bitmask and add 1<<start[j'] to it i.e we are just figuring out where the count for the character j' is encoded in the bitmask then going there and adding 1 to the count. To test for validity we use our isValid function.
Using the above reasoning we do our dynamic programming using an array where dp[i][k][j] stores the number of sequences of length i ending in the character represented by j and with a collection of characters represented by the bitmask k. We initially set everything in the array to 0. Then we loop based on the procedure above (in my code I filled row 1 first then started the loop at row 2, however looping immediately should also work).
The rest is just a matter of summing and taking the modulo diligently to avoid overflow issues when things get large.
code
#include<iostream>
#include<vector>
#include<algorithm>
const int MOD=1e9+7;
using namespace std;
class ColorfulGardenHard{
vector<int> pos, starts, charCt;
//check if k corresponds to a mask with elem elements
//and the character count encoded in the mask
//does not exceed the total number of characters available
bool isValid(int k, int elems){
int tot=0;
for(int i=0; i<pos.size(); i++){
int ct=charCt[pos[i]];
if(i==pos.size()-1){
tot+=k>>starts[i];
if(k>>starts[i]>ct)
return false;
}
else{
int s=starts[i];
int e=starts[i+1];
int comp=k>>s;
int m=((1<<(e-s))-1);
comp=comp&m;
tot+=comp;
if(comp>ct)
return false;
}
}
return tot==elems;
}
public:
int count(string garden, string forbid){
//vi stores the counts of every character for a-z
//appearing in garden we then store this as charCt
//so isValid() can use it
vector<int> vi(26,0);
for(char c:garden){
vi[c-'a']++;
}
charCt=vi;
//pos stores the locations of characters
//that appear in the string i.e ignore those
//with count 0
for(int i=0; i<vi.size(); i++){
if(vi[i])
pos.push_back(i);
}
int k=0;
//start stores the for starting points for
//each character in the string we assign
// in the bitmask representation
//this is the key difference between optimisation
//problems and counting problems
//since we are storing counts of elements
//we may need multiple bits to do so
for(int i:pos){
starts.push_back(k);
int j=0;
int ct=vi[i];
while(ct>=1<<j){
k++;
j++;
}
}
//here is where we use dynamic programming
//dp[i][k][j] stores the number of sequences of length i
//that make use of the character counts represented by the
//bitmask k and end in the character determined by j
vector<vector<vector<long long>>> dp(garden.size()+1,vector<vector<long long>>((1<<16),vector<long long>(pos.size(),0)));
long long ans=0;
for(int j=0; j<pos.size(); j++){
if(forbid[0] !=(char)('a'+pos[j]))
dp[1][1<<starts[j]][j]=1;
}
for(int i=1; i<garden.size(); i++){
for(int j=0; j<pos.size(); j++){
for(int k=0; k<1<<16; k++){
if(dp[i][k][j]){
for(int j2=0; j2<pos.size(); j2++){
if(j!=j2 && forbid[i] !=(char)('a'+pos[j2]) && isValid(k+(1<<starts[j2]),i+1))
dp[i+1][k+(1<<starts[j2])][j2]+=dp[i][k][j]%MOD;
}
}
}
}
}
//getting the answer by summing the number of valid sequences
//of length garden.size() that end in j
//Although the sum involves k there will only be one value
//of k that is non zero namely the value the corresponds
//to using all the characters in the string
for(int j=0; j<pos.size(); j++){
for(int k=0; k<1<<16; k++){
ans+=dp[garden.size()][k][j]%MOD;
ans%=MOD;
}
}
return ans;
}
};
