2338. Count the Number of Ideal Arrays

[mah-shamim]

Topics: Math, Dynamic Programming, Combinatorics, Number Theory

You are given two integers n and maxValue, which are used to describe an ideal array.

A 0-indexed integer array arr of length n is considered ideal if the following conditions hold:

• Every arr[i] is a value from 1 to maxValue, for 0 <= i < n.
• Every arr[i] is divisible by arr[i - 1], for 0 < i < n.

Return the number of distinct ideal arrays of length n. Since the answer may be very large, return it modulo 109 + 7.

Example 1:

• Input: n = 2, maxValue = 5
• Output: 10
• Explanation: The following are the possible ideal arrays:
  • Arrays starting with the value 1 (5 arrays): [1,1], [1,2], [1,3], [1,4], [1,5]
  • Arrays starting with the value 2 (2 arrays): [2,2], [2,4]
  • Arrays starting with the value 3 (1 array): [3,3]
  • Arrays starting with the value 4 (1 array): [4,4]
  • Arrays starting with the value 5 (1 array): [5,5]
    There are a total of 5 + 2 + 1 + 1 + 1 = 10 distinct ideal arrays.

Example 2:

• Input: n = 5, maxValue = 3
• Output: 11
• Explanation: The following are the possible ideal arrays:
  • Arrays starting with the value 1 (9 arrays):
    • With no other distinct values (1 array): [1,1,1,1,1]
    • With 2^nd distinct value 2 (4 arrays): [1,1,1,1,2], [1,1,1,2,2], [1,1,2,2,2], [1,2,2,2,2]
    • With 2^nd distinct value 3 (4 arrays): [1,1,1,1,3], [1,1,1,3,3], [1,1,3,3,3], [1,3,3,3,3]
  • Arrays starting with the value 2 (1 array): [2,2,2,2,2]
  • Arrays starting with the value 3 (1 array): [3,3,3,3,3]
    There are a total of 9 + 1 + 1 = 11 distinct ideal arrays.

Example 3:

• Input: cost = [[2, 5, 1], [3, 4, 7], [8, 1, 2], [6, 2, 4], [3, 8, 8]]
• Output: 10

Constraints:

• 2 <= n <= 104
• 1 <= maxValue <= 104

Hint:

1. Notice that an ideal array is non-decreasing.
2. Consider an alternative problem: where an ideal array must also be strictly increasing. Can you use DP to solve it?
3. Will combinatorics help to get an answer from the alternative problem to the actual problem?

[mah-shamim]

We need to count the number of distinct ideal arrays of length n where each element is between 1 and maxValue, and each element is a multiple of the previous one. The solution involves combinatorics and dynamic programming to efficiently compute the result.

Approach

1. Prime Factorization Insight: Each element in the ideal array must be a multiple of the previous element. This implies that the prime factors of each subsequent element must include the prime factors of the previous element with equal or higher exponents.

2. Combinatorial Counting: For each value v from 1 to maxValue, factorize v into its prime factors. The number of valid sequences ending at v can be determined by the product of combinations of exponents for each prime factor. Specifically, for each prime factor with exponent e, the number of valid sequences is given by the binomial coefficient C(e + n - 1, n - 1).

3. Precomputation: Precompute factorials and inverse factorials up to a sufficient limit using modular arithmetic to efficiently compute binomial coefficients.

4. Summing Contributions: For each value v, compute the product of binomial coefficients for its prime factors and sum these products modulo 10^>9 + 7.

Let's implement this solution in PHP: 2338. Count the Number of Ideal Arrays

<?php
/**
 * @param Integer $n
 * @param Integer $maxValue
 * @return Integer
 */
function idealArrays($n, $maxValue) {
    $mod = 1000000007;

    if ($maxValue == 0) {
        return 0;
    }

    $spf = $this->computeSPF($maxValue);
    $max_fact = $n + $maxValue; // Sufficient upper bound for factorial precomputation
    list($fact, $inv_fact) = $this->precomputeFactorials($max_fact, $mod);

    $total = 0;

    for ($v = 1; $v <= $maxValue; $v++) {
        $current = $v;
        $product = 1;

        if ($current != 1) {
            $factors = array();
            while ($current != 1) {
                $p = $spf[$current];
                $count = 0;
                while ($current % $p == 0) {
                    $current = (int)($current / $p);
                    $count++;
                }
                $factors[] = $count;
            }
            foreach ($factors as $e) {
                $a = $e + $n - 1;
                if ($a > $max_fact) {
                    // This case should not occur due to our precomputed max_fact
                    return -1; // Error case should not happen
                }
                $comb = $fact[$a];
                $comb = ($comb * $inv_fact[$e]) % $mod;
                $comb = ($comb * $inv_fact[$n - 1]) % $mod;
                $product = ($product * $comb) % $mod;
            }
        }

        $total = ($total + $product) % $mod;
    }

    return $total;
}

/**
 * @param $maxValue
 * @return array
 */
function computeSPF($maxValue) {
    $spf = array_fill(0, $maxValue + 1, 0);
    for ($i = 2; $i <= $maxValue; $i++) {
        if ($spf[$i] == 0) {
            $spf[$i] = $i;
            if ($i * $i <= $maxValue) {
                for ($j = $i * $i; $j <= $maxValue; $j += $i) {
                    if ($spf[$j] == 0) {
                        $spf[$j] = $i;
                    }
                }
            }
        }
    }
    return $spf;
}

/**
 * @param $a
 * @param $b
 * @param $mod
 * @return int
 */
function pow_mod($a, $b, $mod) {
    $result = 1;
    while ($b > 0) {
        if ($b % 2 == 1) {
            $result = ($result * $a) % $mod;
        }
        $a = ($a * $a) % $mod;
        $b = $b >> 1;
    }
    return $result;
}

/**
 * @param $max
 * @param $mod
 * @return array
 */
function precomputeFactorials($max, $mod) {
    $fact = array_fill(0, $max + 1, 1);
    for ($i = 1; $i <= $max; $i++) {
        $fact[$i] = ($fact[$i - 1] * $i) % $mod;
    }

    $inv_fact = array_fill(0, $max + 1, 1);
    $inv_fact[$max] = $this->pow_mod($fact[$max], $mod - 2, $mod);
    for ($i = $max - 1; $i >= 0; $i--) {
        $inv_fact[$i] = ($inv_fact[$i + 1] * ($i + 1)) % $mod;
    }

    return array($fact, $inv_fact);
}

// Example usage
echo idealArrays(2, 5) . "\n"; // Output: 10
echo idealArrays(5, 3) . "\n"; // Output: 11
?>

Explanation:

1. Prime Factorization with SPF: The computeSPF function precomputes the smallest prime factor (SPF) for each number up to maxValue using a sieve method. This helps in quickly factorizing any number into its prime factors.

2. Factorial Precomputation: The precomputeFactorials function calculates factorials and their modular inverses up to a sufficient limit to handle the largest required binomial coefficient efficiently.

3. Combination Calculation: For each value v, we factorize it into primes and compute the product of binomial coefficients for each prime's exponent. This product gives the number of valid sequences ending at v.

4. Summing Results: The sum of these products for all values from 1 to maxValue gives the total number of ideal arrays, which is returned modulo 10⁹ + 7.

This approach efficiently handles the constraints by leveraging combinatorial mathematics and dynamic programming to avoid brute-force enumeration of all possible sequences.

[kovatz]

Thanks for solving the problem of "Count the Number of Ideal Arrays"

[mah-shamim]

Thanks