2338. Count-The-Number-Of-Ideal-Arrays

Not gonna lie, I don’t even get what the questions asking…

MOD = 10**9 + 7
MAX_N = 10**4 + 10
MAX_P = 15  # At most 15 prime factors

sieve = [0] * MAX_N  # Smallest prime factor

for i in range(2, MAX_N):
    if sieve[i] == 0:
        for j in range(i, MAX_N, i):
            sieve[j] = i

ps = [[] for _ in range(MAX_N)]

for i in range(2, MAX_N):
    x = i
    while x > 1:
        p = sieve[x]
        cnt = 0
        while x % p == 0:
            x //= p
            cnt += 1
        ps[i].append(cnt)

c = [[0] * (MAX_P + 1) for _ in range(MAX_N + MAX_P)]

c[0][0] = 1
for i in range(1, MAX_N + MAX_P):
    c[i][0] = 1
    for j in range(1, min(i, MAX_P) + 1):
        c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % MOD

class Solution(object):
    def idealArrays(self, n, maxValue):
        """
        :type n: int
        :type maxValue: int
        :rtype: int
        """
        ans = 0
        for x in range(1, maxValue + 1):
            mul = 1
            for p in ps[x]:
                mul = mul * c[n + p - 1][p] % MOD
            ans = (ans + mul) % MOD
        return ans

Time Complexity: O((n + w(m) * w(m) + mw(m)) where w(m) represents the number of distinct prime factors of m

Space Complexity: O((n + log m) * log m)

Time Taken: did not complete