【多数组合 数学 字符串】2514. 统计同位异构字符串数目

template<int MOD = 1000000007>
class C1097Int
{
public:
  C1097Int(long long llData = 0) :m_iData(llData% MOD)
  {
  }
  C1097Int  operator+(const C1097Int& o)const
  {
    return C1097Int(((long long)m_iData + o.m_iData) % MOD);
  }
  C1097Int& operator+=(const C1097Int& o)
  {
    m_iData = ((long long)m_iData + o.m_iData) % MOD;
    return *this;
  }
  C1097Int& operator-=(const C1097Int& o)
  {
    m_iData = (m_iData + MOD - o.m_iData) % MOD;
    return *this;
  }
  C1097Int  operator-(const C1097Int& o)
  {
    return C1097Int((m_iData + MOD - o.m_iData) % MOD);
  }
  C1097Int  operator*(const C1097Int& o)const
  {
    return((long long)m_iData * o.m_iData) % MOD;
  }
  C1097Int& operator*=(const C1097Int& o)
  {
    m_iData = ((long long)m_iData * o.m_iData) % MOD;
    return *this;
  }
  C1097Int  operator/(const C1097Int& o)const
  {
    return *this * o.PowNegative1();
  }
  C1097Int& operator/=(const C1097Int& o)
  {
    *this /= o.PowNegative1();
    return *this;
  }
  bool operator==(const C1097Int& o)const
  {
    return m_iData == o.m_iData;
  }
  bool operator<(const C1097Int& o)const
  {
    return m_iData < o.m_iData;
  }
  C1097Int pow(long long n)const
  {
    C1097Int iRet = 1, iCur = *this;
    while (n)
    {
      if (n & 1)
      {
        iRet *= iCur;
      }
      iCur *= iCur;
      n >>= 1;
    }
    return iRet;
  }
  C1097Int PowNegative1()const
  {
    return pow(MOD - 2);
  }
  int ToInt()const
  {
    return m_iData;
  }
private:
  int m_iData = 0;;
};
template<class T >
class CFactorial
{
public:
  CFactorial(int n):m_res(n+1){
    m_res[0] = 1;
    for (int i = 1; i <= n; i++) {
      m_res[i] = m_res[i - 1] * i;
    }
  } 
  T Com(int iSel, int iCanSel) {
    return m_res[iCanSel] / m_res[iSel]/ m_res[iCanSel - iSel];
  }
  T Com(const vector<int>& cnt) {
    T biRet = 1;
    int iCanSel = std::accumulate(cnt.begin(), cnt.end(), 0);
    for (int j = 0; j < cnt.size(); j++) {
      biRet *= Com(cnt[j], iCanSel);
      iCanSel -= cnt[j];
    }
    return biRet;
  }
  vector<T> m_res;
};
class Solution {
public:
  int countAnagrams(string s) {
    CFactorial<C1097Int<>> fac(s.length());
    vector<int> cnt(26);
    s += ' ';
    C1097Int<> biRet = 1;
    for (const auto& ch : s) {
      if (' ' == ch) {
        biRet *= fac.Com(cnt);
        cnt.assign(26, 0);
      }
      else {
        cnt[ch - 'a']++;
      }
    }
    return biRet.ToInt();
  }
};

template<class T>
void Assert(const T& t1, const T& t2)
{
    assert(t1 == t2);
}
template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
    if (v1.size() != v2.size())
    {
        assert(false);
        return;
    }
    for (int i = 0; i < v1.size(); i++)
    {
        Assert(v1[i], v2[i]);
    }
}
int main()
{
  string s;
  {
    Solution sln;
    s = "too hot";
    auto res = sln.countAnagrams(s);
    Assert(18, res);
  }
  {
    Solution sln;
    s = "aa";
    auto res = sln.countAnagrams(s);
    Assert(1, res);
  }
  
}