LintCode "Permutation Index II" !

class Solution 
{
    long long dupPerm(unordered_map<int, int> &hash) 
    {
        if (hash.empty()) return 1;

        long long dup = 1;
        for (auto it = hash.begin(); it != hash.end(); ++it) 
        {
        dup *= w(it->second);
        }

        return dup;
    }
    long long w(int n) // n*(n-1)*..*2*1
    {
        long long ret = 1;
        while(n > 1)
        {
            ret *= n;
            n --;
        }
        return ret;
    }
public:
    /**
     * @param A an integer array
     * @return a long integer
     */
    long long permutationIndexII(vector<int>& A) 
    {
        int n = A.size();
        if(!n) return 0;
        
        long long index = 1;
        long long factor= w(n - 1);
        
        //  MSB -> LSB
        for(int i = 0; i < n; i ++)    
        {
            // Calc rank
          int rank = 0;
          for(int j = i + 1; j < n; j ++)
          {            
            if(A[i] > A[j])
              rank ++;
          }
          
          // Calc dup factor
            unordered_map<int, int> hm;          
            for(int j = i; j < n; j ++)
                ++hm[A[j]];
      
            index += rank * factor / dupPerm(hm);
            if(i < (n - 1))factor /= n - i - 1;
        }
        
        return index;
    }
};