Medium
题目描述
给你一个正整数数组 nums。
如果数组 nums 的一个子集中，所有元素的乘积是一个无平方因子数，则该子集称为 无平方子集 。
无平方因子数是指不能被除 1 之外任何平方数整除的整数。
返回数组 nums 中 无平方非空子集 的数目。因为答案可能很大，返回对 10^9 + 7 取余的结果。
nums 的非空子集是可以由删除 nums 中一些元素（可能不删除，但不能全部删除）得到的数组。只有选择删除元素的下标不同，两个子集才不同。
示例 1：
输入：nums = [3,4,4,5]
输出：3
解释：示例中有 3 个无平方子集：
- 由第 0 个元素 [3] 组成的子集。元素乘积为 3 ，这是一个无平方因子数。
- 由第 3 个元素 [5] 组成的子集。元素乘积为 5 ，这是一个无平方因子数。
- 由第 0 和第 3 个元素 [3,5] 组成的子集。元素乘积为 15 ，这是一个无平方因子数。
可以证明给定数组中不存在超过 3 个无平方子集。
示例 2：
输入：nums = [1]
输出：1
解释：示例中有 1 个无平方子集：
- 由第 0 个元素 [1] 组成的子集。元素乘积为 1 ，这是一个无平方因子数。
可以证明给定数组中不存在超过 1 个无平方子集。
提示：
1 <= nums.length <= 10001 <= nums[i] <= 30
解题思路
这是一道动态规划 + 位运算的经典题目。
核心思路：
预处理阶段：由于数组元素范围只有 1-30，我们需要找出 30 以内的所有质数（2,3,5,7,11,13,17,19,23,29 共10个），并为每个数字计算其质因子的位掩码表示。
状态设计：使用
dp[mask]表示当前已选质数集合为mask的无平方子集数目。由于只有 10 个质数，所以mask的范围是 0 到 1023。转移方程：对于每个数字，如果它与当前状态
mask没有公共质因子（即按位与为0），则可以将其加入当前子集，状态转移为dp[mask | num_mask] += dp[mask]。特殊处理：数字 1 比较特殊，它可以加入任何子集而不影响无平方性质，所以最终答案需要乘以
2^count_of_1。
算法步骤：
- 预处理得到每个数字的质因子位掩码
- 过滤掉包含平方因子的数字（如4,8,9等）
- 动态规划计算各种质因子组合的方案数
- 处理数字1的贡献并返回最终结果
代码实现
class Solution {
public:
int squareFreeSubsets(vector<int>& nums) {
const int MOD = 1e9 + 7;
vector<int> primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
// 预处理每个数字的质因子掩码
vector<int> masks(31, -1);
masks[1] = 0;
for (int i = 2; i <= 30; i++) {
int mask = 0;
int temp = i;
bool isSquareFree = true;
for (int j = 0; j < 10; j++) {
int cnt = 0;
while (temp % primes[j] == 0) {
temp /= primes[j];
cnt++;
}
if (cnt > 1) {
isSquareFree = false;
break;
}
if (cnt == 1) {
mask |= (1 << j);
}
}
if (isSquareFree && temp == 1) {
masks[i] = mask;
}
}
// 统计各种数字的频次
vector<int> count(31, 0);
for (int num : nums) {
count[num]++;
}
// 动态规划
vector<long long> dp(1024, 0);
dp[0] = 1;
for (int i = 2; i <= 30; i++) {
if (masks[i] == -1 || count[i] == 0) continue;
vector<long long> newDp = dp;
int mask = masks[i];
for (int state = 0; state < 1024; state++) {
if (dp[state] == 0) continue;
if ((state & mask) == 0) {
newDp[state | mask] = (newDp[state | mask] + dp[state] * count[i]) % MOD;
}
}
dp = newDp;
}
long long result = 0;
for (int i = 0; i < 1024; i++) {
result = (result + dp[i]) % MOD;
}
// 处理数字1
long long power = 1;
for (int i = 0; i < count[1]; i++) {
power = (power * 2) % MOD;
}
return (result * power - 1 + MOD) % MOD;
}
};
class Solution:
def squareFreeSubsets(self, nums: List[int]) -> int:
MOD = 10**9 + 7
primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
# 预处理每个数字的质因子掩码
masks = [-1] * 31
masks[1] = 0
for i in range(2, 31):
mask = 0
temp = i
is_square_free = True
for j, prime in enumerate(primes):
cnt = 0
while temp % prime == 0:
temp //= prime
cnt += 1
if cnt > 1:
is_square_free = False
break
if cnt == 1:
mask |= (1 << j)
if is_square_free and temp == 1:
masks[i] = mask
# 统计各种数字的频次
count = [0] * 31
for num in nums:
count[num] += 1
# 动态规划
dp = [0] * 1024
dp[0] = 1
for i in range(2, 31):
if masks[i] == -1 or count[i] == 0:
continue
new_dp = dp[:]
mask = masks[i]
for state in range(1024):
if dp[state] == 0:
continue
if (state & mask) == 0:
new_dp[state | mask] = (new_dp[state | mask] + dp[state] * count[i]) % MOD
dp = new_dp
result = sum(dp) % MOD
# 处理数字1
power = pow(2, count[1], MOD)
return (result * power - 1) % MOD
public class Solution {
public int SquareFreeSubsets(int[] nums) {
const int MOD = 1000000007;
int[] primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
// 预处理每个数字的质因子掩码
int[] masks = new int[31];
Array.Fill(masks, -1);
masks[1] = 0;
for (int i = 2; i <= 30; i++) {
int mask = 0;
int temp = i;
bool isSquareFree = true;
for (int j = 0; j < 10; j++) {
int cnt = 0;
while (temp % primes[j] == 0) {
temp /= primes[j];
cnt++;
}
if (cnt > 1) {
isSquareFree = false;
break;
}
if (cnt == 1) {
mask |= (1 << j);
}
}
if (isSquareFree && temp == 1) {
masks[i] = mask;
}
}
// 统计各种数字的频次
int[] count = new int[31];
foreach (int num in nums) {
count[num]++;
}
// 动态规划
long[] dp = new long[1024];
dp[0] = 1;
for (int i = 2; i <= 30; i++) {
if (masks[i] == -1 || count[i] == 0) continue;
long[] newDp = new long[1024];
Array.Copy(dp, newDp, 1024);
int mask = masks[i];
for (int state = 0; state < 1024; state++) {
if (dp[state] == 0) continue;
if ((state & mask) == 0) {
newDp[state | mask] = (newDp[state | mask] + dp[state] * count[i]) % MOD;
}
}
dp = newDp;
}
long result = 0;
for (int i = 0; i < 1024; i++) {
result = (result + dp[i]) % MOD;
}
// 处理数字1
long power = 1;
for (int i = 0; i < count[1]; i++) {
power = (power * 2) % MOD;
}
return (int)((result * power - 1 + MOD) % MOD);
}
}
var squareFreeSubsets = function(nums) {
const MOD = 1000000007;
const primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29];
function getMask(num) {
let mask = 0;
for (let i = 0; i < primes.length; i++) {
let count = 0;
while (num % primes[i] === 0) {
num /= primes[i];
count++;
}
if (count > 1) return -1;
if (count === 1) mask |= (1 << i);
}
return mask;
}
const count = new Map();
for (let num of nums) {
const mask = getMask(num);
if (mask !== -1) {
count.set(mask, (count.get(mask) || 0) + 1);
}
}
const dp = new Array(1024).fill(0);
dp[0] = 1;
for (let [mask, freq] of count) {
if (mask === 0) {
for (let i = 0; i < 1024; i++) {
dp[i] = (dp[i] * (freq + 1)) % MOD;
}
} else {
for (let i = 1023; i >= 0; i--) {
if ((i & mask) === 0) {
dp[i | mask] = (dp[i | mask] + dp[i] * freq) % MOD;
}
}
}
}
let result = 0;
for (let i = 1; i < 1024; i++) {
result = (result + dp[i]) % MOD;
}
return result;
};
复杂度分析
| 复杂度 | 大小 |
|---|---|
| 时间复杂度 | O(n + 30 × 2^10) |
| 空间复杂度 | O(2^10) |
说明：
- 时间复杂度：O(n) 用于统计数字频次，O(30 × 2^10) 用于动态规划转移，其中 30 是数字范围，2^10 是状态数量
- 空间复杂度：O(2^10) 用于存储 dp 数组，因为有 10 个质数，所以状态总数为 2^10 = 1024