题目
6364. 无平方子集计数
给你一个正整数数组 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 个无平方子集。
|
示例 2：
1
2
3
4
5
| 输入：nums = [1]
输出：1
解释：示例中有 1 个无平方子集：
- 由第 0 个元素 [1] 组成的子集。其元素的乘积是 1 ，这是一个无平方因子数。
可以证明给定数组中不存在超过 1 个无平方子集。
|
提示：
-
1 <= nums.length <= 1000
1 <= nums[i] <= 30
题解
方法一：
思路
我们考虑每个数的质因数分解。
如果一个数有两个相同的质因数则说明这个数是非无平方因子数。
无平方因子数的质因子每种只有一个，注意到每个数的大小不超过30，30内质数只有10个。
我们用10位二进制数表示一个数质因子出现情况。
$f_{i,j}$为前i个数中选取若干个使得乘积为j的选取种数。
$f_{0,0} = 1$
对于第i个数考虑选和不选。
不选，$f_{i,j}$由$f_{i-1,j}$转移。
选择，当$j \cap mask_i = \varnothing$时，$f_{i,j|mask_i}$由$f_{i-1,j}+1$贡献，$mask_i$是第i个数的质因数集合表示，若存在多个相同的质因数则设置为不存在。
1
2
3
4
5
6
7
8
9
10
11
12
13
| ll f[n+1][1<<10]; memset(f, 0, sizeof(f));
f[0][0] = 1;
for (int i=1; i<=n; i++) {
for (int j=0; j<1024; j++) {
f[i][j] = f[i-1][j];
}
for (int j=0; j<1024; j++) {
if (mask[i-1]>=0 && (j & mask[i-1]) == 0) {
f[i][j|mask[i-1]] += f[i-1][j];
f[i][j|mask[i-1]] %= MOD;
}
}
}
|
或者$f_{i,j}$由$f_{i-1, j-mask_i}+1$转移，$j-mask_i$集合$j$移除集合$mask_i$，也就是说要保证$mask_i \in j$
即$f_{i,j} = f_{i-1, j} + f_{i-1, j-mask_i}$，和01背包几乎一样。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| ll f[n+1][1<<10]; memset(f, 0, sizeof(f));
f[0][0] = 1;
for (int i=1; i<=n; i++) {
for (int j=0; j<1024; j++) {
f[i][j] = f[i-1][j];
if (mask[i-1]>=0 && (j | mask[i-1]) == j) {
f[i][j] += f[i-1][j^mask[i-1]];
f[i][j] %= MOD;
}
}
}
|
由于我们用一个二进制数表示集合，当一个集合a是另一个集合b的子集时，所代表的二进制数同样a < b。基于这一点我们可以类似01背包用滚动数组以减小空间复杂度。
1
2
3
4
5
6
7
8
9
10
| ll f[1<<10]; memset(f, 0, sizeof(f));
f[0] = 1;
for (int i=1; i<=n; i++) {
for (int j=1023; j>=0; j--) {
if (mask[i-1]>=0 && (j | mask[i-1]) == j) {
f[j] += f[j^mask[i-1]];
f[j] %= MOD;
}
}
}
|
最后$-1+\sum\limits_{j=0}^{1023}f_{n, j}$
代码
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
43
44
| class Solution {
public:
using ll = long long;
const ll MOD = 1e9+7;
int squareFreeSubsets(vector<int>& nums) {
vector<int> p = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
int n = nums.size();
vector<int> mask(n);
for (int i=0; i<n; i++) {
int ok = 1;
for (int j=0; j<10; j++) {
if (nums[i] % (p[j] * p[j]) == 0) {
ok = 0;
break;
}
while (nums[i] % p[j] == 0) {
mask[i] |= 1<<j;
nums[i] /= p[j];
}
}
if (!ok) mask[i] = -1;
}
ll f[n+1][1<<10]; memset(f, 0, sizeof(f));
f[0][0] = 1;
for (int i=1; i<=n; i++) {
for (int j=0; j<1024; j++) {
f[i][j] = f[i-1][j];
}
for (int j=0; j<1024; j++) {
if (mask[i-1]>=0 && (j & mask[i-1]) == 0) {
f[i][j|mask[i-1]] += f[i-1][j];
f[i][j|mask[i-1]] %= MOD;
}
}
}
int ans = 0;
for (int i=0; i<1024; i++) {
ans += f[n][i];
ans %= MOD;
}
return (ans-1+MOD)%MOD;
}
};
|
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 {
public:
using ll = long long;
const ll MOD = 1e9+7;
int squareFreeSubsets(vector<int>& nums) {
vector<int> p = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
int n = nums.size();
vector<int> mask(n);
for (int i=0; i<n; i++) {
int ok = 1;
for (int j=0; j<10; j++) {
if (nums[i] % (p[j] * p[j]) == 0) {
ok = 0;
break;
}
while (nums[i] % p[j] == 0) {
mask[i] |= 1<<j;
nums[i] /= p[j];
}
}
if (!ok) mask[i] = -1;
}
ll f[1<<10]; memset(f, 0, sizeof(f));
f[0] = 1;
for (int i=1; i<=n; i++) {
for (int j=1023; j>=0; j--) {
if (mask[i-1]>=0 && (j | mask[i-1]) == j) {
f[j] += f[j^mask[i-1]];
f[j] %= MOD;
}
}
}
int ans = 0;
for (int i=0; i<1024; i++) {
ans += f[i];
ans %= MOD;
}
return (ans-1+MOD)%MOD;
}
};
|