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

给你两个正整数 n 和 x 。

请你返回将 _ _n 表示成一些 互不相同 正整数的 _ _x 次幂之和的方案数。换句话说，你需要返回互不相同整数 [n1, n2, ..., nk] 的集合数目，满足 n = n1x + n2x + ... + nkx 。

由于答案可能非常大，请你将它对 109 + 7 取余后返回。

比方说，n = 160 且 x = 3 ，一个表示 n 的方法是 n = 23 + 33 + 53 。

示例 1：

**输入：** n = 10, x = 2
**输出：** 1
**解释：** 我们可以将 n 表示为：n = 32 + 12 = 10 。
这是唯一将 10 表达成不同整数 2 次方之和的方案。

示例 2：

**输入：** n = 4, x = 1
**输出：** 2
**解释：** 我们可以将 n 按以下方案表示：
- n = 41 = 4 。
- n = 31 + 11 = 4 。

提示：

1 <= n <= 300
1 <= x <= 5

把 n 看成背包容量，n_i^x 看成物品，本题就是一个 0-1 背包模板题，具体请看【基础算法精讲 18】。如果这个视频对你有帮助，欢迎一键三连！

代码实现时，由于 n=300,x=1 算出来的结果不超过 64 位整数的最大值，所以可以在计算结束后再取模。

[sol-Python3]MX_N, MX_X = 300, 5
f = [[1] + [0] * MX_N for _ in range(MX_X)]
for x in range(MX_X):
    for i in count(1):
        v = i ** (x + 1)
        if v > MX_N: break
        for s in range(MX_N, v - 1, -1):
            f[x][s] += f[x][s - v]

class Solution:
    def numberOfWays(self, n: int, x: int) -> int:
        return f[x - 1][n] % (10 ** 9 + 7)

[sol-Go]func numberOfWays(n, x int) int {
	f := make([]int, n+1)
	f[0] = 1
	for i := 1; pow(i, x) <= n; i++ {
		v := pow(i, x)
		for s := n; s >= v; s-- {
			f[s] += f[s-v]
		}
	}
	return f[n] % (1e9 + 7)
}

func pow(x, n int) int {
	res := 1
	for ; n > 0; n /= 2 {
		if n%2 > 0 {
			res = res * x
		}
		x = x * x
	}
	return res
}

复杂度分析

时间复杂度：\mathcal{O}(n^2\log x)。
空间复杂度：\mathcal{O}(n)。

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

复杂度分析

相似题目