class Solution {
public:
int sumOfPower(vector<int>& nums, int k) {
}
};
100241. 求出所有子序列的能量和
给你一个长度为 n 的整数数组 nums 和一个 正 整数 k 。
一个整数数组的 能量 定义为和 等于 k 的子序列的数目。
请你返回 nums 中所有子序列的 能量和 。
由于答案可能很大，请你将它对 109 + 7 取余 后返回。
示例 1：
输入： nums = [1,2,3], k = 3
输出： 6
解释：
总共有 5 个能量不为 0 的子序列：
[1,2,3] 有 2 个和为 3 的子序列：[1,2,3] 和 [1,2,3] 。[1,2,3] 有 1 个和为 3 的子序列：[1,2,3] 。[1,2,3] 有 1 个和为 3 的子序列：[1,2,3] 。[1,2,3] 有 1 个和为 3 的子序列：[1,2,3] 。[1,2,3] 有 1 个和为 3 的子序列：[1,2,3] 。所以答案为 2 + 1 + 1 + 1 + 1 = 6 。
示例 2：
输入： nums = [2,3,3], k = 5
输出： 4
解释：
总共有 3 个能量不为 0 的子序列：
[2,3,3] 有 2 个子序列和为 5 ：[2,3,3] 和 [2,3,3] 。[2,3,3] 有 1 个子序列和为 5 ：[2,3,3] 。[2,3,3] 有 1 个子序列和为 5 ：[2,3,3] 。所以答案为 2 + 1 + 1 = 4 。
示例 3：
输入： nums = [1,2,3], k = 7
输出： 0
解释：不存在和为 7 的子序列，所以 nums 的能量和为 0 。
提示：
1 <= n <= 1001 <= nums[i] <= 1041 <= k <= 100原站题解
java 解法, 执行用时: 1 ms, 内存消耗: 41.6 MB, 提交时间: 2024-03-19 20:12:54
class Solution {
public int sumOfPower2(int[] nums, int k) {
final int MOD = 1_000_000_007;
int n = nums.length;
int[][] f = new int[k + 1][n + 1];
f[0][0] = 1;
for (int i = 0; i < n; i++) {
for (int j = k; j >= nums[i]; j--) {
for (int c = i + 1; c > 0; c--) {
f[j][c] = (f[j][c] + f[j - nums[i]][c - 1]) % MOD;
}
}
}
long ans = 0;
int pow2 = 1;
for (int i = n; i > 0; i--) {
ans = (ans + (long) f[k][i] * pow2) % MOD;
pow2 = pow2 * 2 % MOD;
}
return (int) ans;
}
public int sumOfPower(int[] nums, int k) {
long[] f = new long[k + 1];
f[0] = 1;
for (int x : nums) {
for (int j = k; j >= 0; j--) {
f[j] = (f[j] * 2 + (j >= x ? f[j - x] : 0)) % 1_000_000_007;
}
}
return (int) f[k];
}
}
golang 解法, 执行用时: 0 ms, 内存消耗: 2.7 MB, 提交时间: 2024-03-19 20:12:14
func sumOfPower(nums []int, k int) int {
const mod = 1_000_000_007
f := make([]int, k+1)
f[0] = 1
for _, x := range nums {
for j := k; j >= 0; j-- {
if j >= x {
f[j] = (f[j]*2 + f[j-x]) % mod
} else {
f[j] = f[j] * 2 % mod
}
}
}
return f[k]
}
func sumOfPower2(nums []int, k int) (ans int) {
const mod = 1_000_000_007
n := len(nums)
f := make([][]int, k+1)
for i := range f {
f[i] = make([]int, n+1)
}
f[0][0] = 1
for i, x := range nums {
for j := k; j >= x; j-- {
for c := i + 1; c > 0; c-- {
f[j][c] = (f[j][c] + f[j-x][c-1]) % mod
}
}
}
pow2 := 1
for i := n; i > 0; i-- {
ans = (ans + f[k][i]*pow2) % mod
pow2 = pow2 * 2 % mod
}
return
}
python3 解法, 执行用时: 68 ms, 内存消耗: 16.4 MB, 提交时间: 2024-03-19 20:11:46
class Solution:
# 定义 f[i][j][c] 表示考虑前 i 个物品，所选物品体积和是 j，选了 c 个物品的方案数。
def sumOfPower1(self, nums: List[int], k: int) -> int:
MOD = 1_000_000_007
n = len(nums)
f = [[0] * (n + 1) for _ in range(k + 1)]
f[0][0] = 1
for i, x in enumerate(nums):
for j in range(k, x - 1, -1):
for c in range(i + 1, 0, -1):
f[j][c] = (f[j][c] + f[j - x][c - 1]) % MOD
ans = 0
pow2 = 1
for i in range(n, 0, -1):
ans = (ans + f[k][i] * pow2) % MOD
pow2 = pow2 * 2 % MOD
return ans
# 定义 f[i][j] 表示考虑前 i 个数，所选元素和是 j 时的能量和。
def sumOfPower(self, nums: List[int], k: int) -> int:
f = [1] + [0] * k
for x in nums:
for j in range(k, -1, -1):
f[j] = (f[j] * 2 + (f[j - x] if j >= x else 0)) % 1_000_000_007
return f[k]