链接

一、题目描述

给你两个 正 整数 n 和 x 。

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

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

比方说，n = 160 且 x = 3 ，一个表示 n 的方法是 n = 2³ + 3³ + 5³ 。

示例 1：

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

示例 2：

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

提示：

• 1 <= n <= 300

• 1 <= x <= 5

二、分析

分析题意，将n拆分为若干个正整数之和，求其方案数。

这些正整数的要求：另一正整数的x次幂。

1. 先求出正整数的集合，通过快速幂快速求解。

2. 直到集合后，转变为在有限集合里面取若干个，和为n的方案数，标准的0-1背包问题。

三、实现

const mod = 1_000_000_007

func numberOfWays(n int, x int) int {
	// 1. 拆分n次幂集合，范围[1,n] 利用快速幂求解
	pows := []int{}
	var (
		i   = 1
		pow = 0
	)
	for {
		pow = fastPow(i, x)
		if pow > n {
			break
		}
		pows = append(pows, pow)
		i++
	}
	// 2. 0-1背包求解和为n的方案数, f[i] 表示和为i的方案数
	f := make([]int, n+1)
	f[0] = 1
	for _, p := range pows {
		for i := n; i >= p; i-- {
			f[i] = (f[i] + f[i-p]) % mod
		}
	}
	return f[n]
}

func fastPow(a, b int) int {
	if b == 1 {
		return a
	}
	half := fastPow(a, b/2)
	if b&1 == 1 {
		return half * half * a
	}
	return half * half
}