LC-2572.无平方子集计数

题目描述

leetcode 困难题

给你一个正整数数组 nums 。

如果数组 nums 的子集中的元素乘积是一个 无平方因子数 ,则认为该子集是一个 无平方 子集。

无平方因子数 是无法被除 1 之外任何平方数整除的数字。

返回数组 nums 中 无平方 且 非空 的子集数目。因为答案可能很大,返回对 10^9 + 7 取余的结果。

nums 的 非空子集 是可以由删除 nums 中一些元素(可以不删除,但不能全部删除)得到的一个数组。如果构成两个子集时选择删除的下标不同,则认为这两个子集不同。

示例1:

1
2
3
4
5
6
7
输入:nums = [3,4,4,5]
输出:3
解释:示例中有 3 个无平方子集:
- 由第 0 个元素 [3] 组成的子集。其元素的乘积是 3 ,这是一个无平方因子数。
- 由第 3 个元素 [5] 组成的子集。其元素的乘积是 5 ,这是一个无平方因子数。
- 由第 0 个和第 3 个元素 [3,5] 组成的子集。其元素的乘积是 15 ,这是一个无平方因子数。
可以证明给定数组中不存在超过 3 个无平方子集。

提示1:

1
2
1 <= nums.length <= 1000
1 <= nums[i] <= 30

状压 DP

首先需要排除类似 $4, 8, 9, 16…$ 这些自身就能被平方数整除的数,接下来再继续考虑子集乘积能否被平方数整除。

两个数的乘积能被某个平方数整除,说明它们的 $GCD$ 不为 $1$ ,换种说法就是存在相同的因数,由于 $num[i] <= 30$ 且上面我们已经排除了部分数,其实也就是说它们的因数中以下这些值 $[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]$ 不能出现两次或以上,设该列表为 $list$。

定义 $dp[i][j]$ 表示 前 $i - 1$ 个数中,因数出现情况为 $j$ 的子集的数量,其中 $j$ 的某一位为 $1$ ,说明 $list$ 的某一位作为子集的因数已经出现过,那么就有

$$
\begin{align}
&dp(i, j | mask) = dp[i - 1][j | mask] + dp[i - 1][j]                if mask \& j == 0\
\end{align}
$$

转移过程中 $dp[i - 1][j | mask]$ 表示第 $i$ 个元素不选,$dp[i - 1][j]$ 表示 $dp[i - 1][j]$ 状态下选第 $i$ 个数转移到 $j | mask$。

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
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
private final int MOD = (int) (1e9 + 7);

public int squareFreeSubsets(int[] nums) {
List<Integer> list = List.of(2, 3, 5, 7, 11, 13, 17, 19, 23, 29);
int n = nums.length;
long[][] dp = new long[n + 1][1 << 10];
dp[0][0] = 1;
Predicate<Integer> vaild = a -> {
for(int j = 2; j <= 5; j++){
if(a % (j * j) == 0){
return false;
}
}
return true;
};
for (int i = 1; i < n + 1; i++) {
for(int j = 0; j < (1 << 10); j++){
dp[i][j] = dp[i - 1][j];
}
if(!vaild.test(nums[i - 1])){
continue;
}
int mask = 0;
for (int k = 0; k < list.size(); k++) {
if (nums[i - 1] % list.get(k) == 0) {
mask |= (1 << k);
}
}
for (int j = 0; j < (1 << 10); j++) {
if ((mask & j) == 0) {
dp[i][j | mask] = (dp[i][j | mask] + dp[i - 1][j]) % MOD;
}
}
}
long ans = 0;
for (long item : dp[n]) {
ans = (ans + item) % MOD;
}
return (int) (ans - 1 + MOD) % MOD;
}
}

LC-2572.无平方子集计数
https://wecgwm.github.io/2023/02/21/LC-2572-无平方子集计数/
作者
yichen
发布于
2023年2月21日
许可协议