2787. 将一个数字表示成幂的和的方案数

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

考点

  • 01背包

思路

01背包的裸题，枚举1 ~ n的x次幂，看看能不能凑出n即可

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
class Solution {
 public:
  static const int mod = 1e9 + 7;
  long long ksm(long long x, int y) {
    long long s = 1;
    while (y) {
      if (y & 1) s = s * x % mod;
      x = x * x % mod;
      y >>= 1;
    }
    return s;
  }
  int numberOfWays(int n, int x) {
    // 打表, 1~n的x次幂
    long long pw[301];
    for (int i = 1; i <= n; ++i) pw[i] = ksm(i, x);
    // 01背包板子
    long long f[301][301];
    memset(f, 0, sizeof(f));
    f[0][0] = 1;
    for (int i = 1; i <= n; ++i) {
      for (int j = 0; j <= 300; ++j) {
        f[i][j] = (f[i][j] + f[i - 1][j]) % mod;
        if (j >= pw[i]) f[i][j] = (f[i][j] + f[i - 1][j - pw[i]]) % mod;
      }
    }
    return f[n][n];
  }
};

也可以滚掉第一维

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
class Solution {
 public:
  static const int mod = 1e9 + 7;
  long long ksm(long long x, int y) {
    long long s = 1;
    while (y) {
      if (y & 1) s = s * x % mod;
      x = x * x % mod;
      y >>= 1;
    }
    return s;
  }
  int numberOfWays(int n, int x) {
    // 打表, 1~n的x次幂
    long long pw[301];
    for (int i = 1; i <= n; ++i) pw[i] = ksm(i, x);
    // 01背包板子
    long long f[301];
    memset(f, 0, sizeof(f));
    f[0] = 1;
    for (int i = 1; i <= n; ++i) {
      for (int j = 300; j >= pw[i]; --j) {
        f[j] = (f[j] + f[j - pw[i]]) % mod;
      }
    }
    return f[n];
  }
};