2022-10-23：给你一个整数数组 nums 。如果 nums 的一个子集中，所有元素的乘积可以表示为一个或多个互不相同的质数的乘积，那么我们称它为好子集。比方说，如果 nums =

2022-10-23
北京
本文字数：1553 字
阅读完需：约 5 分钟

2022-10-23：给你一个整数数组 nums 。如果 nums 的一个子集中，所有元素的乘积可以表示为一个或多个互不相同的质数的乘积，那么我们称它为好子集。比方说，如果 nums = [1, 2, 3, 4] ：[2, 3] ，[1, 2, 3] 和 [1, 3] 是好子集，乘积分别为 6 = 23 ，6 = 23 和 3 = 3 。[1, 4] 和 [4] 不是好子集，因为乘积分别为 4 = 22 和 4 = 22 。请你返回 nums 中不同的好子集的数目对 109 + 7 取余的结果。nums 中的子集是通过删除 nums 中一些（可能一个都不删除，也可能全部都删除）元素后剩余元素组成的数组。如果两个子集删除的下标不同，那么它们被视为不同的子集。输入：nums = [1,2,3,4]。输出：6。

答案 2022-10-23：

力扣 1994。具体见代码。这道题，go 和 c++的运行速度都远远不如 java。c++的内存占用比 java 的还高。java 运行速度最优。

代码用 rust 编写。代码如下：

impl Solution {    pub fn number_of_good_subsets(nums: Vec<i32>) -> i32 {        unsafe {            counts = [0; 31];            status = [0; 1 << 10];            for num in nums.iter() {                counts[*num as usize] += 1;            }            status[0] = 1;            for _i in 0..counts[1] {                status[0] = (status[0] << 1) % mod0;            }            for i in 2..=30 {                // 2 几次 3 几次 4几次 5几次 30 几次                let cur_primes_status = primes[i];                if cur_primes_status != 0 && counts[i] != 0 {                    // curPrimesStatus K次                    for from in 0..1 << 10 {                        // from 11111111                        // 枚举所有的状态 from                        // from & curPrimesStatus == 0                        if from & cur_primes_status == 0 {                            // to                            let to = from | cur_primes_status;                            status[to as usize] = ((status[to as usize] as i64                                + (status[from as usize] as i64 * counts[i] as i64))                                % mod0 as i64)                                as i32;                            //            // status[to] += status[from] * counts[i];                        }                    }                }            }            let mut ans = 0;            for s in 1..(1 << 10) {                ans = (ans + status[s]) % mod0;            }            return ans;        }    }}
// 2, 3, 5, 6, 7, 10, 11, 13, 14,// 15, 17, 19, 21, 22, 23, 26, 29, 30static primes: [i32; 31] = [    //        11 7 5 3 2    // 2       0 0 0 0 1    // 2 5     0 0 1 0 1    0, // 0 00000000    0, // 1 00000000    1, // 2 00000001    2, // 3 00000010    0, // 4 00000000    4, // 5 00000100    3, // 6 00000011    8, // 7 00001000    0, // 8 00000000    0, // 9 00000000    5, // 10 00000101    16, 0, 32, 9, 6, 0, 64, 0, 128, 0, 10, 17, 256, 0, 0, 33, 0, 0, 512, // 29  10000000    7,   // 30  2 * 3 * 5   111];
static mut counts: [i32; 31] = [0; 31];
static mut status: [i32; 1 << 10] = [0; 1 << 10];
const mod0: i32 = 1000000007;
fn main() {    let nums = vec![4, 2, 3, 15];    let ans = Solution::number_of_good_subsets(nums);    println!("ans = {:?}", ans);}
struct Solution {}