题目

类型：位运算
image.png

解题思路

image.png

代码

  1. class Solution {
  2.     int MOD = (int)1e9+7;
  3.     int[] p = new int[]{2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
  4.     int[] cnts = new int[35];
  5.     public int numberOfGoodSubsets(int[] nums) {
  6.         int n = nums.length;
  7.         for (int i : nums) cnts[i]++;
  8.         int mask = 1 << 10;
  9.         long[] f = new long[mask];
  10.         f[0] = 1;
  11.         for (int i = 2; i <= 30; i++) {
  12.             if (cnts[i] == 0) continue;
  13.             // 对 i 进行试除
  14.             int cur = 0, x = i;
  15.             boolean ok = true;
  16.             for (int j = 0; j < 10; j++) {
  17.                 int t = p[j], c = 0;
  18.                 while (x % t == 0) {
  19.                     cur |= (1 << j);
  20.                     x /= t; c++;
  21.                 }
  22.                 // 如果 i 能够被同一质数试除多次，说明 i 不能加到子集，跳过
  23.                 if (c > 1) { 
  24.                     ok = false;
  25.                     break;
  26.                 }
  27.             }
  28.             if (!ok) continue;
  29.             // 枚举前一状态 prev
  30.             //（确保考虑一个新数值 i 时，依赖的子集 prev 存储的为尚未考虑 i 的方案数）
  31.             for (int prev = mask - 1; prev >= 0; prev--) {
  32.                 // 只有当前选择数与前一状态不冲突，则能够进行转移，将方案数进行累加
  33.                 if ((prev & cur) != 0) continue;
  34.                 f[prev | cur] = (f[prev | cur] + f[prev] * cnts[i]) % MOD;
  35.             }
  36.         }
  37.         long ans = 0;
  38.         // 统计所有非空集的方案数
  39.         for (int i = 1; i < mask; i++) ans = (ans + f[i]) % MOD;
  40.         // 在此基础上，考虑每个 1 选择与否对答案的影响
  41.         for (int i = 0; i < cnts[1]; i++) ans = ans * 2 % MOD;
  42.         return (int) ans;
  43.     }
  44. }