Bitmask Implementation

/*
There 100 different types of caps each having a unique id from 1 to 100. 


Also, there ‘n’ persons each having a collection of variable number of caps. 


One day all of these persons decide to go in a party wearing a cap but to 


look unique they decided that none them will wear the same type of cap. 


So, count the total number of arrangements or ways such that none of them is 


wearing same type of cap.


*/


// C++ program to find number of ways to wear hats
#include<bits/stdc++.h>
using namespace std;

#define SET(a) memset(a,-1,sizeof(a))
#define MOD 1000000007
// dp[2^10][101] .. in dp[i][j], i denotes the mask i.e., it tells that
// how many and which persons are wearing cap. j denotes the first j caps
// used. So, dp[i][j] tells the number ways we assign j caps to mask i
// such that none of them wears the same cap
int dp[1025][101], n;
vector<int> caps[101];
// This is used for base case, it has all the N bits set
// so, it tells whether all N persons are wearing a cap.
int allmask;
// Mask is the set of persons, i is the number of
// caps processed starting from first cap.
int func(int bitmask, int capsNumber)
{
    // If all persons are wearing a cap so we
    // are done and this is one way so return 1
    if(bitmask == allmask)
        return 1;
// If not everyone is wearing a cap and also there are no more
    // caps left to process, so there is no way, thus return 0;
    if(capsNumber>100) return 0;
 // If we already have solved this subproblem, return the answer.
    if(dp[bitmask][capsNumber]!=-1)
        return dp[bitmask][capsNumber];
    int ret=0;
    // size is the total number of persons having cap with id i.
    ret = (ret + func(bitmask, capsNumber+1))%MOD;
     // So, assign one by one ith cap to all the possible persons
    // and recur for remaining caps.
    for(int i=0; i<caps[capsNumber].size(); i++)
    {
        int person = caps[capsNumber][i];
        // if person capList[i][j] is already wearing a cap so continue as
        // we cannot assign him this cap
        if((bitmask & (1<<person))==0)
            ret = (ret + func(bitmask | (1<<person), capsNumber+1))%MOD;
    }

    // Save the result and return it.
    dp[bitmask][capsNumber]=ret;
    return ret;
}

// Driver Program
int main()
{
     int n;   // number of persons in every test case
     cin >> n;

    //----------- READ INPUT --------------------------
    string temp, str;
    int x;
    getline(cin, str);  // to get rid of newline character
    for (int i=0; i<n; i++)
    {
        getline(cin, str);
        stringstream ss(str);

        // while there are words in the streamobject ss
        while (ss >> temp)
        {
            stringstream s;
            s << temp;
            s >> x;

            // add the ith person in the list of cap if with id x
            caps[x].push_back(i);
        }
    }
    //----------------------------------------------------

    // All mask is used to check of all persons
    // are included or not, set all n bits as 1
    allmask = (1 << n) - 1;

    // Initialize all entries in dp as -1
    SET(dp);

    // Call recursive function count ways
    cout << func(0, 1) << endl;
     return 0;
}

// input: 


//3


//5 100 1


//2


//5 100


//Output: 4