【数位dp】【数论】【动态规划】2999. 统计强大整数的数目

class KMP
{
public:
  virtual int Find(const string& s, const string& t)
  {
    CalLen(t);
    m_vSameLen.assign(s.length(), 0);
    for (int i1 = 0, j = 0; i1 < s.length(); )
    {
      for (; (j < t.length()) && (i1 + j < s.length()) && (s[i1 + j] == t[j]); j++);
      //i2 = i1 + j 此时s[i1,i2)和t[0,j)相等 s[i2]和t[j]不存在或相等
      m_vSameLen[i1] = j;
      //t[0,j)的结尾索引是j-1，所以最长公共前缀为m_vLen[j-1]，简写为y 则t[0,y)等于t[j-y,j)等于s[i2-y,i2)
      if (0 == j)
      {
        i1++;
        continue;
      }
      const int i2 = i1 + j;
      j = m_vLen[j - 1];
      i1 = i2 - j;//i2不变
    }
    for (int i = 0; i < m_vSameLen.size(); i++)
    {//多余代码是为了增加可测试性
      if (t.length() == m_vSameLen[i])
      {
        return i;
      }
    }
    return -1;
  }
  vector<int> m_vSameLen;//m_vSame[i]记录 s[i...]和t[0...]最长公共前缀，增加可调试性
  static vector<int> Next(const string& s)
  {// j = vNext[i] 表示s[0,i]的最大公共前后缀是s[0,j]
    const int len = s.length();
    vector<int> vNext(len, -1);
    for (int i = 1; i < len; i++)
    {
      int next = vNext[i - 1];
      while ((-1 != next) && (s[next + 1] != s[i]))
      {
        next = vNext[next];
      }
      vNext[i] = next + (s[next + 1] == s[i]);
    }
    return vNext;
  }
protected:
  void CalLen(const string& str)
  {
    m_vLen.resize(str.length());
    for (int i = 1; i < str.length(); i++)
    {
      int next = m_vLen[i - 1];
      while (str[next] != str[i])
      {
        if (0 == next)
        {
          break;
        }
        next = m_vLen[next-1];
      }
      m_vLen[i] = next + (str[next] == str[i]);
    }
  }
  int m_c;
  vector<int> m_vLen;//m_vLen[i] 表示t[0,i]的最长公共前后缀 
};
template<class ELE, class ResultType, ELE minEle, ELE maxEle>
class CLowUperr
{
public:
  CLowUperr(int iCustomStatusCount) :m_iCustomStatusCount(iCustomStatusCount)
  {
  }
  void Init(const ELE* pLower, const ELE* pHigh, int iNum)
  {
    m_vPre.assign(4, vector<ResultType>(m_iCustomStatusCount));
    if (iNum <= 0)
    {
      return;
    }
    InitPre(pLower, pHigh);
    iNum--;
    while (iNum--)
    {
      pLower++;
      pHigh++;
      vector<vector<ResultType>> dp(4, vector<ResultType>(m_iCustomStatusCount));
      OnInitDP(dp);
      //处理非边界
      for (auto tmp = minEle; tmp <= maxEle; tmp++)
      {
        OnEnumOtherBit(dp[0], m_vPre[0], tmp);
      }
      //处理下边界
      OnEnumOtherBit(dp[1], m_vPre[1], *pLower);
      for (auto tmp = *pLower + 1; tmp <= maxEle; tmp++)
      {
        OnEnumOtherBit(dp[0], m_vPre[1], tmp);
      }
      //处理上边界
      OnEnumOtherBit(dp[2], m_vPre[2], *pHigh);
      for (auto tmp = minEle; tmp < *pHigh; tmp++)
      {
        OnEnumOtherBit(dp[0], m_vPre[2], tmp);
      }
      //处理上下边界
      if (*pLower == *pHigh)
      {
        OnEnumOtherBit(dp[3], m_vPre[3], *pLower);
      }
      else
      {
        OnEnumOtherBit(dp[1], m_vPre[3], *pLower);
        for (auto tmp = *pLower + 1; tmp < *pHigh; tmp++)
        {
          OnEnumOtherBit(dp[0], m_vPre[3], tmp);
        }
        OnEnumOtherBit(dp[2], m_vPre[3], *pHigh);
      }
      m_vPre.swap(dp);
    }
  }
  ResultType Sum(int iMinMask,int iMaxMask)const
  {
    ResultType iRet = 0;
    for (int status = 0; status < 4; status++)
    {
      for (int mask = iMinMask; mask <= iMaxMask; mask++)
      {
        iRet += m_vPre[status][mask];
      }
    }
    return iRet;
  }
protected:
  const int m_iCustomStatusCount;
  virtual void OnEnumOtherBit(vector<ResultType>& dp, const vector<ResultType>& vPre, ELE curValue) = 0;
  virtual void OnEnumFirstBit(vector<ResultType>& vPre, const ELE curValue) = 0;
  virtual void OnInitDP(vector<vector<ResultType>>& dp)
  {
  }
private:
  void InitPre(const ELE* const pLower, const ELE* const pHigh)
  {
    for (ELE cur = *pLower; cur <= *pHigh; cur++)
    {
      int iStatus = 0;
      if (*pLower == cur)
      {
        iStatus = *pLower == *pHigh ? 3 : 1;
      }
      else if (*pHigh == cur)
      {
        iStatus = 2;
      }
      OnEnumFirstBit(m_vPre[iStatus], cur);
    }
  }
  vector<vector<ResultType>> m_vPre;
};
class CMyLowUperr : public CLowUperr<char, long long, '0', '9'>
{
public:
  typedef  long long ResultType;
  typedef  char ELE;
  CMyLowUperr(int limit,const string& strEnd) :CLowUperr<char, long long, '0', '9'>(strEnd.length()+1),m_chLimit('0'+limit), m_strEnd(strEnd)
  {
    m_vNext = KMP::Next(strEnd);
  }
  virtual void OnEnumOtherBit(vector<ResultType>& dp, const vector<ResultType>& vPre, ELE curValue)
  {
    if (curValue > m_chLimit)
    {
      return;
    }
    for (int preMask = 0; preMask < m_iCustomStatusCount; preMask++)
    {
      const int mask = CalSameLen(preMask, curValue);
      dp[mask] += vPre[preMask];
    }
  }
  virtual void OnEnumFirstBit(vector<ResultType>& vPre, const ELE curValue)
  {
    if (curValue > m_chLimit)
    {
      return;
    }
    const int mask = CalSameLen(0, curValue);
    vPre[mask]++;
  }
protected:
  int CalSameLen(int oldLen, const ELE curValue)
  {
    while ((oldLen >= m_vNext.size()) || (curValue != m_strEnd[oldLen]))
    {
      if (0 == oldLen)
      {
        break;
      }
      oldLen = m_vNext[oldLen - 1]+1;
    }
    return oldLen + (curValue == m_strEnd[oldLen]);
  }
  const char m_chLimit;
  vector<int> m_vNext;
  const string m_strEnd;
};
class CNumBitHelp
{
public:
  CNumBitHelp(int limit, string strEnd):m_iLimt(limit),m_strEnd(strEnd)
  {
  }
  long long DoAllLen(long long low, long long high)
  {
    string strLow = std::to_string(low);
    string strHigh = std::to_string(high);
    long long iRet = 0;
    const int len1 = strLow.length();
    const int len2 = strHigh.length();
    if (len1 == len2)
    {
      return Do(strLow, strHigh);
    }
    iRet += Do(strLow, string(len1, '9'));
    for (int i = len1 + 1; i < len2; i++)
    {
      iRet += Do("1" + string(i - 1, '0'), string(i, '9'));
    }
    iRet += Do("1" + string(len2 - 1, '0'), strHigh);
    return iRet;
  }
protected:
  long long Do(const string strLow, const string& strHigh)
  {
    CMyLowUperr my(m_iLimt,m_strEnd);
    my.Init(strLow.data(), strHigh.data(), strLow.length());
    return my.Sum(m_strEnd.length(), m_strEnd.length());
  }
  const int m_iLimt;
  const string m_strEnd;
};
class Solution {
public:
  long long numberOfPowerfulInt(long long start, long long finish, int limit, string s) {
    CNumBitHelp hlp(limit, s);
    return hlp.DoAllLen(start, finish);
  }
};

template<class T, class T2>
void Assert(const T& t1, const T2& 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()
{
  
  int start = 1, finish = 6000, limit = 4;
  string s = "124";
  {
    start = 1, finish = 6000, limit = 4;
    s = "124";
    auto res = Solution().numberOfPowerfulInt(start, finish, limit, s);
    Assert(5, res);
  }
  {
    start = 15, finish = 215, limit = 6, s = "10";
    auto res = Solution().numberOfPowerfulInt(start, finish, limit, s);
    Assert(2, res);
  }
  {
    start = 1000, finish = 2000, limit = 4, s = "3000";
    auto res = Solution().numberOfPowerfulInt(start, finish, limit, s);
    Assert(0, res);
  }
}