- 标签:位运算、数组、数学、动态规划、状态压缩
- 难度:困难
描述:给定一个整数数组
要求:返回
说明:
-
子集:通过删除
$nums$ 中一些(可能一个都不删除,也可能全部都删除)元素后剩余元素组成的数组。如果两个子集删除的下标不同,那么它们被视为不同的子集。 -
好子集:如果
$nums$ 的一个子集中,所有元素的乘积可以表示为一个或多个互不相同的质数的乘积,那么我们称它为好子集。- 比如,如果
$nums = [1, 2, 3, 4]$ :-
$[2, 3]$ ,$[1, 2, 3]$ 和$[1, 3]$ 是好子集,乘积分别为$6 = 2 \times 3$ ,$6 = 2 \times 3$ 和$3 = 3$ 。 -
$[1, 4]$ 和$[4]$ 不是好子集,因为乘积分别为$4 = 2 \times 2$ 和$4 = 2 \times 2$ 。
-
- 比如,如果
-
$1 \le nums.length \le 10^5$ 。 -
$1 \le nums[i] \le 30$ 。
示例:
- 示例 1:
输入:nums = [1,2,3,4]
输出:6
解释:好子集为:
- [1,2]:乘积为 2,可以表示为质数 2 的乘积。
- [1,2,3]:乘积为 6,可以表示为互不相同的质数 2 和 3 的乘积。
- [1,3]:乘积为 3,可以表示为质数 3 的乘积。
- [2]:乘积为 2,可以表示为质数 2 的乘积。
- [2,3]:乘积为 6,可以表示为互不相同的质数 2 和 3 的乘积。
- [3]:乘积为 3,可以表示为质数 3 的乘积。
- 示例 2:
输入:nums = [4,2,3,15]
输出:5
解释:好子集为:
- [2]:乘积为 2,可以表示为质数 2 的乘积。
- [2,3]:乘积为 6,可以表示为互不相同质数 2 和 3 的乘积。
- [2,15]:乘积为 30,可以表示为互不相同质数 2,3 和 5 的乘积。
- [3]:乘积为 3,可以表示为质数 3 的乘积。
- [15]:乘积为 15,可以表示为互不相同质数 3 和 5 的乘积。
根据题意可以看出:
- 虽然
$nums$ 的长度是$[1, 10^5]$ ,但是其值域范围只有$[1, 30]$ ,则我们可以将$[1, 30]$ 的数分为$3$ 类:- 质数:$[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]$(共
$10$ 个数)。由于好子集的乘积拆解后的质因子只能包含这$10$ 个,我们可以使用一个数组$primes$ 记录下这$10$ 个质数,将好子集的乘积拆解为质因子后,每个$primes[i]$ 最多出现一次。 - 非质数:$[4, 6, 8, 9, 10, 12, 14, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28, 30]$。非质数肯定不会出现在好子集的乘积拆解后的质因子中。
- 特殊的数:$[1]$。对于一个好子集而言,无论向中间添加多少个
$1$ ,得到的新子集仍是好子集。
- 质数:$[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]$(共
- 分类完成后,由于
$[1, 30]$ 中只有$10$ 个质数,因此我们可以使用一个长度为$10$ 的二进制数$state$ 来表示$primes$ 中质因数的选择情况。其中,如果$state$ 第$i$ 位为$1$ ,则说明第$i$ 个质因数$primes[i]$ 被使用过;如果$state$ 第$i$ 位为$0$ ,则说明第$i$ 个质因数$primes[i]$ 没有被使用过。 - 题目规定值相同,但是下标不同的子集视为不同子集,那么我们可先统计出
$nums$ 中每个数$nums[i]$ 的出现次数,将其存入$cnts$ 数组中,其中$cnts[num]$ 表示$num$ 出现的次数。这样在统计方案时,直接计算出$num$ 的方案数,再乘以$cnts[num]$ 即可。
接下来,我们就可以使用「动态规划」的方式来解决这道题目了。
按照质因数的选择情况进行阶段划分。
定义状态
对于
此时,状态转移方程为:$dp[state | cur\underline{\hspace{0.5em}}state] = \sum (dp[state] \times cnt) \mod MOD , \quad state \text{ & } cur\underline{\hspace{0.5em}}state == 0$
- 当
$state == 0$ ,所选质因数为空时,空集为好子集,则$dp[0] = 1$ 。同时,对于一个好子集而言,无论向中间添加多少个$1$ ,得到的新子集仍是好子集,所以对于空集来说,可以对应出$2^{cnts[1]}$ 个方案,则最终$dp[0] = 2^{cnts[1]}$ 。
根据我们之前定义的状态,$dp[state]$ 表示为:当质因数的选择的情况为
class Solution:
def numberOfGoodSubsets(self, nums: List[int]) -> int:
MOD = 10 ** 9 + 7
primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
cnts = Counter(nums)
dp = [0 for _ in range(1 << len(primes))]
dp[0] = pow(2, cnts[1], MOD) # 计算 1
# num 分解质因数
for num, cnt in cnts.items(): # 遍历 nums 中所有数及其频数
if num == 1: # 跳过 1
continue
flag = True # 检查 num 的质因数是否都不超过 1
cur_num = num
cur_state = 0
for i, prime in enumerate(primes): # 对 num 进行试除
cur_cnt = 0
while cur_num % prime == 0:
cur_cnt += 1
cur_state |= 1 << i
cur_num //= prime
if cur_cnt > 1: # 当前质因数超过 1,则 num 不能添加到子集中,跳过
flag = False
break
if not flag:
continue
for state in range(1 << len(primes)):
if state & cur_state == 0: # 只有当前选择状态与前一状态不冲突时,才能进行动态转移
dp[state | cur_state] = (dp[state | cur_state] + dp[state] * cnt) % MOD
ans = 0 # 统计所有非空集合的方案数
for i in range(1, 1 << len(primes)):
ans = (ans + dp[i]) % MOD
return ans
-
时间复杂度:$O(n + m \times 2^p)$,其中
$n$ 为数组$nums$ 的元素个数,$m$ 为$nums$ 的最大值,$p$ 为$[1, 30]$ 中的质数个数。 - 空间复杂度:$O(2^p)$。