3082. 求出所有子序列的能量和

发表于 分类于 阅读次数： Waline： 本文字数： 1k 阅读时长 ≈ 3 分钟

考点

  • 01背包
  • 滚动数组
  • 计数DP

思路

可以发现，对于一个和等于K的序列，它对结果产生的贡献为2 ^ (n - 序列长度)

比如对于{1, 2, 2, 3}, K = 4，显然{2, 2}满足条件，那么由它延伸可以得到{2, 2}、{1, 2, 2}、{2, 2, 3}、{1, 2, 2, 3}四种序列，那么产生的贡献就是2 ^ (4 - 2) = 4

由此很容易设计状态转移方程：

1
2
3
4
f[i][j][k]: 考虑前i个数，序列和为j、且序列长度为k的个数
使用Push方向, 即已知f[i]，考虑对f[i+1]的转移
不选nums[i+1], f[i+1][j][k] += f[i][j][k]
选nums[i+1], f[i+1][j+nums[i+1]][k+1] += f[i][j][k]

得到第一版AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
 public:
  static const int maxn = 1e2 + 50, mod = 1e9 + 7;
  // f[i][j][k]：前i个数凑成的，和为j、长度为k的序列个数
  int n;
  long long f[maxn][maxn][maxn];
  long long ksm(long long x, int y) {
    long long res = 1;
    while (y) {
      if (y & 1) res = res * x % mod;
      x = x * x % mod;
      y >>= 1;
    }
    return res;
  }
  int sumOfPower(vector<int>& nums, int K) {
    n = nums.size();
    memset(f, 0, sizeof(f));
    f[0][0][0] = 1;
    for (int i = 0; i < n; ++i) {
      int x = nums[i];
      for (int j = 0; j <= K; ++j) {
        for (int k = 0; k <= i; ++k) {
          f[i + 1][j][k] = (f[i + 1][j][k]+f[i][j][k])%mod;
          if (j + x <= K) f[i + 1][j + x][k + 1] = (f[i + 1][j + x][k + 1]+f[i][j][k])%mod;
        }
      }
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i)
      ans = (ans + (1LL * f[n][K][i] * ksm(2, n - i) % mod)) % mod;
    return ans;
  }
};

这里可以原地滚动数组去掉第一维，降低常数开销：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
 public:
  static const int maxn = 1e2 + 50, mod = 1e9 + 7;
  // f[i][j][k]：前i个数凑成的，和为j、长度为k的序列个数
  int n;
  long long f[maxn][maxn];
  long long ksm(long long x, int y) {
    long long res = 1;
    while (y) {
      if (y & 1) res = res * x % mod;
      x = x * x % mod;
      y >>= 1;
    }
    return res;
  }
  int sumOfPower(vector<int>& nums, int K) {
    n = nums.size();
    memset(f, 0, sizeof(f));
    f[0][0] = 1;
    for (int i = 0; i < n; ++i) {
      int x = nums[i];
      for (int j = K; j >= 0; --j) {
        for (int k = 0; k <= i; ++k) {
          if (j + x <= K) f[j + x][k + 1] = (f[j + x][k + 1] + f[j][k]) % mod;
        }
      }
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i)
      ans = (ans + (1LL * f[K][i] * ksm(2, n - i) % mod)) % mod;
    return ans;
  }
};

这样还是慢了，通过观察可以发现，压根不需要记录序列长度那一维：

1
2
3
4
5
6
7
8
9
10
f[i][j]: 前i个数, 考虑所有和为j的序列，记录它们的2 ^ (i - 序列长度)之和
假设现在的f[i][j]记录的是两个序列:
1 3
1 1 2
同样是Push方向，考虑对f[i+1]的转移
若nums[i+1]并不加入到当前序列，只是用以重排列，那么f[i+1][j] += f[i][j] * 2
这是显然的，因为{1, 3}可以变成{1, 3, 不选nums[i+1]}和{1, 3, nums[i+1]}两种状态
若nums[i+1]加入当前序列, f[i+1][j+nums[i+1]] += f[i][j]
这是显然的，之前是{1, 3}, 一共n个数, 贡献就是2 ^ (n - 2)
而现在是{1, 3, nums[i+1]}, 一共n+1个数, 贡献就是2 ^ (n + 1 - (2 + 1)) = 2 ^ (n - 2), 并没有变

得到第二版代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
 public:
  static const int maxn = 1e2 + 50, mod = 1e9 + 7;
  // f[i][j]：考虑前i个数，对于所有和为j的序列，记录它们2^(i-其序列长度)的和
  int n;
  long long f[maxn][maxn];
  int sumOfPower(vector<int>& nums, int K) {
    n = nums.size();
    memset(f, 0, sizeof(f));
    f[0][0] = 1;
    for (int i = 0; i < n; ++i) {
      for (int j = K; j >= 0; --j) {
        f[i + 1][j] = (f[i + 1][j] + f[i][j] * 2 % mod) % mod;
        if (j + nums[i] <= K)
          f[i + 1][j + nums[i]] = (f[i + 1][j + nums[i]] + f[i][j]) % mod;
      }
    }
    return f[n][K];
  }
};

当然，这里同样可以使用滚动数组，时间和空间效率拉到极致：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
 public:
  static const int maxn = 1e2 + 50, mod = 1e9 + 7;
  int n;
  long long f[maxn];
  int sumOfPower(vector<int>& nums, int K) {
    n = nums.size(), memset(f, 0, sizeof(f));
    f[0] = 1;
    for (int i = 0; i < n; ++i) {
      for (int j = K; j >= 0; --j) {
        if (j + nums[i] <= K) f[j + nums[i]] = (f[j + nums[i]] + f[j]) % mod;
        f[j] = f[j] * 2 % mod;
      }
    }
    return f[K];
  }
};