Unit Power Subsets

We can recursively generate all the possible subsets of Arr and for each subset we can check whether its product can be expressed as product of unit powers of one or more primes. Implementation details will be as per the following algorithm.

Algorithm:

Check Function

Function arguments - integer array ‘subset’ to check for validity.

Returns boolean value whether the given subset is valid.

• Declare frequency map primeFactors.
• Iterate over all elements i of subset
  • Declare integer limit = squareRoot(i)
  • Iterate over j from 2 to limit
    • While i > 0 AND i is divisible by j
      • Divide i by j
      • Increment primeFactors[j]
  • If i > 1
    • Increment primeFactors[i]
• For every frequency x in primeFactors
  • If x > 1
    • Return false
• Return true if (primeFactors is not empty) and false otherwise.

Subsets Function

Function arguments - integer array ‘arr’, integer array ‘subset’ to maintain current subset, 64Bit integer ‘ans, integer value ‘ind’

Generates all subsets of arr and check them for validity.

• If ind == size of options
  • Incement ans by check(subset)
  • Return
• subsets(arr, subset, ans, ind+1)
• Append options[ind[ to subset
• subsets(arr, subset, ans, ind+1)
• Remove the last element from the subset

Given Function

• Declare and initialize 64Bit integer ‘ans’ to 0.
• Declare integer array ‘subset’
• subsets(arr, subset, ans)
• Return ans

We have a very low number of possible Arr[i] values as constraints are very low. Moreover, we can completely ignore some values like 4, 9, 12, etc., which contains multiple power of a single prime, as they can never be part of a valid subset. In total, after these removals, we are left with less than 14 values for possible values of Arr[i], which can be included in a valid subset. We will consider all of these (around 2^20) candidate subsets and check them for validity. If a subset is valid, its total number of occurrences as distinct subsets can be easily estimated by multiplying the frequency of occurrence of each value in ‘Arr’. To check whether a subset is valid or not efficiently, we can store each value’s prime factorization in a bitmask. The ith bit is set in the bitmask if it is divisible by the prime i. Implementation details are as per the following Algorithm.

Algorithm:

Factorize Function

Function arguments - integer value ‘M’ to be factorized.

Returns - Integer bitmask representing prime factorization of ‘M’.

• Declare and initialize integer ‘ans’ as 0.
• Declare and initialize integer ‘init’ as ‘M’.
• Iterate over i from 2 to init
  • If ‘M’ is divisible by i
    • Divide ‘M’ by i
    • Add 2 raised to power i in ans
• Return ans

Check Function

Function arguments - integer array ‘subset’ to check for validity, integer array ‘freq’ storing frequency values of every value, integer array ‘factors’ containing mask values for prime factorization, 64Bit integer ‘ans’ to which will store the actual answer.

Checks whether the given subset is valid. If the subset is valid then add the frequency of that subset in ‘ans’.

• If the subset is empty
  • Return
• Initialize integer bitmask ‘subsetFactors’ = 0, to store factorization of subset
• Iterate over all elements i of subset
  • If factors[i] binaryAND subsetFactors != 0
    • Return
  • subsetFactors = subsetFactors binaryOR factors[i]
• Declare and Initialize integer local to 1.
• Iterate over all elements i of subset
  • local = local * freq[i] % mod
• ans = (ans + local) % mod

Subsets Function

Function arguments - integer array of valid options to construct subarrays, integer array ‘subset’ to maintain current subset, 64Bit integer ‘ans, integer array ‘freq’ to store frequency of each value, integer array ‘factors’ to store prime factorization masks for each value, integer value ‘ind’

Creates every possible subset of all valid options which can be included in a subset.

• If ind == size of options
  • check(subset, freq, factors, ans)
  • Return
• subsets(options, subset, ans, freq, factors, ind+1)
• Append options[ind[ to subset
• subsets(options, subset, ans, freq, factors, ind+1)
• Remove the last element from the subset

Given Function

• Create a integer array of valid options which can be included in a valid subset and initialize it to {2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19}
• Declare and initialize 64Bit integer ‘ans’ to 0.
• Declare subset and freq array of size 21.
• Iterate over integer i in Arr
  • Increment freq[i] by one.
• Declare integer array newOptions.
• Iterate over every integer i in options
  • If freq[i] > 0
    • Append i to newOptions
• Set integer array options = newOptions
• Declare integer array factors of size 21.
• Iterate over i from 2 to 20
  • Set factors[i] = factorise(i)
• subset(options, subset, ans, freq, factors)
• Iterate over i from 1 to freq[1]
  • ans = ans * 2 % mod
• Return ans