【动态规划 状态机dp】3082. 求出所有子序列的能量和

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;
  }
  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 sumOfPower(vector<int>& nums, int k) {
    vector<vector<C1097Int<>>> pre(nums.size()+1,vector<C1097Int<>>( k + 1));
    pre[0][0] = 1;
    for (const auto& n : nums) {
      auto dp = pre;
      for (int len = 0; len+1 <= nums.size(); len++) {
        for (int iPre = 0; iPre <= k; iPre++) {
          const int iNew = iPre + n;
          if (iNew > k) { continue; }
          dp[len+1][iNew] += pre[len][iPre];
        }
      }     
      pre.swap(dp);
    }
    C1097Int<> biRet;
    for (int i = 1; i <= nums.size(); i++) {
      biRet += pre[i].back() * C1097Int(2).pow(nums.size()-i);
    }
    return biRet.ToInt();
  }
};