【动态规划】【同余前缀和】【多重背包】[推荐]2902. 和带限制的子多重集合的数目

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;
  }
  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;;
};
class Solution {
public:
  int countSubMultisets(vector<int>& nums, int left, int r) {
    const int iMax = *std::max_element(nums.begin(), nums.end());
    vector<int> vCnt(1 + iMax);
    for (const auto& n : nums)
    {
      vCnt[n]++;
    }
    vector<C1097Int<>> vPre(r + 1);
    vPre[0] = 1;
    for (int i = iMax; i >= 0; i--)
    {
      if (0 == vCnt[i])
      {
        continue;
      }
      vector<C1097Int<>> dp(r + 1);
      if (0 == i)
      {
        for (int k = 0; k <= r; k++)
        {
          dp[k] = vPre[k] * (1 + vCnt[i]);
        }
      }
      else
      {
        for (int m = 0; m < i; m++)
        {
          C1097Int<> iiSum = 0;
          for (int k = m; k <= r; k += i)
          {
            iiSum += vPre[k];
            const int delIndex = k - (vCnt[i] + 1) * i;
            if (delIndex >= 0)
            {
              iiSum -= vPre[delIndex];
            }
            dp[k] = iiSum;
          }
        }
      }
      vPre.swap(dp);
    }
    C1097Int<> biRet = std::accumulate ( vPre.begin() + left, vPre.begin() + r + 1, C1097Int<>());
    return biRet.ToInt();
  }
};

emplate<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()
{
  vector<int> nums;
  int l,  r;
  {
    Solution sln;
    nums = { 1, 2, 2, 3 }, l = 6, r = 6;
    auto res = sln.countSubMultisets(nums, l, r);
    Assert(1, res);
  }
  {
    Solution sln;
    nums = { 2, 1, 4, 2, 7 }, l = 1, r = 5;
    auto res = sln.countSubMultisets(nums, l, r);
    Assert(7, res);
  }
  {
    Solution sln;
    nums = { 1, 2, 1, 3, 5, 2 }, l = 3, r = 5;
    auto res = sln.countSubMultisets(nums, l, r);
    Assert(9, res);
  }
}