Count the Number of Ideal Arrays

Leetcode Problem:

• Count the Number of Ideal Arrays

Summary

• The problem requires finding the number of distinct ideal arrays of length n, where an ideal array is defined as an array where every element is a value from 1 to maxValue, and every element is divisible by the previous element.

Approach

• The approach used is dynamic programming and prime factorization
• The solution first calculates the prime factors of each number from 1 to maxValue and stores them in a list
• Then, it uses a dynamic programming table to calculate the number of ideal arrays for each possible value of the first element
• Finally, it sums up the number of ideal arrays for each value and returns the result modulo 10^9 + 7.

Complexity

• O(n * maxValue * log(maxValue))

Explanation

• The solution first calculates the prime factors of each number from 1 to maxValue and stores them in a list
• Then, it uses a dynamic programming table to calculate the number of ideal arrays for each possible value of the first element
• The dynamic programming table is initialized with c[i][j] = 1, where c[i][j] represents the number of ideal arrays of length i with j prime factors
• Then, for each prime factor p, it updates the dynamic programming table with c[i][j] = (c[i][j] + c[i - 1][j - 1]) % MOD, where c[i - 1][j - 1] represents the number of ideal arrays of length i - 1 with j - 1 prime factors
• Finally, it sums up the number of ideal arrays for each value and returns the result modulo 10^9 + 7.

Solution Code:

const int MOD = 1e9 + 7, MAX_N = 1e4 + 10,
          MAX_P = 15;  // There are up to 15 prime factors
int c[MAX_N + MAX_P][MAX_P + 1];
vector ps[MAX_N];  // List of prime factor counts
int sieve[MAX_N];       // Minimum prime factor

class Solution {
public:
    Solution() {
        if (c[0][0]) {
            return;
        }
        for (int i = 2; i < MAX_N; i++) {
            if (sieve[i] == 0) {
                for (int j = i; j < MAX_N; j += i) {
                    sieve[j] = i;
                }
            }
        }
        for (int i = 2; i < MAX_N; i++) {
            int x = i;
            while (x > 1) {
                int p = sieve[x];
                int cnt = 0;
                while (x % p == 0) {
                    x /= p;
                    cnt++;
                }
                ps[i].push_back(cnt);
            }
        }
        c[0][0] = 1;
        for (int i = 1; i < MAX_N + MAX_P; i++) {
            c[i][0] = 1;
            for (int j = 1; j <= min(i, MAX_P); j++) {
                c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % MOD;
            }
        }
    }
    int idealArrays(int n, int maxValue) {
        long long ans = 0;
        for (int x = 1; x <= maxValue; x++) {
            long long mul = 1;
            for (int p : ps[x]) {
                mul = mul * c[n + p - 1][p] % MOD;
            }
            ans = (ans + mul) % MOD;
        }
        return ans;
    }
};