“This is my 36th day of participating in the First Challenge 2022. For details: First Challenge 2022”

Topic describes

This is 1994 on LeetCode. Number of good subsets, difficulty is difficulty.

Tag: “Shape pressure DP”

Give you an integer array nums. A subset of NUMs is called a good subset if the product of all elements can be represented as the product of one or more distinct prime numbers.

  • For example, ifnums = [1, 2, 3, 4] ：
    • [2, 3] ，[1, 2, 3] 和 [1, 3]Is a good subset, and the product is6 * 3 = 2 ，6 * 3 = 2 和 3 = 3 。
    • [1, 4] 和 [4]Not a good subset, because the product is, respectively4 = 2 * 2 和 4 = 2 * 2 。

    Would you please returnnumsThe number of pairs of different good subsets in
    1 0 9 + 7 10 ^ 9 + 7     The result of mod.

A subset of NUMS is an array of the remaining elements after deleting some (perhaps none, perhaps all) of numS elements. If two subsets are deleted with different subscripts, they are treated as different subsets.

Example 1:

Input: nums = [1,2,3,4] output: 6 description: a good subset is: - [1,2] : the product is 2 and can be expressed as the product of the prime number 2. - [1,2,3] : the product is 6, which can be expressed as the product of different prime numbers 2 and 3. - [1,3] : the product is 3 and can be expressed as the product of the prime number 3. - [2] : The product is 2 and can be expressed as the product of the prime number 2. - [2,3] : The product is 6, which can be expressed as the product of different prime numbers 2 and 3. - [3] : The product is 3 and can be expressed as the product of the prime number 3.Copy the code

Example 2:

Input: nums = [4,2,3,15] output: 5 description: a good subset is: - [2] : the product is 2 and can be expressed as the product of the prime number 2. - [2,3] : The product is 6, which can be expressed as the product of different prime numbers 2 and 3. - [2,15] : the product is 30, which can be expressed as the product of different prime numbers 2,3 and 5. - [3] : The product is 3 and can be expressed as the product of the prime number 3. - [15] : The product is 15, which can be expressed as the product of different prime numbers 3 and 5.Copy the code

Tip:


  • 1 < = n u m s . l e n g t h < = 1 0 5 1 <= nums.length <= 10^5

  • 1 < = n u m s [ i ] < = 30 1 <= nums[i] <= 30

Cylindrical pressure DP

This problem belongs to NP-complete problem, which is doomed to have no polynomial solution, and can only be solved by “explosive search + pruning” or “shaped pressure DP”.

Prime factorization of the subset product is equivalent to prime factorization of each digit of the subset.

1<=nums[I]<=301 <=nums[I]<=301 <=nums[I]<=30. No more than 303030 prime number including,3,5,7,11,13,17,19,23,29 [2] [2, 3, 5, 7, 11, 13, 17, 19, 23, ,3,5,7,11,13,17,19,23,29 29] [2] (101010), to be remembered as the PPP, in a good subset, each p p p [I] [I] [I] up one more time.

At the same time, the numerical same topic rules, subscript different schemes are considered to be different, so we can use first array CNTSCNTSCNTS statistics in numsnumsnums each number of occurrences, CNTS [VAL]= XCNTS [VAL]= XCNTS [VAL]=x means that the number of occurrences of valvalval in NUMsnumsnums is XXX.

The number used is limited
10 10 ), and the number used appears at most once, it is easy to think of using “shape pressure DP” to solve: we use a binary number to indicate which prime numbers can be decomposed into the good subset product eventually, if the decomposition result contains
p [ i ] p[i] , corresponding to the number in the binary representation
i i Who are the
1 1 , or for
0 0 .

define
f [ s t a t e ] f[state] Is the prime number used for the disassembling result of the current subset product
s t a t e state The number of schemes,
s t a t e state Is a length
10 10 Binary number of, if
s t a t e state The first of
k k Bit binary is represented by
1 1 , represents the value
p [ k ] p[k] Appeared in the disassembly results; If the first
k k Bit binary is represented by
0 0 On behalf of
p [ k ] p[k] It didn’t show up in the disassembly results.

We have initiation conditions: empty set, i.e. F [0]=1f[0] =1f[0] =1.

Without loss of generality, f[s]f[s] how to calculate f[s] : Consider from front to back whether each value (in the range [2,30][2, 30], 111 does not affect good subsets, and discuss at the end) can be added to a subset if and if a value TTT can be added to a subset if and only if the number is not represented by multiplying the same prime numbers.

If a numeric TTT can be added to a good subset, we decompose it into multiple prime numbers in PPP by “trial division”, and use the binary number curcurcur to indicate which prime numbers in PPP are used. Then we need to determine which subsets TTT can be added to. Prevprevprev, prevprevPrev, The final f[s]f[s]f[s] is the sum of the product of all valid PrevprevPrev states F [prev]f[prev]f[prev] f[prev] and the number of occurrences of numerical TTT CNTS [t] CNTS [t] CNTS [t] CNTS [t] [T].

Note that since we are considering each TTT backwards from the range [2,30][2, 30][2,30], we need to iterate backwards when enumerating prevprevPrev, Ensure that the f[prev]f[prev]f[prev] that f[s] relies on to calculate f[s]f[s]f[prev]f[prev] is the number of schemes without considering the current value TTT.

Ans =∑state ‘=11<<10f[state’]ans = \sum_{state’ =1}^{{1 <<10}} F [state’]ans=∑state ‘=11<<10f[state ‘], where state’state ‘state’ corresponds to a legal good subset scheme.

On this basis, consider the influence of number 111 on the answer: Under the premise of each legal state’state ‘state ‘, increasing several 111 does not affect the subset product (that is, the good subset is still a good subset after increasing 111). Therefore, each legal subset state’state ‘state can be corresponding to 2cnts[1]2^{CNTS [1]}2cnts[1] specific schemes (representing that each 111 can be selected or not).

Code:

class Solution {
    int MOD = (int)1e9+7;
    int[] p = new int[] {2.3.5.7.11.13.17.19.23.29};
    int[] cnts = new int[35];
    public int numberOfGoodSubsets(int[] nums) {
        int n = nums.length;
        for (int i : nums) cnts[i]++;
        int mask = 1 << 10;
        long[] f = new long[mask];
        f[0] = 1;
        for (int i = 2; i <= 30; i++) {
            if (cnts[i] == 0) continue;
            // Try dividing I
            int cur = 0, x = i;
            boolean ok = true;
            for (int j = 0; j < 10; j++) {
                int t = p[j], c = 0;
                while (x % t == 0) {
                    cur |= (1 << j);
                    x /= t; c++;
                }
                // If I can be divided more than once by the same prime number, I cannot be added to the subset
                if (c > 1) { 
                    ok = false;
                    break; }}if(! ok)continue;
            // Enumerate the prev of the previous state
            // When considering a new value I, the dependent subset prev stores the number of schemes that have not yet considered I.
            for (int prev = mask - 1; prev >= 0; prev--) {
                // If the current selected number does not conflict with the previous state, the state can be transferred and the scheme number can be accumulated
                if((prev & cur) ! =0) continue; f[prev | cur] = (f[prev | cur] + f[prev] * cnts[i]) % MOD; }}long ans = 0;
        // Count the number of alternatives for all non-empty sets
        for (int i = 1; i < mask; i++) ans = (ans + f[i]) % MOD;
        // On this basis, consider the effect of each 1 choice on the answer
        for (int i = 0; i < cnts[1]; i++) ans = ans * 2 % MOD;
        return (int) ans; }}Copy the code
  • Time complexity: the complexity of occurrence times of each value is O(n)O(n)O(n). Let the value range C=30C =30C =30, the number of states M=1024M =1024M =1024, and the partial complexity of DP is O(C∗M)O(C * M)O(C∗M). O(n+C∗M)O(n +C * M)O(n+C∗M)
  • Space complexity: O(C+M)O(C +M)O(C +M)

The last

This is the No.1994 of our “Brush through LeetCode” series. The series started on 2021/01/01.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour… .

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.